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

11–20 of 34 posts

Re: A new generation of mathematicians pushes prime number barriers

#11

Post by creata »

akarve wrote: post #8
test77777 wrote: post #7

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?

Re: A new generation of mathematicians pushes prime number barriers

#12

Post by akarve »

creata wrote: post #11
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.

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

Re: A new generation of mathematicians pushes prime number barriers

#13

Post by test77777 »

akarve wrote: post #8
test77777 wrote: post #7

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.

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.

Re: A new generation of mathematicians pushes prime number barriers

#14

Post by adgjlsfhk1 »

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.

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

Re: A new generation of mathematicians pushes prime number barriers

#15

Post by test77777 »

adgjlsfhk1 wrote: post #14
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.

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.

Re: A new generation of mathematicians pushes prime number barriers

#16

Post by ndsipa_pomu »

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.

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.

Re: A new generation of mathematicians pushes prime number barriers

#17

Post by credit_guy »

test77777 wrote: post #7

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.

You should check the concept of "primality certificate".

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

Re: A new generation of mathematicians pushes prime number barriers

#18

Post by magneticnorth »

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.

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.

Re: A new generation of mathematicians pushes prime number barriers

#19

Post by adgjlsfhk1 »

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.

prime testing is much easier than factoring. you need to factor to break rsa
Post reply on HN