Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euler's theorem as primality test?

  1. Jul 6, 2008 #1
    Using Euler's theorem, and the fact that [tex]\varphi(p) = p - 1[/tex] when p is prime, and the fact that 2 is coprime to all odd numbers, is it right to say that

    [tex]2^{m-1} \equiv 1 \ (mod \ m)[/tex] iff m is prime > 2?
     
  2. jcsd
  3. Jul 6, 2008 #2
    Yes, I think so.
     
  4. Jul 6, 2008 #3
    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 [tex]2^{m-1}[/tex] have to be calculated to check if [tex]2^{m-1}\equiv \ 1 (mod \ m)[/tex], or is there a shortcut?
     
  5. Jul 6, 2008 #4

    gel

    User Avatar

    Note that to calculate e.g., 232 you don't need to do 31 multiplications. 5 is enough.
    [tex]
    \begin{align*}
    &2^2=4,\\
    &2^4=4^2=16,\\
    &2^8=16^2=256,\\
    &2^{16}=256^2=65536,\\
    &2^{32}=65536^2=4294967296.
    \end{align*}
    [/tex]
    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)2 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)2log(log(n)) to calculate 2n-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 2560=1 (mod 561).
     
    Last edited: Jul 6, 2008
  6. Jul 6, 2008 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  7. Jul 6, 2008 #6

    gel

    User Avatar

    Ah, looking at this I see that my counterexample of 561 is actually the smallest Carmichael number.
     
  8. Jul 6, 2008 #7

    gel

    User Avatar

    actually, 341=11*13 is the smallest counterexample. 2340=(210)34= 134=1 (mod 341).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?