IMPORTANT NOTES OF NUMBER THEORY AND CRYPTOGRAPHY(ROSEN DISCRETE MATHEMATICS)

•   If a and b are integers with a !=0, we say that a divides b if there is an integer c such that b = ac, or equivalently, if b a is an integer. When a divides b we say that a is a factor or divisor of b, and that b is a multiple of a. The notation a | b denotes that a divides b. We write a!| b when a does not divide b.

•  Let a, b, and c be integers, where a !=0. Then (i) if a | b and a | c, then a | (b+c); (ii) if a | b, then a | bc for all integers c; (iii) if a | b and b | c, then a | c.

• THE DIVISIONALGORITHM Let a be an integer and d a positive integer. Then there are unique integers q and r, with 0≤ r<d, such that a = dq+r.

• in the division algorithm, d is called the divisor, a is called the dividend, q is called the quotient, and r is called the remainder. This notation is used to express the quotient and remainder: q = a div d, r = a mod d.

•  If a and b are integers and m is a positive integer, then 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. We say that a ≡ b (mod m) is a congruence and that m is its modulus (plural moduli). If a and b are not congruent modulo m, we write a !≡ b (mod m).

•  Let a and b be integers, and let m be a positive integer. Then a ≡ b (mod m) if and only if            a mod m = b mod m.
•  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 + k m.
•  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).
•  Let m be a positive integer and let a and b be integers. Then (a+b) mod m = ((a mod m)+(b mod m))mod m and ab mod m = ((a mod m)(b mod m))mod m.

• ALGORITHM 5 Modular Exponentiation.

 procedure modular exponentiation

(b: integer, n = (ak−1ak−2 ...a1a0)2, m: positive integers) 

x :=1 

power := b mod m

 for i :=0 to k−1 

if ai =1 then x := (x·power) mod m 

power :=(power ·power) mod m

return x{x equals bn mod m}

•  An integer p greater than 1 is called prime if the only positive factors of p are 1 and p. A positive integer that is greater than 1 and is not prime is called composite.
•  If n is a composite integer, then n has a prime divisor less than or equal to √n.
•  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).
•  The integers a and b are relatively prime if their greatest common divisor is 1.
•  Let a = bq+r, where a,b,q, and r are integers. Then gcd(a,b) =gcd(b,r).
• ALGORITHM 1 The Euclidean Algorithm.
• procedure gcd(a,b: positive integers) x := a y := b 

                while y !=0 

                r := x mod y     

                x := y y := r      

                return x{gcd(a,b) is x}

•  BÉZOUT’STHEOREM  If a and b are positive integers, then there exist integers s and t such that gcd(a,b)= sa+tb.

•  If a, b, and c are positive integers such that gcd(a,b) =1 and a | bc, then a | c.
• Let m be a positive integer and let a, b, and c be integers. If ac≡ bc (mod m) and gcd(c,m) = 1, then a ≡ b(mod m).
• A congruence of the format  ax ≡ b(mod m), where m is a positive integer, a and b are integers, and x is a variable, is called a linear congruence. 
•  If a and m are relatively prime integers and m>1, then an inverse of a modulo m exists. Furthermore, this inverse is unique modulo m. (That is, there is a unique positive integer a less than m that is an inverse of a modulo m and every other inverse of a modulo m is congruent to a modulo m.)
• THE CHINESE REMAINDERTHEOREM 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.)
• • FERMAT’S LITTLE THEOREM If p is prime and a is an integer not divisible by p, then a^(p−1 )≡1 (mod p). Furthermore, for every integer a we have a^p ≡ a(mod p).
•  Let b be a positive integer. If n is a composite positive integer, and b^(n−1 )≡1 (mod n), then n is called a pseudoprime to the base b.
• The process of recovering plaintext from ciphertext without knowledge of both the encryption method and the key is known as cryptanalysis or breaking codes