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

2017-04-19, 21:44   #45
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by xilman Not everyone is laughing. There appears to be at least two groups who are not. Those who do not understand the mathematics behind estimates based on established technology, and those who are now giving serious thoughts as to how the mathematics or technology or both can be improved to the point where the stated task becomes feasible. I'm in the second category but I very much doubt that I will be able to make useful progress in either field of endeavour.
my only thought is some high power of 10 as a base for condensing the number itself if the exponent wasn't divisible by 11 I'd say 10^11 as the base or something like that to work off of to put in in a form that could work.

2017-04-20, 04:57   #46
LaurV
Romulan Interpreter

Jun 2011
Thailand

214028 Posts

Quote:
 Originally Posted by ET_ Even applying a reduction of a factor 100,000 using hypothetical "optical computers", we need more than 27,6 million years to perform it.
I don't know where you got this from.

Assuming (a) an iterative test method (like Lucas Lehmer, fastest primality test known to man) is found for this type of numbers (10^n+7), and assuming that (b) you have a computer which is a trillion times faster than the actual computers (that is, 10^12, faster than every optical or quantum dreams), and assuming that (c) everybody on the planet (10 billion people in the year 2200, or 10^10) have a billion such computers (yes, each person on the planet, including children and grandmothers, have 10^9 such computers in his/her kitchen), and (d) they exchange data instantly, and assuming that (e) a multiplication algorithm is found which is a million (10^6) times faster than actual FFC. (these all sum to 10^37)

For comparison, such "system" will do a 332M (100 mega-digits) LL test (done by ultra-modern, 10 physical cores (20 hyperthreaded) computers in 60 days) in just a millionth part of a yoctosecond, or micro-yocto-second (more exactly: 1.93*10^-30 seconds). It could do all the job GIMPS did from its inception to present (say 25 years, 100 teraflops continuously), in just about 4.5 zeptoseconds.

And it would test all 50 million primes below 1000000000 in just 9.5 picoseconds.

Do you think this is fast enough?

Note that this is 10^9, all GIMPS' range of interest, without doing any TF/P-1 factors elimination, just do bulk LL for all exponents. The remaining job (with all exponents factored we have today may take GIMPS another 50-100 years or so, including Moore's Law).

Such system will do in one second (a blink of an eye) one hundred billion times all the job that takes humanity 200 years to do.

Say more, that you invent a method to store in few atoms and quants all digits of $$10^{10^{1500}}+7$$, and you can instantly access them, and do one iteration of it every yoctosecond (10^-24, or one trillion of trillions of iterations per second).

Then, you still have to do about $$10^{1500}$$ iterations, which will take $$10^{1500-24}$$ seconds.

Or $$\frac{10^{1500-24}}{3600\cdot 24\cdot 365}$$ years.

For comparison, 27 million years is something like 10^7.

Last fiddled with by LaurV on 2017-04-20 at 05:44

2017-04-20, 06:22   #47
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22·23·113 Posts

Quote:
Originally Posted by LaurV
Quote:
 Originally Posted by ET_ Even applying a reduction of a factor 100,000 using hypothetical "optical computers", we need more than 27,6 million years to perform it.
I don't know where you got this from.

...

For comparison, 27 million years is something like 10^7.
Is 10^1468 years not more than 27.6 million years?

2017-04-20, 12:37   #48
LaurV
Romulan Interpreter

Jun 2011
Thailand

896210 Posts

Quote:
 Originally Posted by xilman Is 10^1468 years not more than 27.6 million years?
Well... ... it is, indeed... hehe...

edit: But I still don't know where the 27.6 millions comes from, it is not the universe age which was the subject of the paragraph, etc...

Last fiddled with by LaurV on 2017-04-20 at 12:42

2017-04-20, 12:46   #49
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by LaurV Well... ... it is, indeed... hehe... edit: But I still don't know where the 27.6 millions comes from, it is not the universe age which was the subject of the paragraph, etc...
my guess is messing up millions for billions and taking the diameter of the observable universe instead of a radius.

of course https://en.wikipedia.org/wiki/Observ...ns_on_its_size shows that's not the correct size anyways.

Last fiddled with by science_man_88 on 2017-04-20 at 13:18

 2017-04-20, 15:15 #50 Dr Sardonicus     Feb 2017 Nowhere 132×23 Posts I have no idea of any significance to numbers of the form 10^n + 7. The polynomial x^n + 7 is irreducible in Q[x] for every positive integer n, by Eisenstein's criterion with p = 7. FWIW, I checked 10^n + 7 up to the limit n = 2000, and found pseudoprimes for the exponents n = 1, 2, 4, 8, 9, 24, 60, 110, 134, 222, 412, 700, 999, and 1383. I don't see any obvious pattern. Most (but not all) of these n are even. Six of them are divisible by 3. If n is odd, then 10*(10^n + 7) = (10^(n+1)/2)^2 + 70, so -70 is a quadratic residue of every prime factor of 10^n + 7. If one is testing small primes as divisors for the given odd value of n, this would eliminate about half the candidates.
2017-04-20, 15:59   #51
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by Dr Sardonicus I have no idea of any significance to numbers of the form 10^n + 7. The polynomial x^n + 7 is irreducible in Q[x] for every positive integer n, by Eisenstein's criterion with p = 7. FWIW, I checked 10^n + 7 up to the limit n = 2000, and found pseudoprimes for the exponents n = 1, 2, 4, 8, 9, 24, 60, 110, 134, 222, 412, 700, 999, and 1383. I don't see any obvious pattern. Most (but not all) of these n are even. Six of them are divisible by 3. If n is odd, then 10*(10^n + 7) = (10^(n+1)/2)^2 + 70, so -70 is a quadratic residue of every prime factor of 10^n + 7. If one is testing small primes as divisors for the given odd value of n, this would eliminate about half the candidates.
10^(p-1)-1 is divisible by p for p coprime to 10 ( via fermat's little theorem probably an extension I'm missing to Euler's theorem.) and hence 10^(p-1)+7 is 8 mod p. and for multiples of it that fit these forms it relates to 10^(p-1)+1 etc. mod p to figure it out in this case for the exponent doubling one less than a prime it is 9 mod p. edit: okay scratch that last part my brain is wacko it seems.

Last fiddled with by science_man_88 on 2017-04-20 at 16:37

2017-04-20, 17:17   #52
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,591 Posts

Quote:
 Originally Posted by Dr Sardonicus ...FWIW, I checked 10^n + 7 up to the limit n = 2000, and found pseudoprimes for the exponents n = 1, 2, 4, 8, 9, 24, 60, 110, 134, 222, 412, 700, 999, and 1383. I don't see any obvious pattern. ...
10^n+7 is in Kamada's collection. Many more PRPs are known for it, as well as many factorizations for n<=300

 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 17:33.

Thu Dec 3 17:33:05 UTC 2020 up 13:44, 1 user, load averages: 1.78, 1.67, 1.66