3 ms·
It's not really clear to me what they invented. You basically have two computational options, both with drawbacks. You could use randomness and find one by gue
by danbruc 3y ago
It's not really clear to me what they invented.
You basically have two computational options, both with drawbacks. You could use randomness and find one by guessing, but the method is inconsistent — you run the risk of generating a different prime every time. Or you could use a more reliable, deterministic algorithm, but at a heavy computational cost.
If you use a pseudorandom number generator and fix the seed, then you get a deterministic result. But I guess we can not prove that replacing random numbers with pseudorandom ones does not alter the behavior of the algorithm. So they came up with something clever where they use true random numbers to find a primes and are able to proof this while at the same time mostly canceling out the effect of the random numbers used so that the prime number they get pack is the same every time with high probability. Or am I misunderstanding the article?
- jksk61 3y agoI guess that algorithm used to get the prime number they want to generate, involves sampling from some kind of distribution such that by Law of large numbers it converges in probability to the same thing (but of course much more advanced than that).
- eklitzke 3y agoAccording to the article, the original motivating problem posed by Terence Tao is to develop an algorithm that deterministically generates an N-digit prime in polynomial time. The article says of the new algorithm: >The algorithm works for infinitely many input lengths, but it doesn’t cover all lengths of digits. There may still be some values of n out there for which the algorithm doesn’t deterministically produce a prime. So the advancement here is that they've "nearly solved" the problem posed by Tao, and maybe (hopefully) someone else will be able to build on their solution to fully solve the problem.