Translate

Friday, August 07, 2015

Finding primes using non-square residues

Back in 2007, was probably just trying to come up with something, and put forward an idea for finding primes by using non-square residues. The idea is simple enough.

Given a known prime p, use one of its non-quadratic residues r, with:

p2 - r

and factor the result, to get a new larger prime in it. If a new large one is in it.

At that time I used 29 and 17.

The quadratic residues of 29 are:

1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28

So yeah, 17 is not one of them.

Start:

292 - 17 = 824 = 8*103

Next iteration:

1032 - 17 = 32*331

Second iteration:

3312 - 17 = 8*13693

Third iteration:

136932 - 17 = ( 23 )( 19 )( 43 )( 28687 )

Fourth iteration:

286872 - 17 = ( 24 )( 1429 )( 35993 )

Fifth iteration:

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

And I mused at that time about why it was going so slow. I did do two more iterations and you can see my musings back then in a post.

But it's interesting, I'm not sure why I thought that would work. And I'm also not so sure on why it should work. Though I'm guessing there is a simple reason. Putting it here to kind of collect it.

Maybe not the most practical thing for finding primes from what I'm seeing, but kind of curious. I think you can have cases where no larger prime comes up, but not sure.

Gives me something to do if I'm bored trying to understand something I used to know, years ago.

It does fade away. Sometimes I struggle to understand my own postings, with enough distance I am not quite certain how I figured something out.

But back then it was so easy I often zoomed through the results, not always leaving enough detail even for myself later on. I try not to do that now.

Have gained perspective.


James Harris

Post a Comment