Friday, August 11, 2006
with a basic result that I am sure is considered trivial by many, which I found fascinating, which is that given an odd natural number n,
n^2 - 2 = 0 mod p
will only be true for primes p that have 2 as a quadratic residue. Well, duh, you might say, but I realized that offered a neat route to finding large prime numbers, quickly, and since you can use any quadratic residue that is not a square, I'll show what I mean with 17.
And start with n=29, while you can use any natural n to start that is coprime to 17:
29^2 - 17 = 824 = 8*103
And I have the prime number, 103.
So now you use 103^2 - 17 = 32*331, giving you 331.
Then 331^2 - 17 = 8*13693, so I get 13693, in three iterations.
(Astute readers may note that I could use an even number instead of odd numbers with 17 to eliminate the factors of 2, but hey, they're easy to divide off anyway.)
Next is 13693^2 - 17 = 8*19*43*28687, so the next prime is 28687.
Next is 28687^2 - 17 = 16*1429*35993.
One more iteration: 35993^2 - 17 = 32*179*226169
So after 5 iterations starting with 29, the largest prime I have is 226169.
So how is it growing roughly?
One benefit of this approach is that it likes small primes paired with a much larger prime, so even as the numbers get bigger, it's not terribly hard to factor them, as most factors will be small primes.
And that's a simple idea with a simple idea, where you can get randomness by starting with a random or pseudo-random n, and pick whatever quadratic residue you like, as long as it's not a square, and is coprime to n, and off you go, randomly generating ever larger primes.
So yes, you can start with a really large n, and are likely to immediately get much bigger primes than I got starting with n=29.
So what's wrong with this idea which might speed up how quickly your browser can connect by SSL? Well, I'm posting it for objective criticism, but I suspect instead I'll get a lot of namecalling and other juvenile behavior from people who will hate the idea—because I give it.
(So yes, this could be worth money if I cared at all about patenting it, like, millions of dollars U.S. because of the volume of usage of RSA systems.)
That's the real mathematical world. Of course, if it IS practical, then someone somewhere in some country should pick it up, and later I'll use this as yet another example of how real mathematicians behave today, when I say it's because math is a DIFFICULT SUBJECT, so there are more "mathematicians" than can be supported by real discoveries, so the bulk of them make things up!!!
So they have to come after people who don't, which is why they do it in such low ways, like calling names like "crank" or "crackpot" because they are cons trying to keep people from noticing how little they actually accomplish compared to what they claim to accomplish in mathematical areas.
[A reply to someone who wrote the if James does this using a fixed algorithm, then his primes will be predictable.]
Why start with small numbers&helllip;I just gave a quick demonstration of a simple idea.
Practically you'd probably start with a number roughly the size of the prime you wanted, generated pseudo-randomly like with any other method, so it'd probably only take a few iterations.
[A reply to someone who asked James how he proves that he gets prime numbers.]
How does anyone prove primality when looking for primes to use in public keys?
That is detail irrelevant to the idea, which applies to any approach for finding large primes for use with RSA.
An important aspect of this particular approach though is that composites generated by it will tend to pair very small primes with very large primes, making them easy to factor.
n^2 - 2 = 0 mod p
will only be true for primes p that have 2 as a quadratic residue. Well, duh, you might say, but I realized that offered a neat route to finding large prime numbers, quickly, and since you can use any quadratic residue that is not a square, I'll show what I mean with 17.
And start with n=29, while you can use any natural n to start that is coprime to 17:
29^2 - 17 = 824 = 8*103
And I have the prime number, 103.
So now you use 103^2 - 17 = 32*331, giving you 331.
Then 331^2 - 17 = 8*13693, so I get 13693, in three iterations.
(Astute readers may note that I could use an even number instead of odd numbers with 17 to eliminate the factors of 2, but hey, they're easy to divide off anyway.)
Next is 13693^2 - 17 = 8*19*43*28687, so the next prime is 28687.
Next is 28687^2 - 17 = 16*1429*35993.
One more iteration: 35993^2 - 17 = 32*179*226169
So after 5 iterations starting with 29, the largest prime I have is 226169.
So how is it growing roughly?
One benefit of this approach is that it likes small primes paired with a much larger prime, so even as the numbers get bigger, it's not terribly hard to factor them, as most factors will be small primes.
And that's a simple idea with a simple idea, where you can get randomness by starting with a random or pseudo-random n, and pick whatever quadratic residue you like, as long as it's not a square, and is coprime to n, and off you go, randomly generating ever larger primes.
So yes, you can start with a really large n, and are likely to immediately get much bigger primes than I got starting with n=29.
So what's wrong with this idea which might speed up how quickly your browser can connect by SSL? Well, I'm posting it for objective criticism, but I suspect instead I'll get a lot of namecalling and other juvenile behavior from people who will hate the idea—because I give it.
(So yes, this could be worth money if I cared at all about patenting it, like, millions of dollars U.S. because of the volume of usage of RSA systems.)
That's the real mathematical world. Of course, if it IS practical, then someone somewhere in some country should pick it up, and later I'll use this as yet another example of how real mathematicians behave today, when I say it's because math is a DIFFICULT SUBJECT, so there are more "mathematicians" than can be supported by real discoveries, so the bulk of them make things up!!!
So they have to come after people who don't, which is why they do it in such low ways, like calling names like "crank" or "crackpot" because they are cons trying to keep people from noticing how little they actually accomplish compared to what they claim to accomplish in mathematical areas.
[A reply to someone who wrote the if James does this using a fixed algorithm, then his primes will be predictable.]
Why start with small numbers&helllip;I just gave a quick demonstration of a simple idea.
Practically you'd probably start with a number roughly the size of the prime you wanted, generated pseudo-randomly like with any other method, so it'd probably only take a few iterations.
[A reply to someone who asked James how he proves that he gets prime numbers.]
How does anyone prove primality when looking for primes to use in public keys?
That is detail irrelevant to the idea, which applies to any approach for finding large primes for use with RSA.
An important aspect of this particular approach though is that composites generated by it will tend to pair very small primes with very large primes, making them easy to factor.
# posted by James Harris @ 08:23 
