A new generation of mathematicians pushes prime number barriers | Hacker News Reader

A new generation of mathematicians pushes prime number barriers

quantamagazine.org

69 pointsdigital5531 comments

"...automorphic forms, which have their own version of the Riemann hypothesis." What's the Riemann hypothesis for automorphic forms?

To automorphic forms, you can associate an L-function. There are similar conjectures about the zeros of those functions than for the Riemann Zeta function.

https://en.wikipedia.org/wiki/Grand_Riemann_hypothesis

thanks!

Never mind I think it means the Ramanujan–Petersson conjecture

> The sieve of Eratosthenes comes alive in this animation, which shows multiples of each prime loping along the number line.

A more accurate depiction would not have a bunch of prime curves starting from 0, but would have each one sprouting from its prime just when that prime is passed over by all existing prime curves.

That would start to resemble some sort of cool fractal.

https://en.wikipedia.org/wiki/Ulam_spiral

If you just make up a number claim it’s prime and nobody disputes it, it’s prime apparently. I don’t think it’s really possible to have a very large prime number, because unless someone has tried every factor it’s really not prime yet, honestly that explains a lot about the elusiveness of the concept.

> If you just make up a number claim it’s prime and nobody disputes it

You can test if a number is prime in polynomial time, much faster than a sieve. There’s no need to test every divisor to know whether a number is prime or not.

Algos like RSA generate large primes millions of times every day—-there’s nothing to take on faith.

Doesn't RSA typically settle for numbers that are probably prime?

Technically I think so, so there’s a tiny bit of faith for RSA but absolutely none for primality in general https://en.wikipedia.org/wiki/AKS_primality_test

I’d argue that you’re just misunderstanding what makes a number prime. You can literally never be 100% sure a randomly generated number is or isn’t prime, it’s just the way numbers work.

I think you have some confusion about RSA cryptography - it relies on numbers that are deliberately generated using very large (known) primes, so these numbers are definitely not "randomly generated".

It takes a short time to generate such a number but a very long time to decompose it, but this is a different problem than telling whether a number is prime.

The primes used in RSA are definitely randomly generated for each new key, unless I’m misunderstanding what you’re trying to say. And afaik determining that the random number is prime is a mixture of “generate a random number using a formula that has a high probability of generating primes” and various probabilistic primality tests. It’s possible AKS has been incorporated to prove the numbers are prime in modern implementations, not sure. But historically RSA traditionally (definitely before 2006) determined primality probabilistically.

ECC doesn’t require primes and so is safer in that respect although I’ve been hearing that ECC might have structural deficiencies that causes a swing back to RSA for the most secure applications.

deterministic tests generally aren't used because the brobibalistic ones can easily get you to a guaranteed chance of 2^-100 of not having a false positive which is enough that it is dramatically more likely that 6 cosmic rays came and flipped the answer than a false positive.

Yeah I didn’t think anyone used deterministic ones because speed, but I don’t know how much faster probabilistic variants are because if the deterministic ones aren’t too much slower I could imagine the added safety margin would be more useful assuming that key generation isn’t a critical path in an application (which it shouldn’t be because typically you don’t generate many many RSA keys dynamically)

A lot of the problem is that the types of people who care about deterministic results care more about asymptotic runtime than wall clock runtime. The other problem is that the asymptotics of AKS are still pretty bad (log(n)^7.5 vs log(n)^2 for Miller Rabin).

Counterexample, roll a dice. That gives you a randomly generated number. You can then test whether said random number is prime by enumeration.

There is literally an entirely deterministic algorithm for checking primality, so you can be 100% sure that a randomly-generated number is prime: https://en.wikipedia.org/wiki/AKS_primality_test

you absolutely can. aks is a polynomial time deterministic primality check.

Ok then break all cryptography with that. It just proves my point you can SAY you can do it but in practice you can’t.

Cryptography is about finding large prime factors of a large number. That's a much harder problem than just determining whether a specific number is prime or not.

I don’t understand you just say it was about finding factors, okay yeah that determines whether a number is prime. You’re not telling me anything I don’t know, I just disagree with your stance.

I don't understand your stance.

You seem to be claiming that the ability to determine whether a number is prime or not is extremely difficult and that it would break (some) cryptography if it were no so. My stance is that (some) cryptography would not be broken unless factorisation of large numbers into two large primes becomes easy.

Can you clarify how you think that some cryptography is broken by a relatively simple test of whether a large number is prime or not?

primality checking is much easier that factoring. it's somewhat unintuitive, but there are deterministic methods of primality testing that don't tell you the factors.

AKS is an example of a deterministic algorithm which works out whether a number is prime or composite and runs in polynomial time in the number of bits in the number.

https://en.wikipedia.org/wiki/AKS_primality_test

I'm not sure why you would expect this to break all (or any) cryptographic protocols.

prime testing is much easier than factoring. you need to factor to break rsa

Some cryptography depends on hardness of factoring, not hardness of checking primality.

How would that work?

The article starts by saying mathematicians want things to work for large numbers, but that doesn't really get to the crux of the issue with primes. Infinite sequences are ubiquitous in number theory, and in general it will be infeasible to have a test for inclusion in these sequences for large enough numbers. But often they have structure that we can use to characterise them very precisely - think about square numbers, it's easy to say what the trillionth square number is, what it's remainder when you divide by 13, etc.

What makes primes hard, and also interesting, is that they seem to be extremely unstructured, we believe they behave like a kind of random number generator, even though they are clearly not random. In fact many of the theorems and conjectures mentioned in the article actually hinge on this. Random numbers are unpredictable on a small scale, but on a large scale they have very nice distributional properties, whereas more structured ones of similar growth rate will often have undesirable restrictions on them.

You should check the concept of "primality certificate".

https://en.wikipedia.org/wiki/Primality_certificate

Reply on news.ycombinator.com