我们cryptography里讲到的primality test只是讲了一个theorem,
if there exist solutions to ( x^2 = 1 mod p ) other than +1 or -1, then p is not a prime
具体怎么实现就没说
好像不对吧。。。。。。
e.g. Let p=3, then there exist x=5 such that 5^2=1(mod 3).
In this case, 5 is not +1 or -1, but p=3 is still a prime. :P
In this case, 5 is not +1 or -1, but p=3 is still a prime. :P
Huasing Association 1999 - 2013