Playing around with modular arithmetic

[Lenggries]

I just wanted to emphasize that the naive trial division method is O(sqrt(p)), so the Wilson's theorem test, being O(p), is far worse than even that method for p remotely large.

Yeah, I fiddled with it some. You can definitely reduce Wilson's Therorem to p/2 by pairing n with (p-n) = -n^2 mod p, not that that changes the Big-Oh formula. I wouldn't be surprised if there are other tricks that could reduce it further, though. After all, the naive sieve is only reduced to O(sqrt(p)) due to the non-obvious realization that you only need to consider divisors up to the square root of p. In fact, using the prime number theorem, the naive method can be reduced even further if one has a list of all primes less than the sqrt(p) to O(sqrt(p)/ln(p)).

"A fundamentally new idea would be required to obtain a deterministic primality testing algorithm with run time exponent smaller than 6."

Oooohhh... now I know what to work on if I want to drive myself insane

Hmm, you shouldn't get overflow problems until p is around the square root of MaxInt.

I'm not sure he was taking products in modulo, which means he'll hit an overflow a lot faster than sqrt(MAXINT). Even using an unsigned 64 bit integer, he'd overflow before he could test p=23, since 22! > 2^64. Taking products in modulo, however, I think you are correct with your sqrt(MAXINT) approximation.

Actually, RSA can't be broken by a fast prime test. A fast factoring algorithm would break it, though.

Something else I can drive myself insane with...