Comment by tgflynn
10 years ago
It's not a primality test. A primality test determines whether or not a single given integer is prime.
The circuit I described checks that the product of two arbitrary input integers is a specific known integer.
By solving the decision problem for each bit independently you can determine all bits of the 2 input integers and hence factor the known target.
Neat. I wasn't aware of the trick of peeling off a bit at a time.