Primality testing is easy in the sense that if someone discovered that factorization was that easy, they would win the Nobel Prize in Math. Which doesn’t even exist.
Right, a primality test is not hard like factorisation, but it’s harder than multiplication. Our pebblesorters are clearly somewhere between multiplication and prime testing. If a pebblesorter proved something like the AKS algorithm, they would win more than the Gödel prize!
Primality testing is easy in the sense that if someone discovered that factorization was that easy, they would win the Nobel Prize in Math. Which doesn’t even exist.
Right, a primality test is not hard like factorisation, but it’s harder than multiplication. Our pebblesorters are clearly somewhere between multiplication and prime testing. If a pebblesorter proved something like the AKS algorithm, they would win more than the Gödel prize!
Have you been watching Teen Wolf?
Nope—didn’t even know that was a TV series until I wikipediaed it just now.