checking very large number for primality.

[science_man_88]

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.

[LaurV]

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.

That is about 10^1468 years....

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

[xilman]

Originally Posted by LaurV

I don't know where you got this from.

...

That is about 10^1468 years....

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

Is 10^1468 years not more than 27.6 million years?

[LaurV]

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...

[science_man_88]

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.

[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.

[science_man_88]

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.

[Batalov]

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