Explore BrainMass

Fermat's little theorem

How many different substitution ciphers are there? Explain.

Fermat's little theorem, which says that if p is a prime number then (n^p) â?' n is always divisible by p is fundamental to many modern methods of cryptography. The important point is that if one restricts attention to possible remainders when divided by p (that is, 0, 1, . . . , p â?' 1), then this gives a method of performing a complex operation, namely raising to the pth power, whose net effect is to give back the original input. Imagine, for a moment, that one could write p = ab for whole numbers a and b. Then a person wishing to communicate a numerical message n, between 0 and p â?' 1, could send the remainder of n^a when divided by p. The person receiving the message would then look for the remainder this leaves when raised to the bth power, recovering the message n.

a Explain why this method works, that is explain why (n^a)^b â?? n (mod p).

b. Why will this method, as described, not be secure? Would it matter if p could be factored in different ways?

Solution Summary

Fermat's little theorem is clearly applied in this case.