Transcript Fermat`s Little Theorem

Fermat’s Little Theorem
• The RSA Cryptosystem will require
exponentiation to decrypt messages.
• Exponentiation Notation
• Example 1: Compute Exponentials
• Example 2: compute Exponential Mod
• In Example 2 it is seen that modulus arithmetic
on small exponentials is easy. However, Modular
arithmetic on large numbers can be quite difficult
and is subject to computer errors due to
computer round off.
– Example: Large exponential…
Exponential Notation
• All laws of exponents in the real number system carry over
to MOD arithmetic, except division.
• Laws of Exponents
• Method of Successive Squaring for Arithmetic Modulo m
– Step 1: Break the exponent down into the sum of powers of 2.
– Step 2: Write the base as a succession of the same base with the
exponents from step 1.
– Step 3: Write the base to each power of 2, up to the highest one
used from step 1 (1, 2, 4, 8, …, highest), and perform the
modular arithmetic on these.
– Step 4: Multiply the numbers obtained in 3 modulo m.
– Example 3: Compute Modulo 23
– Example 4: Compute Modulo 41…
Fermat’s Little Theorem
• Fermat’s Little Theorem
• Example 5: Compute powers modulo m
• Example 6: Solve Equation…!