Introduction to Cryptography Chapter 7

Here we define gcd and fast exponentiation as functions:

def gcd(x, y):
    if y == 0: return x
    return gcd(y, x % y)

def power(a, d, n):
    l = []
    cur = d
    while cur != 0:
        l.append(cur % 2)
        cur = cur // 2
    
    r = []
    cur = a % n
    for i in range(len(l)):
        r.append(cur)
        cur = (cur ** 2) % n
    
    ans = 1
    for i in range(len(l)):
        if l[i] == 0: continue
        ans = (ans * r[i]) % n
    
    return ans

Exercise 7.6.1

Find $a \in {\mathbb Z}$ that satisfies:

${\rm gcd}(a, n) = 1 \quad$

$a^{n-1} \not\equiv 1 {\quad}{\rm mod} {\hspace{1mm}}n$

n = 1111
for a in range(2, n):
    if gcd(a, n) != 1: continue
    if power(a, n-1, n) == 1: continue

    print(a)
    break

Result

Exercise 7.6.2

$\pi(x)$ denotes the number of primes which are less than or equal to $x$ . Use Sieve of Eratosthenes.

n = 100
l = list(range(2, n+1))

for p in range(2, n+1):
    l = [i for i in l if i == p or i % p != 0]

print(f'{len(l)}')

Result

Exercise 7.6.3

A pseudoprime to the base $a$ is an odd composite number which satisfies:

$a^{n-1} \equiv 1 {\quad}{\rm mod} {\hspace{1mm}}n$

To check whether a certain number is prime or composite, Sieve of Eratosthenes is used.

max_n = 500
primes = list(range(2, max_n+1))
for p in range(2, max_n+1):
    primes = [i for i in primes if i == p or i % p != 0]

a = 2
for n in range(2, max_n):
    if n in primes: continue
    if power(a, n-1, n) != 1: continue
    
    print(n)
    break

Result

Exercise 7.6.4

find $a \in {\mathbb Z}$ that satisfies:

${\rm gcd}(a, n) = 1 \quad$

$a^{n-1} \not\equiv 1 {\quad}{\rm mod} {\hspace{1mm}}n$

n = 2 ** (2 ** 5) + 1
for a in range(2, n):
    if gcd(a, n) != 1: continue
    if power(a, n-1, n) == 1: continue

    print(a)
    break

Result

Note: $F_{5} = 641 \times 6700417$

Exercise 7.6.6

Introduce $2^{s}$ as the largest power of 2 which divides $n - 1$ . Then we can define $d = (n - 1)/2^{s}$ .

Find $a \in {\mathbb Z}$ that satisfies:

${\rm gcd}(a, n) = 1 \quad$

$a^{d} \not\equiv 1 {\quad}{\rm mod} {\hspace{1mm}}n$

$a^{2^{r}d} \not\equiv -1 {\quad}{\rm mod} {\hspace{1mm}}n$

where $\forall r \in (0, 1, ..., s-1)$

n = 2 ** (2 ** 5) + 1
d = n - 1
s = 0
while d % 2 == 0:
    d = d // 2
    s = s + 1

for a in range(2, n):
    if gcd(a, n) != 1: continue
    if power(a, d, n) == 1: continue

    flag = True
    for r in range(s):
        flag = flag and power(a, d*(2**r), n) != n - 1
    if not flag: continue

    print(a)
    break

Result

Exercise 7.6.7

The pseudoprime is $n = 341$ . Substitute 341 for $n$ in the above code, instead of $2^{2^{5}} + 1$ .

Result

Exercise 7.6.8

Slightly changed.

n = 221
d = n - 1
s = 0
while d % 2 == 0:
    d = d // 2
    s = s + 1

l = []
for a in range(2, n):
    if gcd(a, n) != 1: continue
    if power(a, d, n) == 1: continue

    # condition 2
    flag = True
    for r in range(s):
        flag = flag and power(a, d*(2**r), n) != n - 1
    
    if flag: l.append(a)

print(len(l))

Result