## Comment: Arrest Donald Knuth? (Score 2) 205

Actually, a decent mathematician should figure out RSA if you just remind them that every prime number has a primitive root, and that primitive roots of about half of all primes can be used to solve x^3 = a (modulo p) for primes p, and to solve x^3 = a (modulo pq) for a product of two primes pq if p and q are known, but not if only the product pq is known.

For large primes (like 1024 or 2048 bit) the number of calculations needed are a bit lengthy, but even a naive implementation on a modern computer is fast enough to implement it. Maybe not fast enough for hard disk encryption, but fast enough to encrypt a few megabytes of documents.