Thread for posting tiny primes

[CRGreathouse]

Originally Posted by 3.14159

About 20-25 tests prove that it is prime. Oh, right.. M-R's weakness = Proth numbers.

You can prove any non-Proth 72-bit number prime with M-R.

How? I know a way with 4843 to 4982 tests (Miller-Bach) under the ERH, but none with 20-25.

And what's this about a Proth exception/weakness?

[3.14159]

And what's this about a Proth exception/weakness?

It sucks if the test is performed on a Proth number. Its weakness is powers of 2 and their multiples.

.. Must be that sucky applet that's misleading me. It sucks with testing Proth numbers.

285*2^171 + 1 divides 10^(2^168) + 1.

[3.14159]

.. Well.. 10^(2^162) + 1 has no factors up to 5000 * 2^200

Rediscovered a Fermat divisor: 124569837190956926160012901398286924947521176078042100592562667521 divides F₂₀₁

Well, I'll keep on the lookout for GF(162, 10)

[CRGreathouse]

Originally Posted by 3.14159

.. Must be that sucky applet that's misleading me. It sucks with testing Proth numbers.

To make sure I understand you: You're saying the applet is slow to test (M-R) numbers that are one more than a number that is divisible by a large power of two?


And what's this about proving primality with a small number of M-R tests?

[CRGreathouse]

Originally Posted by 3.14159

Well, I'll keep on the lookout for GF(162, 10)

I don't see anything here
http://www1.uni-hamburg.de/RRZ/W.Keller/GFN10.html
for what that's worth.

[3.14159]

Originally Posted by Charles

To make sure I understand you: You're saying the applet is slow to test (M-R) numbers that are one more than a number that is divisible by a large power of two?

Yes. It sucks when dealing with Proth numbers.

Originally Posted by Charles

And what's this about proving primality with a small number of M-R tests?

Proving a p22 prime only needs about 15-20 tests. If it passes 15-20 tests, it is a guaranteed prime. Or, since you're inclined to disagree, why not find me a c20-c22 which passes at least 15 M-R tests?

[3.14159]

Concerning GF(162, 10): Methinks I see a PRP.

201 to 500 complete: No divisors below 2^500. (k range is in between 1 and 5000) (155 digits)

[3.14159]

Looking at the tables.. I should look at a wider range of k's. No divisor for GF(162, 10) for k up to 300000, for 2^163

I'm going to try 300k to 1M for the k-range.

Tips, anyone?

[CRGreathouse]

Originally Posted by 3.14159

Proving a p22 prime only needs about 15-20 tests. If it passes 15-20 tests, it is a guaranteed prime. Or, since you're inclined to disagree, why not find me a c20-c22 which passes at least 15 M-R tests?

Sure. c21 = 173856327202426657531 passed 42 M-R tests with the following (random) bases:

95622740577804523455,23069092803048071711,44179559199029113423,158519654882801332750,169885874659273032388,84535319621293019359,152789797831795760686,144846324167413396961,151540879126766719306,116834736382599522275,32716964423973440426,64364236781702628491,69254441727874026049,168218203171825470370,172627028627620587526,71184165222645935452,167170105457191883484,156576076598177849404,134848796708134828009,34983881171709232458,137134901958634022390,44585298146111647206,71030932867307306943,47425085825819583089,59436007712955605992,91413389668922177395,119541168673809843091,95355086327014714891,16011483881968810283,56428911447298258533,62121315216836647481,137716224278304005383,112618261032654595237,89675671930042264760,137943150698040557615,141963564054040556225,147810014197952195906,145754770219812208668,70534413019386161381,12205414224336243559,17177503095892952043,137612790916322884716

but 173856327202426657531 = 12116600581 * 14348605951.

[3.14159]

... *mumbles* Bastard..

[CRGreathouse]

Originally Posted by 3.14159

... Bastard..

It was worth the time spent, then!