Please enable JavaScript.
Coggle requires JavaScript to display documents.
Number Theory and Cryptography (Divisibility and Modular Arithmetic…
Number Theory and Cryptography
Divisibility and Modular Arithmetic
Division
Definition
a divides b when there is an integer c such as b= ac, a≠0
a | b means a divides b.
a ∤ b means a not divides b.
Theorems
a ∣ b & a ∣ c ⇒ a ∣ (b+c)
a ∣ b ⇒ a ∣ bc for all integers c
a ∣ b & b ∣ c ⇒ a ∣ c.
Division Logarithm
Definition
a = bq+r, b>0
Where a is dividend, b is divider, q is quotient, and r is remainder.
q = a
div
b
r = a
mod
b
Modular Arithmetic
Definition
Let a, b ∈ Z, m ∈ Positive Integer ⇒ a ≡ b (
mod
m)
if m | a - b
Theorems
Let a, b ∈ Z, m ∈ Positive Integer,
a ≡ b(
mod
m) ⇔ a
mod
m = b
mod
m
Let m ∈ Positive Integer,
a ≡ b(
mod
m) ⇔ a = b + km, k ∈ Z
Let m ∈ Positive Integer,
a ≡ b(
mod
m) ^ c ≡ d(
mod
m)⇔ a = b + km, k ∈ Z
Arithmetic Modulo
m
Zm is the set of nonnegative integers less than m
a + mb = (a+b)mod m
a - mb = (a-b)mod m
Integer Representation and algorithm
Representations of Integers
n = akb^k + ak−1b^k−1 + ⋯ + a1b + a0,
Algorithms for Integer Operations
Addition
a + b = (sn sn−1 sn−2 … s1 s0)2
Multiplication
ab = a(b02^0 + b12^1 + ⋯ + bn−1x2^n−1)
= a(b02^0) + a(b12^1) + ⋯ + a(bn−1x2^n−1)
Modular Exponentiation
bn = b^(ak−1⋅2^k−1+⋯+a1⋅2+a0) = b^(ak−1⋅2k−)
⋯ b(a1⋅2) ⋅ (ba0) .