Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to implement Fermat's primality test to test whether a given number n is prime or not. According to Wikipedia the test is as follows:

Given an integer n, choose some integer a coprime to n and calculate a^(n − 1) modulo n. If the result is different from 1, then n is composite. If it is 1, then n may or may not be prime.

So you basically run the test for some randomly generated numbers, and after that you can affirm with some degree of certainty that the number is prime.

However, I am having trouble trying to make this work with small sample numbers. Take 17 for example. Let's say the coprime we'll use will be 11.

11^(17-1) = 45949729863572160

But 45949729863572160 % 17 is 0, so this would mean that 17 is composite, when we know it's prime.

What part am I interpreting wrong on Fermat's test?

Update: I changed the numbers above to illustrate the problem more clearly.

share|improve this question

migrated from programmers.stackexchange.com Dec 14 '11 at 21:44

This question came from our site for professional programmers interested in conceptual questions about software development.

1  
is it not supposed to be mod n? you're doing mod 2 –  Morpheus Dec 14 '11 at 16:56
1  
Yep, I realized just after posting. sorry about that. –  daniels Dec 14 '11 at 17:03
2  
Eleven to the sixteenth power is an even number? –  Eric Lippert Dec 14 '11 at 18:05
    
11^(17-1) = 45949729863572161 –  nikie Dec 14 '11 at 18:09

1 Answer 1

up vote 15 down vote accepted

You are doing the computation in inexact arithmetic. $11^{16}$ cannot possibly be an even number. In fact, every power of eleven obviously ends in a one.

You're probably doing the computation in doubles. Doubles are only accurate to about fifteen decimal places; after that they round off.

Moreover, you do not need to calculate the whole big number. Use this identity:

$(a \times b) \bmod c$ is congruent modulo $c$ to $(a \bmod c) \times (b \bmod c)$

Make sure that makes sense to you. Take, say, $15$ and $18$, and you want to work out $(15\times 18) \bmod 4$. You could multiply $15$ by $18$ and then divide by $4$ and take the remainder. But think about it like this.

$(15 \times 18) =$

$( (3 \times 4 + 3) \times (4 \times 4 + 2 ) ) =$

$(3 \times 4) \times (4 \times 4) + 3 \times (4 \times 4) + 2 \times (3 \times 4) + 3 \times 2$.

Obviously the first three summands are all divisible by 4, so they go away modulo 4. So

$(15 \times 18) \bmod 4$ is congruent mod 4 to $(15 \bmod 4) \times (18 \bmod 4)$.

Which is equal to $3 \times 2$, so $(15 \times 18) \bmod 4$ is congruent modulo 4 to $(3 \times 2) \bmod 4$, which is a much easier problem to solve.

Do the same thing for powers.

$11^{16} \bmod 17$ is congruent mod 17 to $(11^{8} \bmod 17) \times (11^{8} \bmod 17)$

and the problem is now much easier to solve. Keep going:

$11^{8} \bmod 17$ is congruent $\bmod 17$ to $(11^{4} \bmod 17) \times (11^{4} \bmod 17)$

and now the problem is yet easier. Keep going!

$11^{4} \bmod 17$ is congruent $\bmod 17$ to $(11^{2} \bmod 17) \times (11^{2} \bmod 17)$

And now we have an easy problem to solve. $121 \bmod 17$ is 2, so $11^{4} \bmod 17$ is congruent to $2 \times 2 \bmod 17$. Therefore $11^{4} \bmod 17$ is 4.

$11^{8} \bmod 17$ is congruent $\bmod 17$ to $11^{4} \bmod 17 \times 11^{4} \bmod 17$, so $11^{8} \bmod 17$ is congruent mod 17 to $4 \times 4$, which is 16. Therefore $11^{8} \bmod 17$ is 16.

Similarly, $11^{16} \bmod 17$ is congruent $\bmod 17$ to $16 \times 16$, which is easily determined to be congruent to $1 \bmod 17$.

Therefore $11^{16}$ gives a remainder of 1 when divided by 17. That's a lot easier than doing the big multiplication and the big division, particularly when the numbers get large.

And sure enough, we got one, so that is evidence that 17 is prime.

share|improve this answer
1  
Thanks for the exhaustive answer. –  daniels Dec 14 '11 at 18:26
    
"You're probably doing the computation in doubles. Doubles are only accurate to about fifteen decimal places; after that they round off. " this it correct but misleading... mariusbancila.ro/blog/2013/10/24/… missleading in a sense that inexperienced devs might expect guaranteed 15 dec places regardles of calculations they do on double –  NoSenseEtAl Feb 14 at 19:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.