Cryptography: Number Theory - Congruence

Congruences 

•Let a and b be integers and m be a positive integer. We say that a is congruent to b modulo m  if
  m divides a – b.

•We use the notation a ≡ b (mod m) to indicate that a is congruent to b modulo m.

•In other words:
a ≡ b (mod m) if and only if a mod m = b mod m.

•Is it true that 46 º 68 (mod 11) ?

•Yes, because 11 | (46 – 68).

•Is it true that 46 º 68 (mod 22)?

•Yes, because 22 | (46 – 68).

•For which integers z is it true that z º 12 (mod 10)?

•It is true for any zÎ{…,-28, -18, -8, 2, 12, 22, 32, …}

 

Theorem:

Let m be a positive integer. The integers a and b are congruent modulo m if and only if there is an integer k such that a = b + km.

7 ≡ 1(mod3)

−8 ≡ 1(mod3)

−2 ≡ 1(mod3)

7 ≡ −8(mod3)

−2 ≡ 7(mod3)

Theorem:

Let m be a positive integer. If a º b (mod m) and c º d (mod m), then

  a + c ≡ b + d (mod m) and

  ac ≡ bd (mod m).

Proof:

We know that a ≡ b (mod m) and c ≡ d (mod m) implies that there are integers s and t with
b = a + sm and d = c + tm.

Therefore,

b + d = (a + sm) + (c + tm) = (a + c) + m(s + t) and

bd = (a + sm)(c + tm) = ac + m(at + cs + stm).

Hence, a + c ≡ b + d (mod m) and ac ≡ bd (mod m).

 

Cryptography: Number Theory - Modular Arithmetic

Modular Arithmetic 

Given any integer a and a positive integer n, and given a division of a by n that leaves the remainder between 0 and n − 1, both inclusive, we define

  a mod n    to be the remainder.

Note that the remainder must be between 0 and n − 1, both ends inclusive, even if that means that we must use a negative quotient when dividing a by n. 

Modular Arithmetic - Exponentation 

•To find 117 mod 13, we can proceed as follows:

•112 = 121 º 4 (mod13)
114 = (112)2 º 42 º 3 (mod13)
117 º 11*4*3 º132 º 2(mod13)

 

Properties of Modular Arithmetic

Modulo n arithmetic maps all integers into the set {0, 1, 2, 3, ...., n − 1} 

1.[(a mod n) + (b mod n)] mod n = (a + b) mod n

2.[(a mod n) - (b mod n)] mod n = (a - b) mod n

3.[(a mod n) * (b mod n)] mod n = (a * b) mod n

Proof 1:

•Define (a mod n) = ra and (b mod n) = rb.

•Then we can write a = ra + jn for some integer j and b = rb + kn for some integer k. Then

–(a+b) mod n = (ra + jn + rb + kn) mod n

–(ra + rb + (k+j) n) mod n

–(ra + rb)mod n

–[(a mod n) + (b mod n)] mod n 

 

Cryptography: Number Theory - Pairwise Relatively Prime Numbers

Definition: Pairwise Relatively Prime Integers
The integers a1, a2, …, an are pairwise relatively prime if gcd(ai, aj) = 1 whenever 1 <= i < j <= n.

Examples:
Are 15, 17, and 27 pairwise relatively prime?
No, because gcd(15, 27) = 3.

Are 15, 17, and 28 pairwise relatively prime?
Yes, because gcd(15, 17) = 1, gcd(15, 28) = 1 and gcd(17, 28) = 1.

Cryptography: Number Theory - Euclidean Algorithm

Euclidean Algorithm 

•One of the basic techniques of number theory is the Euclidean algorithm, which is a simple procedure for determining the greatest common divisor of two positive integers.

•Relative Prime

•Two integers are relatively prime if their only common positive integer factor is 1.

Relatively Prime Integers 
Definition:

Two integers a and b are relatively prime if gcd(a, b) = 1.

Examples:

•Are 15 and 28 relatively prime?

–Yes, gcd(15, 28) = 1.

•Are 55 and 28 relatively prime?

–Yes, gcd(55, 28) = 1.

•Are 35 and 28 relatively prime?

–No, gcd(35, 28) = 7.

 

Greatest Common Divisor  

•Let a and b be integers, not both zero.

•The largest integer d such that d | a and d | b is called the greatest common divisor of a and b.

•The greatest common divisor of a and b is denoted by gcd(a, b).

•

•Example 1: What is gcd(48, 72) ?

–The positive common divisors of 48 and 72 are
1, 2, 3, 4, 6, 8, 12, 16, and 24, so gcd(48, 72) = 24.

•Example 2: What is gcd(19, 72) ?

–The only positive common divisor of 19 and 72 is
1, so gcd(19, 72) = 1.

Cryptography: Number Theory - Divisibility

Divisibility 

•If a and b are integers with a ¹ 0, we say that
a divides b if there is an integer c so that b = ac.

•When a divides b we say that a is a factor of b and that b is a multiple of a.

•The notation a | b means that a divides b.

•We say a non-zero integer a is a divisor of another integer b provided the remainder is zero when we divide b by a. That is, when b = ma for some integer m.

•For integers a, b, and c it is true that

•If a|1, then a=±1

•if a | b and b | a, then a=±b

•if a | b and a | c, then a | (b + c)

–Example: 3 | 6 and 3 | 9, so 3 | 15.

•if a | b, then a | bc for all integers c

–Example: 5 | 10, so 5 | 20, 5 | 30, 5 | 40, …

•if a | b and b | c, then a | c

–Example: 4 | 8 and 8 | 24, so 4 | 24.