Fermat's little theorem
Not what you're looking for?
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?
Purchase this Solution
Solution Summary
Fermat's little theorem is applied in this case. How many different substitution ciphers are there is determined.
Solution Preview
I'm attaching the solution in .pdf and .docx formats.
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 ...
Purchase this Solution
Free BrainMass Quizzes
Solving quadratic inequalities
This quiz test you on how well you are familiar with solving quadratic inequalities.
Geometry - Real Life Application Problems
Understanding of how geometry applies to in real-world contexts
Multiplying Complex Numbers
This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.
Probability Quiz
Some questions on probability
Graphs and Functions
This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.