The question about “pseudoprimes” is really a red herring. First a number N is pseudoprime for 2 if N divides 2^N - 2. There are not very many non-prime pseudoprimes for 2 (and the test can be refined somewhat to reduce that already small probability). Then you try it for 3. Does N divide 3^N - 3. If it does you can try 5 and 7 and at this point, the chances of non-primality are getting absurd. There actually non-primes that satisfy the pseudoprime tests to every base. But they are few and very far between.
But suppose you do use a non-prime? In principle, your key will be easier to crack, but only if the non-primality is suspected. If your base is 1024 bits, then the assumption is that the prime factors are around 512 bits each, but your pseudoprime will likely have factors that are only about 256 bits each and you won’t be looking for such factors.
Of course, if you really do want a guarantee that your suspected prime really is prime, you can always go ahead and deterministically check it for primality. It takes longer, but if that’s what you want, that’s what you want; (and it’s not so bad; it can be done in polynomial-time in the number of digits).
Please folks, don’t throw out seives and such. Methods like that have absolutely nothing whatsover to do with finding large primes for RSA type methods.
Start with this section of the above linked Wikipedia article.
In practice, for RSA one finds large primes thus:
Pick a very large random number that’s not divisible by small primes (e.g., 2 and 3).
Test it using one of the methods listed in the link.
If it fails, go on to the next candidate prime in sequence. No need to randomize again. E.g., adding 6 works if you started with a non-multiple of 2 and 3.
Once you have you primes, put them into your RSA algorithm and do some test encrypting and decrypting. If it works, you should be fine. (This virtually rules out the one in a zillion chance you didn’t really get a prime.)
The test I was thinking of is called Euclid’s_algorithm. Given two numbers, it’s a fast simple method of finding the largest number that divides both of them evenly.
The linked article goes into detail, but the method is simple. Divide the smaller number into the larger, and replace the larger one with the remainder. Since that must be smaller than the original small one, divide back the other way, and repeat (alternating directions) until you get a remainder of 0. The last divisor is the Greatest Common Factor.
Somebody (I’m sure his name is in the RSA article linked in a previous post) proved that for large non-primes you have a 50% chance of finding a common factor. So to see if a number is “probably prime” you test it against random numbers until you find a common factor other than 1, or you’re satisfied the chance of being non-prime is small enough.
Hari Seldon’s pseudoprime test gives smaller probabilities at each step, so it will converge faster to the reliability you want, but Euclid is too cool to ignore!
So far as the assertion that for large composite numbers you have a 50% chance of finding a common factor goes, I think you may be misremembering something; can you find a cite for the theorem you are referring to?
Yes, I was mistaken, but not completely off. In Wikipedia’s “Coprime” article, the Probabilities section says that the probability that two numbers don’t have a common factor is almost 61%, leaving the chance that they do at about 39%.
(I was sure I saw 50% somewhere quite recently. No idea where or why. Thanks for making me check!)
As a practical matter, though, that 61% number is for all composite numbers. If you avoid even numbers a-priori, it rises to 81%, and if you’ve avoided numbers divisible by 2 or 3, it rises to 91%, leaving only a 9 percent chance two otherwise random numbers have a common factor.
That 61% number (more exactly, 6/π[sup]2[/sup]) is for all numbers, period. (Specifically, the proportion of pairs of positive integers below N which are coprime tends to 6/π[sup]2[/sup] as N tends to infinity.)
The 61% is the product of (1 - 1/p[sup]2[/sup]) over all primes p, incidentally (two numbers being coprime if they have no prime factor in common, and residues modulo distinct primes being independent); it’s the probability that both numbers are indivisible by 2 times the probability that both numbers are indivisible by 3 times the probability that both numbers are indivisible by 5 and so on. So, sure, you can nominally increase it by removing the factors corresponding to the primes 2 or 3, but this just means rather than checking A and B for common factors which may include 2 or 3, you first check A and B for 2 and 3, then check A and B for any other common factors. Same thing ultimately.
Sorry, where I said “probability that both numbers are indivisible by p”, I should of course have said “probability that it’s not the case that both numbers are divisible by p”, in each instance.
Yes, obviously for all numbers, not just composite. My point is, you’re not likely ever comparing a pair of random numbers when using Euclid’s algorithm, but as a minimum only random odd numbers.
You can save some time and work by making sure that you start with an odd number (flip the low order bit of your random number to 1) and adding two (instead of one) before each prime test. There’s no reason to check the even numbers.
Thinking about this further, even using that 61 percent figure, you can’t use the 39 percent chance repeatedly.
You’re going to stop after you find that your number is not relatively prime with another number. After a few trials, the most likely result is just that your number doesn’t have a small factor, and your chance of finding a common factor is smaller each time if you don’t have a small factor.
In other words, after comparing your number with N random numbers and not finding a common factor, the chance of you number not being prime isn’t (1-0.39)^N, but something much larger.