- Fermat's Little Theorem
- if p is a prime and p does not divide a, then
- a
^{p-1}≡ (1 mod p) - Example
- 2
^{10 }= 1024 ≡ 1 (mod 11) - can then evaluate 2
^{53}(mod 11) - 2
^{53 }= (2^{10})^{5}2^{3}≡ 1^{5}2^{3}≡ 8 (mod 11) - We now require an analog for composite modulus n
- Define φ(n) as the number of integers a between 1 and n such that gcd(a,n) = 1
- Example
- φ(10) = 4 [1,3,7,9]
- Also can be deduced from chinese remainder theorem
- φ(n) = n Π
_{p|n}(1-1/p) - φ(p) = p - 1 where p is a prime number
- when n = pq where p and q are primes φ(pq) = (p - 1)(q - 1)
- Euler's Theorem
- If gcd(a,n) = 1, then a
^{φ(n) }≡ 1 (mod n) - Example
- What are the last 3 digits of 7
^{803} - same as working mod 1000
- 1000 = 2
^{3}5^{3} - φ(1000) = 1000(1-1/2)(1-1/5) = 400
- Example
- Compute 2
^{43210 }(mod 101) - Note that 101 is prime, therefore 2
^{100 }≡ 1 (mod 101) - Therefore (2
^{100})^{432}2^{10}= 1^{432}2^{10}≡ 1024 (mod 101) ≡ 14

## Tuesday, October 8, 2013

### Notes - Fermat's Little Theorem and Euler's Theorem

The following are notes from Introduction to Cryptography with Coding Theory.

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment