- Modular Arithmetic or Congruences
- Let a, b, n be integers with n ≠ 0
- a ≡ b (mod n)
- read as a is congruent to b mod n if a-b is a mutliple of n
- or congruent if a and b differ by a multiple of n
- can be rewritten as a = b + nk for some integer k
- Examples
- 32 ≡ 7 mod 5
- -12 ≡ 37 mod 7
- Proposition
- let a, b, c, n be integers with n ≠ 0
- a ≡ 0 mod n if and only if n|a
- a ≡ a mod n
- a ≡ b mod n
- if a ≡ b and b ≡ c mod n, then a ≡ c mod n
- Proposition
- let a, b, c, d, n be integers with n ≠ 0 and suppose a ≡ b mod n and c ≡ d mod n
- then a + c = b + d, a - c = b - d, ac ≡ bd mod n
- Modulo operations
- addition - we add them as integers then if the product is less than n we stop, if the product is larger than n-1 then we divide by n and take the remainder.
- subtraction - same as addition
- multiplication- same as addition
- note - we can use negative but usually use positive integers
- division
- let a, b, c, d, n be integers with n ≠ 0 and with gcd(a,n)=1. If ab ≡ ac mod n then b ≡ c mod n. In other words, if a and n are relatively prime,we can divide both sides of the congruence by a
- Examples
- Solve 2x + 7 ≡ 3 mod 17
- 2x ≡ -4
- x ≡ -2 ≡ 15
- division allowed because gcd(2,17) = 1
- Solve 5x + 6 ≡ 13 mod 11
- 5x ≡ 7
- 7 ≡ 18 ≡ 29 ≡ 40
- 5x ≡ 7 is equivalent to 5x ≡ 40
- x ≡ 8 mod 11
- Proposition
- Suppose gcd(a,n) = 1. Let s and t be integers such that as + nt = 1. (They can be found via the extended euclidean algorithm) Then as = 1 mod n, so s is the multiplicative inverse for a mod n
- Example
- solve 11,111x ≡ 4 mod 12,345
- gcd
- 12,345 = 1 * 11,111 + 1,234
- 11,111 = 9 * 1,234 + 5
- 1234 = 246 * 5 + 4
- 5 = 1 * 4 + 1
- 4 = 4 * 1 + 0
- Extended Euclidean Method
- x
_{0}= 0 - x
_{1}= 1 - x
_{2}= -1 * 1 + 0 = -1 - x
_{3}= -9 * -1 + 1 = 10 - x
_{4}= -246 * 10 + -1 = -2461 - x
_{5}= -1 * -2461 + 10 = 2471 - Therefore
- 11111 * 2471 + 12345 * y
_{5}= 1 - 11111 * 2471 ≡ 1 (mod 12345)
- multiple original 11111x ≡ 4 by 2471 to get
- x ≡ 9884 (mod 12345)
- Summary
- Finding a
^{-1}(mod n) - use extended euclidean algorithm to find integers s and t such that as + nt = 1
- a
^{-1 }≡ s (mod n) - Solving ax ≡ c (mod n) when gcd(a,n) = 1
- use the extended euclidean algorithm to find as + nt = 1
- the solution is x ≡ cs (mod n)
- What if gcd(a,n)>1?
- If d does not divide b, there is no solution
- assume d|b consider the new congruence
- (a/d)x ≡ b/d (mod n/d)
- solve above to obtain solution x
_{0} - the solutions of original congruence ax ≡ b (mod n)
- x
_{0, }x_{0 }+ (n/d), x_{0 }+ 2(n/d),...., x_{0}+(d-1)(n/d) mod n_{} - Example
- solve 12x ≡ 21 (mod 39)
- gcd (12,39) =3
- divide by 3
- 4x ≡ 7 (mod 13)
- we can get a x
_{0}of 5 through trial and error or the extended euclidean method - we get two more solutions by adding 39/3 once then twice to obtain 18 and 31 as other answers.

## Friday, September 20, 2013

### Notes - Congruences

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

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment