> Finally, I generated random fluctuations in the number and tested each with the Miller-Rabin primality test. This produced a shortlist of numbers which were very very likely to be prime. I used Dario Alpern’s fantastic tool to determine whether any of them actually were prime.
I thought that in crypto one normally just repeats Miller-Rabin enough times that it's infinitesimally improbable that the candidate isn't a prime, and that the reason for doing this is that it's too expensive to actually prove it. This indicates that it's now feasible to just prove that a number is actually prime; should crypto libraries now switch to a different method of ensuring primality?
From an engineering point of view it really does not matter. The chance that the probabilistic algorithm fails is so insignificantly small, that cosmic rays hitting your CPU registers is probably a bigger problem.
From a mathematical/CS point of view, indeed it was a fairly recent, and fairly pleasant discovery that the primality testing algorithm can be derandomized while still retaining its low complexity (it was suspected for a long time, but proving it was awesome).
Here is one script [0] that was posted on Github yesterday, I believe a few others have been popping up ever since this video [1] by Numberphile on Thursday.
That isn't very difficult. Choose a prime, say 2. Now pick a sufficiently large number of digits to get a high enough resolution. Pick a number that graphically spells out 2. Replace the least significant bit of the number with a zero. You are done.
In general, "fixing" a number such that it is divisible by a given prime is easy.
> Finally, I generated random fluctuations in the number and tested each with the Miller-Rabin primality test. This produced a shortlist of numbers which were very very likely to be prime. I used Dario Alpern’s fantastic tool to determine whether any of them actually were prime.
I thought that in crypto one normally just repeats Miller-Rabin enough times that it's infinitesimally improbable that the candidate isn't a prime, and that the reason for doing this is that it's too expensive to actually prove it. This indicates that it's now feasible to just prove that a number is actually prime; should crypto libraries now switch to a different method of ensuring primality?