I’d like to write a function to generate big primes and semiprimes suitable for cryptography. It’s important to try to factor p-1; the primes should at least be in A073024. But I could encounter a number which can’t be completely factored in a reasonable time, in which case I should discard it. What package can I use to test primality of and try to factor such big numbers?
I think using Primes.jl could be a starting point but I have no personal experience with it and certainly not with cryptographic primes so I can’t tell whether it will be sufficient for you.
1 Like
For cryptographic applications, normally one uses probabilistic primality testing, not factoring. Primes.isprime(p-1) does this — you can easily make the probability of a false positive arbitrarily low (it is \approx 1/10^{15} with the default arguments).
3 Likes
Primes.isprime(p-1) will immediately fail because p-1 is even. Once I know that p is prime, I need to find out if p-1 has a prime factor greater than p^(2/3).
Sorry, I was thinking of isprime(p), for an RSA-like algorithm where you generate two large primes and multiply them.
Not sure what they do in cryptography to ensure that p-1 has large prime factors, but I’m guessing it’s probabalistic?
This is totally not my field at all, but about 15 years ago I did some reading on this sort of thing while teaching an undergraduate course. I think generating the prime p and checking p-1 is backward. You want to focus on making sure p-1 has the desired large prime factor first and then check the primality of p second. So you can generate a prime q that is suitably large to be an acceptable prime factor of p-1 and then set p = jq + 1 for different values of j that make p suitably large. You can test each candidate p for primality and then, once you have found that p is prime, p-1 will have q as a prime factor.
Edit: Thinking a little more, you should use just even values of j, because otherwise p-1 will be odd and p will be even, which is obviously not what you want.
3 Likes
note that modern guidance iiuc doesn’t require testing for “safe primes” since approximately 100% of 2048 bit primes are safe
They have typically discarded cryptography based on large primes. They are being replaced by newer schemes based on code theory and lattice theory etc.
https://csrc.nist.gov/publications/fips
1 Like
The purpose of p-1 having a factor greater than p^(2/3) is to prevent factorization by noisy quantum computers (all quantum computers so far are noisy), as mentioned on the OEIS page. I think elliptic curve factorization would be a good method to try. Has anyone implemented elliptic curve factorization in Julia?
Except for 5 and 7, all safe primes are noisy-quantum-proof primes. The fraction of primes which are noisy-quantum proof is known to be positive; the fraction of primes which are safe is not.