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

That gives

29

^{2}- 17 = 824 = 8*103

and 103 is prime, so now you use 103

^{2}- 17 = 32*331, giving you 331, and now I'm wondering why I picked 17.

It's maybe quicker to just use n

^{2}- 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 331

^{2}- 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 13693

^{2}- 17 = ( 2

^{3})( 19 )( 43 )( 28687 ).

Then next is 28687

^{2}- 17 = ( 2

^{4})( 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:

35993

^{2}- 17 = ( 2

^{5})( 179 )( 226169 )

and one more

226169

^{2}- 17 = ( 2

^{5})( 1598513017 )

and one last one:

1598513017

^{2}- 17 = ( 2

^{5})( 229 )( 859 )( 1879 )( 216036409 )

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

One more to leave on a high note:

216036409

^{2}- 17 = ( 2

^{5})( 19 )( 76762713838183 )

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

James Harris

## No comments:

Post a Comment