Algorithm-1:Algorithms with numbers

Notes from the algorithms course: modular arithmetic, primality testing, cryptography (RSA), and hashing.

Textbook:
Algorithms (Umesh Vazirani, Christos H. Papadimitriou )

The mind map was generated by Doubao

Big O notation

Chapter1: Algorithms with numbers

Multiplication and division

$x \cdot y=\left\{\begin{array}{cl} 2(x \cdot\lfloor y / 2\rfloor) & if y is even \\ x+2(x \cdot\lfloor y / 2\rfloor) & if y is odd. \end{array}\right.$

Div:

if x = 0: return (q, r) = (0, 0)
(q, r) = divide(⌊x/2⌋, y) 
q = 2 · q, r = 2 · r 
if x is odd: r = r + 1
if r ≥ y: r = r − y, q = q + 1
return (q, r)

Modular arithmetic

$2^{345} \equiv\left(2^{5}\right)^{69} \equiv 32^{69} \equiv 1^{69} \equiv 1 \quad(mod 31) .$ $x^y= \begin{cases}\left(x^{\lfloor y / 2\rfloor}\right)^{2} & if y is even \\ x \cdot\left(x^{\lfloor y / 2\rfloor}\right)^{2} & if y is odd. \end{cases}$

The algorithm will halt after at most n recursive calls, and during each call it multiplies n -bit numbers, for a total running time of

Extended Euclid algorithm

Eculid:

Euclid(a, b)
// Input: two integers a and b with a ≥b ≥0 
// Output: gcd(a, b)
1. if b = 0 then return a
2. return Euclid(b, a mod b)

The correctness is by mod y , y ) for all
The running time is

Extended Euclid:

ExtendedEuclid(a, b)
// Input: two integers a and b with a ≥b ≥0
// Output: integers x, y, d such that d = gcd(a, b) and ax + by = d
1. if b = 0 then return (1, 0, a)
2. (x', y', d) = ExtendedEuclid(b, a mod b)
3. (x, y) = (y', x' − ⌊a/b⌋y')
4. return (x, y, d)

The correctness is by mod y , y ) for all
The running time is

Modular inverse

We say x is the multiplicative inverse of a modulo N if $a x \equiv 1 \ (\text{mod}\ N)$

The inverse does not necessarily exist, and when it does there is at most one.

Theorem (Modular Division Theorem):

For any a mod N ,a has a multiplicative inverse modulo N if and only if it is relatively prime to N (i.e.. ).

Primality testing

Fermat’s little theorem

$a^{p-1} \equiv 1 \quad(mod \quad p)$

proof:

Construct the set of nonzero integers modulo p, $S = {1, 2, \cdots, p - 1}$ . When every element of S is multiplied by a (mod p), the resulting set is the same as the original set S, only with the elements in a different order (i.e., these numbers are a permutation of S). Based on this, multiplying together the elements of each of the two sets gives $(p - 1)! \equiv a^{p - 1} \cdot (p - 1)! \ (\text{mod}\ p)$ . Since (p - 1)! is coprime to p (because p is prime), dividing both sides by (p - 1)! yields $a^{p - 1} \equiv 1 \ (\text{mod}\ p)$ .

Limitations:

The converse of Fermat’s little theorem does not hold: if $a^p \equiv a \ (\text{mod}\ p)$ , then p is not necessarily prime.
$2^{340} \equiv 1 \ (\text{mod}\ 341)$ , but $341=11\times31$ is composite.

Carmichael numbers:

There are composite numbers N such that for every (a<N) relatively prime to N (Carmichael numbers are composite),

$a^{N-1} \equiv 1(mod N) .$

Example: 561 = 3 · 11 · 17

An algorithm for testing primality with low error probability:

primality2(N)
// Input: positive integer N
// Output: yes/no

1. Pick positive integers a1, a2, . . . , ak < N at random
2. if $a_{i}^{N-1}$ ≡ 1 (mod N) for all i = 1, 2, . . . , k then return yes
3. else return no.

Pr(primality2 returns yes when N is prime) = 1
Pr(primality2 returns yes when N is not prime) ≤ .

If the randomly chosen N is truly prime, which happens with probability at least 1/n, then it will certainly pass the test. So on each iteration, this procedure has at least a 1/n chance of halting. Therefore on average it will halt within O(n) rounds.

Cryptography

RSA

The steps of the RSA encryption algorithm are as follows:

Key generation
- Choose two large primes p and q
- Compute n = p × q
- Compute φ(n) = (p-1)(q-1)
- Choose an integer e coprime to φ(n) as the public key
- Compute the private key d such that d × e ≡ 1 (mod φ(n))
Encryption
- Public key: (n, e)
- Plaintext message m
- Encryption: c =
Decryption
- Private key: (n, d)
- Ciphertext c
- Decryption: m =

Example:

# 一个简单的RSA实现示例
p = 61
q = 53
n = p * q                     # n = 3233
φn = (p-1) * (q-1)           # φn = 3120
e = 17                       # 选择e与φn互质
# 计算d: 17d ≡ 1 (mod 3120)
d = 2753                     # 私钥

# 加密消息m = 123
c = 123^{17} mod 3233 = 855    # 密文

# 解密
m = 855^{2753} mod 3233 = 123  # 恢复明文

Proof:

If x → mod N is invertible, it must be a bijection; hence (2) implies (1).
To (2), we first observe that e is invertible module (p − 1)(q − 1) because it is relatively prime to this number. It remains to show:

$(x^e )^d ≡ x \ (\text{mod}\ N).$

Since ed ≡ 1 mod (p − 1)(q − 1), we can write ed = 1 + k(p − 1)(q − 1)

is divisible by p,

since and likewise by q.

Since p and q are primes, this expression must be divisible by N = pq.

Hashing

example: IP address

We can define a function h from IP addresses to a number mod n as follows:

Fix any four numbers mod (n=257) , say 87, 23, 125, and 4.

Now map the IP address $(x_{1}, ..., x_{4})$ to $h(x_{1}, ..., x_{4}) = (87 x_{1}+23 x_{2}+125 x_{3}+4 x_{4})$ mod 257.

In general for any $a=(a_{1}, a_{2}, a_{3}, a_{4}) \in(0,1, ..., n-1)^{4}$ and define

$h_{a}\left(x_{1}, ..., x_{4}\right)=\left(a_{1} \cdot x_{1}+a_{2} \cdot x_{2}+a_{3} \cdot x_{3}+a_{4} \cdot x_{4}\right) mod n .$

Consider any pair of distinct IP addresses $x=(x_{1}, ..., x_{4})$ and $y=(y_{1}, ..., y_{4})$ . If the coefficients $a=(a_{1}, ..., a_{4})$ are chosen uniformly at random from $0,1, ..., n-1$ , then

$Pr\left[h_{a}\left(x_{1}, ..., x_{4}\right)=h_{a}\left(y_{1}, ..., y_{4}\right)\right]=\frac{1}{n} .$

Translated from the Chinese original.