mersenneforum.org > Math checking very large number for primality.
 Register FAQ Search Today's Posts Mark Forums Read

 2017-04-17, 18:44 #12 JeppeSN     "Jeppe" Jan 2016 Denmark 2×34 Posts The exponent n has the additional (besides 11) prime factor 5402920651. Cofactor is still composite. The number 10^n + 7 is so huge you cannot primality test it. But you can search for small factors. Knowing the full factorization of the exponent n is maybe a slight advantage when checking for small divisors of 10^n + 7; I do not now. It is extremely unlikely that an arbitrary number that huge be prime. The average distance between consecutive primes that huge is 9.1 * 10^1522. That is also the expected number of "random" candidates you need to test at this size before you hit a prime. /JeppeSN
 2017-04-17, 18:53 #13 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 111100101112 Posts I am pretty sure that no commercially available (super)computers that can be very useful for a number of that size. But if you have a deep enough pocket, there might be options. Let us know your budget.
 2017-04-17, 19:10 #14 firejuggler     Apr 2010 Over the rainbow 2,473 Posts Well, 10^n+7 are 5mod 6, so they have a chance to be prime
 2017-04-17, 19:19 #15 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 36278 Posts The probability of any random number of that size being prime is greater than 0. But it is an understatement to say it is astronomically low. There is nothing special about powers of 10 (5 and 2 to be more precise) + a coprime like 7, compared to any other number when it comes to being prime except that it can be easily represented with decimal based notations. The only thing we can be sure of is that it won't factor into, 2, 5 or 7. Last fiddled with by a1call on 2017-04-17 at 19:27
2017-04-17, 20:44   #16
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

27·5·7 Posts

Quote:
 Originally Posted by a1call I am pretty sure that no commercially available (super)computers that can be very useful for a number of that size. But if you have a deep enough pocket, there might be options. Let us know your budget.
This is total BS. Perhaps you'd like to explain what your imagination has in mind? For a budget, estimate the total wealth of the planet; in fact, you can imagine every physical resource on the planet is dedicated to your "options". Please, let us know how long you think a calculation would take for primality, as well as what algorithm you would be using.

2017-04-17, 20:53   #17

"Kieren"
Jul 2011
In My Own Galaxy!

26·157 Posts

Quote:
 Originally Posted by VBCurtis This is total BS. Perhaps you'd like to explain what your imagination has in mind? For a budget, estimate the total wealth of the planet; in fact, you can imagine every physical resource on the planet is dedicated to your "options". Please, let us know how long you think a calculation would take for primality, as well as what algorithm you would be using.
I believe the explanation could be that a1call's intention is wry irony.

 2017-04-17, 21:43 #18 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 29×67 Posts I just happen to think that the technology to perform specialized tasks such as factoring large integers much quicker than PCs is neither out of reach (given the right resources), nor perhaps non existent. What do you know about optical computers?
 2017-04-17, 22:10 #19 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 29×67 Posts Here is the Wikipedia article for those interested: https://en.m.wikipedia.org/wiki/Optical_computing
2017-04-17, 23:02   #20
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by JeppeSN The exponent n has the additional (besides 11) prime factor 5402920651. Cofactor is still composite. The number 10^n + 7 is so huge you cannot primality test it. But you can search for small factors. Knowing the full factorization of the exponent n is maybe a slight advantage when checking for small divisors of 10^n + 7; I do not now. It is extremely unlikely that an arbitrary number that huge be prime. The average distance between consecutive primes that huge is 9.1 * 10^1522. That is also the expected number of "random" candidates you need to test at this size before you hit a prime. /JeppeSN

the only advantage ( though I did try factoring to 2^30 or thereabouts earlier) I see is it might break the number down into values we can easily mod by the totients for other numbers. since it factors into all odd primes, and all odd numbers above 2 are nontotients according to the OEIS, then the prime divisors of the exponent themselves only help to break the number down to more manageable chunks I think. I still hope there's a form we can put the exponent in that will help in finding factors. At least it's a form ( the whole value 10^n+7) that is 5 mod 6 ( if n is above 0)

10^1+7 =6*2+5
10^2+7 =6*17+5
10^3+7 = 6*167+5
...

if you use it algebraically 6*k+5 the next k is roughly (10*previous k) -3 if that holds up we can give a value to figure out if it fits the form of a possible prime (composites show specific forms for k). but that would brute force it even more probably.

Last fiddled with by science_man_88 on 2017-04-17 at 23:10

2017-04-17, 23:18   #21
Nick

Dec 2012
The Netherlands

5DC16 Posts

Quote:
 Originally Posted by a1call I just happen to think...
It is time for you to start thinking a little deeper before posting here.

At what fraction of the speed of light do electrical signals travel in wires?

For a task which would take many thousands of years, would a switch to optical signalling make any practical difference?

Once you have worked that out, you may understand the incredulous reactions.

2017-04-17, 23:31   #22
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000101100012 Posts

Quote:
 Originally Posted by science_man_88 though I did try factoring to 2^30 or thereabouts earlier) .
doh that was the whole thing not the exponent so the whole 10^n+7 has no factors up to 2^30:

Code:
my(a=39639600000000033079722130334105193516374462454515382070790605358914985114125041349652662917631491895468078068144227588488256698643731392656301687065828647039364869335097585180284485610320873304664240820377108832285808799206086668871981475355607012901091630830301025471386040357260999007608336089976844194508766126364538537876281839232550446576248759510420112471055243135957657955673172345352299040688058220310949388025140588819053919947072444591465431690373800860072775388686735031425736023817399933840555739331789612967251075090969235858418789282170029771749917300694674164737016209063843863711544823023486602712537214687396625868342705921270261329804829639431028779358253390671518359245782335428382401587826662256037049288785974197816738339397949057227919285478001984783327820046311610982467747270922924247436321534899106847502480979159775057889513728084684088653655309295401918623883559378101223949718822361892160105855110817069136619252398279854449222626529937148527952365200132318888521336420774065497849818061528283162421435659940456500165398610651670525967581872312272576910353953026794574925570625206748263314588157459477340390340721137942441283493218656963281508435329143235196824346675487925901422428051604366523321204101885544161429043996030433344359907376778035064505458154151505127356930201786304995038041680449884220972543830631822692689381409196162752232881243797552100562355276215679788289778365861726761495203440291101554746940125702944095269599735362222957327158451869004300363876943433675157128680119087);forprime(x=3,2^30,if(lift(Mod(10,x)^lift(Mod(a,x-1))+7)==0,print(x)))

 Similar Threads Thread Thread Starter Forum Replies Last Post VolMike YAFU 18 2012-04-09 21:39 ixfd64 Math 12 2010-01-05 16:36 NeoGen Software 8 2006-03-20 01:22 Washuu Factoring 10 2005-08-11 05:09 fortega Data 2 2005-06-16 22:48

All times are UTC. The time now is 09:07.

Fri Nov 27 09:07:05 UTC 2020 up 78 days, 6:18, 4 users, load averages: 1.16, 1.27, 1.27