> Even if it did do quite well in terms of accuracy, probabilistic models aren't 100% correct so you still have to check for primality deterministically.
Deterministic primality tests are rarely used in practice -- they're too slow, and the probabilistic tests have such a high accuracy that it doesn't matter.
> on January 18, 2018, I found a numerical sequence that generated the exact same pattern as Shaun’s pattern
Does this mean that we have a sort of bloom filter-esque test for primality? (ie, it will give you a guaranteed no in O(1) but you'll have to crunch numbers to get the yes?)
If so, are there implications for things that want to know "is it prime?" quickly? Crpytography comes to mind, for instance...
> Like with a naive algorithm you’d need to use erastothenes sieve to find primes up to 2^16 to test against.
p(2^16)=6542: if you told me in elementary school that I might disproving something famous I can see myself working on that for a couple of hours daily for a week or so.
Why would anyone ask to find primes? Most people don't know the best algorithm and anyone who needs to code efficient ways of determining primality has intense number theory training.
The "naive" solution typically is a sieve method and checks more than the required number of factors (goes beyond sqrt(n)). It's like asking someone to sort an array and expecting bubble sort because you never use sorting algorithms in what you actually code.
The best way I know (and there are actually better) to find primes is using an approximation algorithm that no one would ever come up with independently without months of research. The Miller-Rabin primality test finds if a candidate for primality n has a % chance of being prime by looking for numbers a < n that don't satisfy Fermat's little equation. Almost every composite number violates Fermat's little equation (Carmichael numbers are the only exceptions).
Once you hit the desired probability that n is prime (testing more a < n raises this probability) you use a deterministic method to determine 100% if n is prime. If it isn't you throw it out and use Miller-Rabin to find another candidate. Even though you might throw some candidates out and have to pick others to check for primality this method is far faster than a purely deterministic solution using a naive sieve methods.
This is a moronic test of ability. It exposes the arrogance of the company in assuming they can evaluate candidates in 15 minutes by asking the most challenging number theory problems out there when they have no understanding of the current methods in the discipline.
> However, the odds of a very large prime (like a gigabyte) looking intentionally ordered over its entire length seems vanishingly small.
Can we estimate how many gigabyte sized primes exist? I think one can do that using the prime number theorem. Let’s call that N. What is the probability one of those N messages is meaningful? I think it is a lot higher than you think it is. I think N is a very big number, even though it is very small compared to the number of composite gigabyte-sized numbers, it is still unimaginably large in absolute terms.
Performing a Miller-Rabin primality test or filling a Sieve of Eratosthenes will almost always be the way to go. However, this line of code seems like magic and that's kind of impressive.
I don't know Colin's logic, but my personal reasoning would be:
1. If this were true then it gives a simple, efficient, deterministic method to test for primes. (You can compute P_n modulo n efficiently using matrix exponentiation.)
2. If there was such a method I am sure I would have heard of it before - and people wouldn't bother using Miller-Rabin or the complicated deterministic primality method
> 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?
I have seen the source code for some large prime generation algos... and they all have a test / verify stage which checks for divisibility by primes upto about a million (or billion), and the prime is then tested against the Miller-Rabin test.
My first reaction after reading this article was that, either they are using a bad version of a self authored prime generation algo, or keys are corrupted.
The guys who wrote the large prime generating algos are very well aware of your concerns (and share them too). I think you should not be too hasty in doubting these 'sophisticated algorithms'. One should probably verify that such issues exist in the prime generating algo, before we start calling one of our best mathematicians/programmers as incompetent.
> One possible reason is that pre-baked primes can be designed to avoid certain pitfalls (e.g. primes close to powers of 2, which the article implies can be solved using the much faster algorithm) or otherwise to be resistant against certain cryptographic attacks.
Why can't those primes be calculated on the fly? Checking a number for being within a certain distance of a power of two is well within the programming capability of a freshman CS student.
> I don't know enough about DH to know if that's really the case here or if it's merely done to avoid having to compute fresh large primes, but I'm going to guess there's a good reason for it.
Given the incentives involved, I see strong reason to believe this is not the case.
I noticed that too, I think he may be referring to the fact that generating super large actual prime numbers is hard, so people use probabilistic algorithms to generate probably almost primes
That made me wonder how the game determines if the number is a prime or not. Turns out it's the Miller-Rabin test with a deterministic variant used for the range (up to 2^53) the game supports. I don't know why the game internally uses a bigint implementation while only supporting numbers up to 2^53 though...
Noted in the details section of the link you provided:
"Primality testing on numbers larger than (2^31) uses the probabilistic Miller-Rabin algorithm."
reply