Translate

Wednesday, June 20, 2007

Quadratic residue method for finding large primes

The idea is to get quadratic residues modulo some non-square and iterate up with them in the search for ever larger primes.

Start with, say 29 and let 17 be the non-square.

That gives

292 - 17 = 824 = 8*103

and 103 is prime, so now you use 1032 - 17 = 32*331, giving you 331, and now I'm wondering why I picked 17.

It's maybe quicker to just use n2 - 2, as then you get mostly primes at first though as you go farther out with bigger numbers you do tend to get composites.

The idea just shifts you to another distribution of primes--primes with a quadratic residue of 17 or 2 or whatever non-square you pick--so the probability is higher that you will get primes than just going with naturals.

Hmmm...let me do one more iteration, so 3312 - 17 = 8*13693, so it's starting to pick up a little steam. So I went from 29 to 103, to 331, to 13693, in three iterations.

Next would be 136932 - 17 = ( 23 )( 19 )( 43 )( 28687 ).

Then next is 286872 - 17 = ( 24 )( 1429 )( 35993 ).

So this thing is going slow, oh well, so maybe it's not so great an idea for that reason?

Here's another iteration:

359932 - 17 = ( 25 )( 179 )( 226169 )

and one more

2261692 - 17 = ( 25 )( 1598513017 )

and one last one:

15985130172 - 17 = ( 25 )( 229 )( 859 )( 1879 )( 216036409 )

Went backwards with that one. Oh well, just an idea...

One more to leave on a high note:

2160364092 - 17 = ( 25 )( 19 )( 76762713838183 )

Looks like you get about 5 bits added to the length per iteration.


James Harris