Euler's theorem as primality test?

[huba]

Using "[URL theorem[/URL], and the fact that \varphi(p) = p - 1 when p is prime, and the fact that 2 is coprime to all odd numbers, is it right to say that

2^{m-1} \equiv 1 \ (mod \ m) iff m is prime > 2?

 

[ehrenfest]

Using "[URL theorem[/URL], and the fact that \varphi(p) = p - 1 when p is prime, and the fact that 2 is coprime to all odd numbers, is it right to say that

2^{m-1} \equiv 1 \ (mod \ m) iff m is prime > 2?

Yes, I think so.

 

[huba]

Thanks. My question was related to another thread about prime numbers which resulted in the observation that Wilson's theorem can be used to test if an odd number is prime, but it is a far less efficient way of testing primality than trying factors <= the square root of a number.
I assume that Euler's theorem offers a primality testing method which is better than Wilson's theorem but still worse than the "square root method", in terms of the efficiency of the necessary computation. Does 2^{m-1} have to be calculated to check if 2^{m-1}\equiv \ 1 (mod \ m), or is there a shortcut?

 

[gel]

Note that to calculate e.g., 2³² you don't need to do 31 multiplications. 5 is enough.
<br /> \begin{align*}<br /> &amp;2^2=4,\\<br /> &amp;2^4=4^2=16,\\<br /> &amp;2^8=16^2=256,\\<br /> &amp;2^{16}=256^2=65536,\\<br /> &amp;2^{32}=65536^2=4294967296.<br /> \end{align*}<br />
To calculate 2^(m-1) will require on the order of log(m) multiplications and additions. As you only need to do it modulo n, the multiplications are done on numbers no bigger than n.

Multiplying two numbers of size about n requires log(n)² operations using the normal method of multiplication that you learn as a kid, because they will have log(n) digits.
However, Fast Fourier Transforms can improve this to log(n)log(log(n)).

Altogether, this gives a time on the order of log(n)²log(log(n)) to calculate 2^n-1 modulo n.

However, does this really work as a primality test?

edit: it doesn't. Just tried some examples and got 561 = 3 * 11 * 17 is not prime, but 2⁵⁶⁰=1 (mod 561).

 

[matt grime]

Yes, I think so.

No, it's not. Primes may be in P, but not by doing this. What you're describing isn't even as strong as being a Carmichael number.

 

[gel]

No, it's not. Primes may be in P, but not by doing this. What you're describing isn't even as strong as being a Carmichael number.

Ah, looking at http://en.wikipedia.org/wiki/Carmichael_number" I see that my counterexample of 561 is actually the smallest Carmichael number.

 

[gel]

actually, 341=11*13 is the smallest counterexample. 2³⁴⁰=(2¹⁰)³⁴= 1³⁴=1 (mod 341).