Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A new generation of mathematicians pushes prime number barriers

quantamagazine.org

Post reply on HN
Print view View original

21–30 of 34 posts

Re: A new generation of mathematicians pushes prime number barriers

#21

Post by vlovich123 »

magneticnorth wrote: post #18
test77777 wrote: post #13

Earlier quoted context omitted.

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.

Re: A new generation of mathematicians pushes prime number barriers

#22

Post by Ar-Curunir »

test77777 wrote: post #13
akarve wrote: post #8

Earlier quoted context omitted.

> 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.

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.

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

Re: A new generation of mathematicians pushes prime number barriers

#23

Post by Ar-Curunir »

test77777 wrote: post #15
adgjlsfhk1 wrote: post #14

Earlier quoted context omitted.

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.

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

Re: A new generation of mathematicians pushes prime number barriers

#24

Post by eigenket »

test77777 wrote: post #15
adgjlsfhk1 wrote: post #14

Earlier quoted context omitted.

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.

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.

Re: A new generation of mathematicians pushes prime number barriers

#26

Post by JonChesterfield »

test77777 wrote: post #13
akarve wrote: post #8

Earlier quoted context omitted.

> 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.

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.

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

Re: A new generation of mathematicians pushes prime number barriers

#27

Post by bigbillheck »

test77777 wrote: post #15
adgjlsfhk1 wrote: post #14

Earlier quoted context omitted.

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.

How would that work?

Re: A new generation of mathematicians pushes prime number barriers

#28

Post by test77777 »

ndsipa_pomu wrote: post #16
test77777 wrote: post #15

Earlier quoted context omitted.

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.

Re: A new generation of mathematicians pushes prime number barriers

#29

Post by adgjlsfhk1 »

test77777 wrote: post #28
ndsipa_pomu wrote: post #16

Earlier quoted context omitted.

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.

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.

Re: A new generation of mathematicians pushes prime number barriers

#30

Post by ndsipa_pomu »

test77777 wrote: post #28
ndsipa_pomu wrote: post #16

Earlier quoted context omitted.

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?

Post reply on HN