Week 6 Monday#

Screenshare notes#

Slide 1

Slide 2

Slide 3

Slide 4

Deepnote notebook#

from Lab5_Helper import factor_out_2

n = 294409

  • Let n = 294409. For which values \(2 \leq a < 100\), does \(a\) fail to witness the compositeness of \(n\) using the Fermat primality test?

fermat_failures = [] # list of a's which do not prove compositeness using Fermat
for a in range(2, 100):
    if pow(a, n-1, n) == 1:
        fermat_failures.append(a)

len(fermat_failures)

95

fermat_failures2 = [] # list of a's which do not prove compositeness using Fermat
for a in range(2, 100):
    if pow(a, n, n) == a:
        fermat_failures2.append(a)

len(fermat_failures2)

98

[x for x in fermat_failures2 if x not in fermat_failures]

[37, 73, 74]

n

294409

from math import gcd

# At this point we know definitively that n is composite, since n > 37 and n is divisible by 37.
gcd(37, n)

37

n%37

0

gcd(74, n)

37

gcd(73, n)

73

That was just the first 98 bases, what about all the bases? None of them witness compositeness, but n is a composite number, so n is a Carmichael number.

for a in range(2, n):
    if pow(a, n, n) != a:
        print(a)

  • Let n = 294409. For which values \(2 \leq a < 100\) does \(a\) fail to witness the compositeness of \(n\) using the Miller-Rabin primality test?

A base \(a\) relatively prime to \(n\) can fail to witness compositeness of \(n\) using Miller-Rabin in two ways:

  1. Say \(n = 2^k \cdot q\). We can have \(a^q \equiv 1 \bmod n\).

  2. We can have \(a^{2^i q} \equiv -1 \bmod n\), for some \(0 \leq i \leq k\).

factor_out_2(n-1)

(3, 36801)

(2**3)*36801

294408

mr_failures1 = []
for a in range(2, 100):
    if pow(a, 36801, n) == 1:
        mr_failures1.append(a)

mr_failures1

[16, 75, 81]

None of the bases 16, 75, 81 are Miller-Rabin witnesses of the compositeness of n.

pow(16, 36801, n)

1

pow(16, 2*36801, n) # Square of previous, still 1

1

pow(16, (2**2)*36801, n)

1

# This was checked in the Fermat portion
pow(16, (2**3)*36801, n)

1

16 in fermat_failures

True

(2**3)*36801 == n-1

True

mr_failures2 = []
for a in range(2, 100):
    for i in range(0, 4):
        if pow(a, (2**i)*36801, n) == n-1:
            mr_failures2.append(a)

mr_failures2

[6, 19, 23, 24, 36, 50, 54, 76, 79, 92, 96, 98]

n

294409

pow(23, 36801, n)

205541

# Notice: this is -1 mod n
pow(23, 2*36801, n)

294408

17 not in (mr_failures1 + mr_failures2)

True

# 17 witnesses the compositeness of n using Miller-Rabin
pow(17, 36801, n)

225706

pow(17, 2*36801, n)

137121

pow(17, (2**2)*36801, n)

32265

pow(17, (2**3)*36801, n)

1

# 32265 is a nontrivial square root of unity
pow(32265, 2, n)

1

# 32265^2 = 1^2 mod n
gcd(n, 32265+1)

73

gcd(n, 32265-1)

4033

# Not a prime factorization, because n is not an RSA modulus, so more than 2 prime factors
73*4033

294409

  • What if we replace n with a prime number?

Created in deepnote.com Created in Deepnote