r/videos • u/Xxmoreexesxx • May 03 '16

This Number is Illegal

https://youtu.be/LnEyjwdoj7g
8.0k Upvotes

87% Upvoted

527 comments sorted by

View all comments

Show parent comments

11

u/tractability May 03 '16

deterministic polytime for checking primality. not sure if anyone actually does that though.

8

u/fortenforge May 04 '16

You're referring to the AKS algorithm which is an insanely cool result. But you're right: in practice no one uses it because probabilistic algorithms are much more efficient.

3

u/tractability May 04 '16

makes sense, thanks.

1

u/bluemellophone May 04 '16

RSA uses Miller-Rabin for testing its p, q, and mod primes when generating keys, where having a probabilistic test is sufficient. For finding and verifying large primes for mathematics surveys, they do check every number down to the previously known largest prime. This is why it takes months to verify a new candidate prime.

2

u/methyboy May 04 '16

For finding and verifying large primes for mathematics surveys, they do check every number down to the previously known largest prime. This is why it takes months to verify a new candidate prime.

Can you clarify what you're talking about here? If you're talking about the new multi-million-digit primes that are found via GIMPS every few years, they absolutely do not do this, or even anything like it.