Week 5 Monday#
Screenshare notes#
Deepnote notebook#
from sympy import nextprime, isprime, factorint
The Fermat Primality Test#
(And why it’s inadequate.)
n = 5459
a = 2
pow(a, n-1, n) # Much better than pow(a, n-1)%n
517
Because 517 is not 1 mod n, this proves definitively that 5459 is composite. a=2 is a witness to the compositeness of 5459.
# We don't see any zeros, so this wasn't enough divisions to prove compositeness.
for a in range(2, 50):
print(a, n%a)
2 1
3 2
4 3
5 4
6 5
7 6
8 3
9 5
10 9
11 3
12 11
13 12
14 13
15 14
16 3
17 2
18 5
19 6
20 19
21 20
22 3
23 8
24 11
25 9
26 25
27 5
28 27
29 7
30 29
31 3
32 19
33 14
34 19
35 34
36 23
37 20
38 25
39 38
40 19
41 6
42 41
43 41
44 3
45 14
46 31
47 7
48 35
49 20
n1 = nextprime(5000)
n1
5003
pow(2, n1-1, n1)
1
pow(3, n1-1, n1)
1
for j in range(2, 150):
print(j, pow(j, n1, n1))
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
52 52
53 53
54 54
55 55
56 56
57 57
58 58
59 59
60 60
61 61
62 62
63 63
64 64
65 65
66 66
67 67
68 68
69 69
70 70
71 71
72 72
73 73
74 74
75 75
76 76
77 77
78 78
79 79
80 80
81 81
82 82
83 83
84 84
85 85
86 86
87 87
88 88
89 89
90 90
91 91
92 92
93 93
94 94
95 95
96 96
97 97
98 98
99 99
100 100
101 101
102 102
103 103
104 104
105 105
106 106
107 107
108 108
109 109
110 110
111 111
112 112
113 113
114 114
115 115
116 116
117 117
118 118
119 119
120 120
121 121
122 122
123 123
124 124
125 125
126 126
127 127
128 128
129 129
130 130
131 131
132 132
133 133
134 134
135 135
136 136
137 137
138 138
139 139
140 140
141 141
142 142
143 143
144 144
145 145
146 146
147 147
148 148
149 149
Don’t use the phrase “witness” in this context, we only use “witness” when something is proven. These results don’t prove that n1 is prime.
10 minute break until 10:10am#
# Back to n
n
5459
# Proved n was composite
pow(2, n-1, n)
517
Notice: we proved n was composite without finding a prime divisor (or any nontrivial divisor) of n. Your intuition should be that proving a number is composite is much easier (much faster, can be done much more efficiently) than finding a nontrivial divisor.
Think:
gcd and modular exponentiation (
pow(a,b,c)) are very fastprimality testing is pretty fast, but not as fast as gcd and fast powering
Factoring and discrete logs are very slow to compute
Major flaw with the Fermat primality test#
n2 = 340561
pow(2, n2-1, n2)
1
pow(3, n2-1, n2)
1
for j in range(2, 13):
print(j, pow(j, n2-1, n2))
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
# Notice a^(p-1) = 1 mod p, also have a^p = a mod p (this second one, no constraints on a), when p is prime
# these results scream "prime"
for j in range(2, 150):
print(j, pow(j, n2, n2))
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
52 52
53 53
54 54
55 55
56 56
57 57
58 58
59 59
60 60
61 61
62 62
63 63
64 64
65 65
66 66
67 67
68 68
69 69
70 70
71 71
72 72
73 73
74 74
75 75
76 76
77 77
78 78
79 79
80 80
81 81
82 82
83 83
84 84
85 85
86 86
87 87
88 88
89 89
90 90
91 91
92 92
93 93
94 94
95 95
96 96
97 97
98 98
99 99
100 100
101 101
102 102
103 103
104 104
105 105
106 106
107 107
108 108
109 109
110 110
111 111
112 112
113 113
114 114
115 115
116 116
117 117
118 118
119 119
120 120
121 121
122 122
123 123
124 124
125 125
126 126
127 127
128 128
129 129
130 130
131 131
132 132
133 133
134 134
135 135
136 136
137 137
138 138
139 139
140 140
141 141
142 142
143 143
144 144
145 145
146 146
147 147
148 148
149 149
# Let's use `isprime` from sympy to confirm that n2 is indeed prime
isprime(n2)
False
n2
340561
factorint(n2)
{13: 1, 17: 1, 23: 1, 67: 1}
13*17*23*67
340561
Major flaw with the Fermat primality test: there exist composite numbers n, called Carmichael numbers, such that the only values of a which witness the compositeness of n are values of a such that gcd(a,n) > 1
pow(13, n2-1, n2)
157183
Finding a Fermat witness for a Carmichael number is no easier than finding a nontrivial divisor of that Carmichael number.
The smallest Carmichael number is 561. It has been proved there are infinitely many Carmichael numbers.
for j in range(2, 150):
print(j, pow(j, n2-1, n2))
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 157183
14 1
15 1
16 1
17 240397
18 1
19 1
20 1
21 1
22 1
23 207299
24 1
25 1
26 157183
27 1
28 1
29 1
30 1
31 1
32 1
33 1
34 240397
35 1
36 1
37 1
38 1
39 157183
40 1
41 1
42 1
43 1
44 1
45 1
46 207299
47 1
48 1
49 1
50 1
51 240397
52 157183
53 1
54 1
55 1
56 1
57 1
58 1
59 1
60 1
61 1
62 1
63 1
64 1
65 157183
66 1
67 76246
68 240397
69 207299
70 1
71 1
72 1
73 1
74 1
75 1
76 1
77 1
78 157183
79 1
80 1
81 1
82 1
83 1
84 1
85 240397
86 1
87 1
88 1
89 1
90 1
91 157183
92 207299
93 1
94 1
95 1
96 1
97 1
98 1
99 1
100 1
101 1
102 240397
103 1
104 157183
105 1
106 1
107 1
108 1
109 1
110 1
111 1
112 1
113 1
114 1
115 207299
116 1
117 157183
118 1
119 240397
120 1
121 1
122 1
123 1
124 1
125 1
126 1
127 1
128 1
129 1
130 157183
131 1
132 1
133 1
134 76246
135 1
136 240397
137 1
138 207299
139 1
140 1
141 1
142 1
143 157183
144 1
145 1
146 1
147 1
148 1
149 1
for j in range(2, 150):
print(j, n2%j)
2 1
3 1
4 1
5 1
6 1
7 4
8 1
9 1
10 1
11 1
12 1
13 0
14 11
15 1
16 1
17 0
18 1
19 5
20 1
21 4
22 1
23 0
24 1
25 11
26 13
27 10
28 25
29 14
30 1
31 26
32 17
33 1
34 17
35 11
36 1
37 13
38 5
39 13
40 1
41 15
42 25
43 1
44 1
45 1
46 23
47 46
48 1
49 11
50 11
51 34
52 13
53 36
54 37
55 1
56 25
57 43
58 43
59 13
60 1
61 59
62 57
63 46
64 17
65 26
66 1
67 0
68 17
69 46
70 11
71 45
72 1
73 16
74 13
75 61
76 5
77 67
78 13
79 71
80 1
81 37
82 15
83 12
84 25
85 51
86 1
87 43
88 1
89 47
90 1
91 39
92 69
93 88
94 93
95 81
96 49
97 91
98 11
99 1
100 61
101 90
102 85
103 43
104 65
105 46
106 89
107 87
108 37
109 45
110 1
111 13
112 81
113 92
114 43
115 46
116 101
117 91
118 13
119 102
120 1
121 67
122 59
123 97
124 57
125 61
126 109
127 74
128 81
129 1
130 91
131 92
132 1
133 81
134 67
135 91
136 17
137 116
138 115
139 11
140 81
141 46
142 45
143 78
144 1
145 101
146 89
147 109
148 13
149 96
The Miller-Rabin Primality Test#
# Carmichael number
n = 340561
a = 2
pow(a, n-1, n)
1
n-1
340560
pow(a, (n-1)/2, n)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
Cell In [31], line 1
----> 1 pow(a, (n-1)/2, n)
TypeError: pow() 3rd argument not allowed unless all arguments are integers
type((n-1)/2)
float
(n-1)/2
170280.0
(n-1)%2
0
# Forces the output to be an integer
# Only use this `//` if you know the number is divisible
(n-1)//2
170280
pow(a, (n-1)//2, n)
1
pow(a, (n-1)//4, n)
140232
n
340561
pow(140232, 2, n)
1
\(140232^2 \equiv 1 \bmod n\) So we have \((140232^2 - 1^2) \equiv 0 \bmod n\) So \(n\) divides \((140232 - 1)(140232 + 1)\)
from math import gcd
gcd(n, 140232 - 1)
20033
n%20033
0
n
340561
Our very first choice of a, a = 2, was a witness to the compositeness of n.
Created in Deepnote