Number Theory (Part C)
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
February 09, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 4c MdH W22 February 09, 2022 1 / 14
1 Solving Congruence
2 Applications of Congruences
3 Introduction to Cryptography
Md. Hasan (uOttawa) Discrete Structures 4c MdH W22 February 09, 2022 2 / 14
The Chinese Remainder Theorem (CRT)
Background: Sun-Tsu’s Puzzle
Solve for x when it satisfies the following congruences.
x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).
Md. Hasan (uOttawa) Discrete Structures 4c MdH W22 February 09, 2022 3 / 14
The CRT (cont.)
Let m1, m2, …, mn be pairwise relatively prime positive integers greater
than one and a1, a2, …, an arbitrary integers. Then the system
x ≡ a1 (mod m1), x ≡ a2 (mod m2), .
x ≡ an (mod mn)
has a unique solution modulo m = m1m2…mn. (That is there is a solution x with 0 ≤ x < m, and all other solutions are congruent modulo m to this solution.)
Md. Hasan (uOttawa) Discrete Structures 4c MdH W22 February 09, 2022 4 / 14
The CRT (cont.)
To establish the CRT, we need to show that a solution exists and it is
unique modulo m.
Let, Mk = m/mk for k = 1,2,...,n. That is, Mk is the product of the moduli except for mk . As m1, m2, ..., mn are pairwise relatively prime, it follows that gcd(mk , Mk ) = 1. There is an integer yk , an inverse of Mk modulo mk, such that Mkyk ≡ 1 (mod mk).
To construct a simultaneous solution, we form the sum
x = a1M1y1 + a2M2y2 + ... + anMnyn.
All terms except the kth term in this sum are congruent to 0 modulo mk. Thus, x ≡ akMkyk ≡ ak (mod mk), for k = 1,2,...,n. It is shown that x is a simultaneous solution to the n congruences.
x = (nk=1 akMkyk) mod m.
Md. Hasan (uOttawa) Discrete Structures 4c MdH W22 February 09, 2022 5 / 14
The CRT (cont.)
Solution to Sun-Tsu’s Puzzle
We get m = 3 · 5 · 7 = 105,
M1 =m/3=35,M2 =m/5=21,andM3 =m/7=15. Theinversesare,y1 =2,y2 =1,andy3 =1.
(Obtained by using the inverse property, b ̄b ≡ 1 (mod d).)
Thus, x = (2 · 35 · 2 + 3 · 21 · 1 + 2 · 15 · 1) mod 105 = 23 (mod 105).
Notes: (i) Here 23 is the smallest positive integer that is a simultaneous solution.
(ii) This kind of problems can also be solved using the back substitution method.
Md. Hasan (uOttawa) Discrete Structures 4c MdH W22 February 09, 2022 6 / 14
Fermat’s Little Theorem
Fermat’s Little Theorem
If p is prime and a is an integer not divisible by p, then ap−1 ≡ 1 (mod p).
Furthermore, for every integer a we have
ap ≡ a (mod p).
Exercise
Find 231002 mod 41.
Md. Hasan (uOttawa) Discrete Structures 4c MdH W22 February 09, 2022 7 / 14
Pseudoprimes and Primitive Roots
Pseudoprimes
Let b be a positive integer. If n is a composite positive integer, and
bn−1 ≡ 1 (mod n), then n is called a pseudoprime to the base b. Primitive Roots
A primitive root modulo prime p is an integer r in Zp such that every nonzero element of Zp is a power of r.
Discrete Logarithms
Suppose that p is a prime, r is a primitive root modulo p, and a is an integer between 1 and p − 1 inclusive. If re mod p = a and
0 ≤ e ≤ p − 1, we say that e is the discrete logarithm of a modulo p to the base r and we write logr a = e (where the prime p is understood).
Md. Hasan (uOttawa) Discrete Structures 4c MdH W22 February 09, 2022 8 / 14
Applications of Congruences
Hashing Functions
A hashing function h assigns memory location h(k) to the record that has
k as its key.
– Assigns memory locations to computer files.
– A common hashing function is h(k) = k mod m, where m is the number of memory locations.
– As this hashing function is onto, all memory locations are possible. – If there is a collision, next available location is assigned.
Md. Hasan (uOttawa) Discrete Structures 4c MdH W22 February 09, 2022 9 / 14
Applications of Congruences (cont.)
Pseudorandom Numbers
The linear congruential method is one commonly used procedure for generating pseudorandom numbers. Four integers are needed: the modulus m, the multiplier a, the increment c, and seed x0, with 2≤a