1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
from sympy import FF, symbols
from unittest import TestCase
from pyecsca.ec.mod import Mod, gcd, extgcd, Undefined, miller_rabin, has_gmp, RawMod, SymbolicMod, jacobi
from pyecsca.ec.error import NonInvertibleError, NonResidueError, NonInvertibleWarning, NonResidueWarning
from pyecsca.misc.cfg import getconfig, TemporaryConfig
class ModTests(TestCase):
def test_gcd(self):
self.assertEqual(gcd(15, 20), 5)
self.assertEqual(extgcd(15, 0), (1, 0, 15))
self.assertEqual(extgcd(15, 20), (-1, 1, 5))
def test_jacobi(self):
self.assertEqual(jacobi(5, 1153486465415345646578465454655646543248656451), 1)
self.assertEqual(jacobi(564786456646845, 46874698564153465453246546545456849797895547657), -1)
self.assertEqual(jacobi(564786456646845, 46874698564153465453246546545456849797895), 0)
def test_miller_rabin(self):
self.assertTrue(miller_rabin(2))
self.assertTrue(miller_rabin(3))
self.assertTrue(miller_rabin(5))
self.assertFalse(miller_rabin(8))
self.assertTrue(miller_rabin(0xe807561107ccf8fa82af74fd492543a918ca2e9c13750233a9))
self.assertFalse(miller_rabin(0x6f6889deb08da211927370810f026eb4c17b17755f72ea005))
def test_inverse(self):
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
self.assertEqual(Mod(0x702bdafd3c1c837b23a1cb196ed7f9fadb333c5cfe4a462be32adcd67bfb6ac1, p).inverse(), Mod(0x1cb2e5274bba085c4ca88eede75ae77949e7a410c80368376e97ab22eb590f9d, p))
with self.assertRaises(NonInvertibleError):
Mod(0, p).inverse()
with self.assertRaises(NonInvertibleError):
Mod(5, 10).inverse()
getconfig().ec.no_inverse_action = "warning"
with self.assertRaises(NonInvertibleWarning):
Mod(0, p).inverse()
with self.assertRaises(NonInvertibleWarning):
Mod(5, 10).inverse()
getconfig().ec.no_inverse_action = "ignore"
Mod(0, p).inverse()
Mod(5, 10).inverse()
getconfig().ec.no_inverse_action = "error"
def test_is_residue(self):
self.assertTrue(Mod(4, 11).is_residue())
self.assertFalse(Mod(11, 31).is_residue())
self.assertTrue(Mod(0, 7).is_residue())
self.assertTrue(Mod(1, 2).is_residue())
def test_sqrt(self):
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
self.assertIn(Mod(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc, p).sqrt(), (0x9add512515b70d9ec471151c1dec46625cd18b37bde7ca7fb2c8b31d7033599d, 0x6522aed9ea48f2623b8eeae3e213b99da32e74c9421835804d374ce28fcca662))
with self.assertRaises(NonResidueError):
Mod(0x702bdafd3c1c837b23a1cb196ed7f9fadb333c5cfe4a462be32adcd67bfb6ac1, p).sqrt()
getconfig().ec.non_residue_action = "warning"
with self.assertRaises(NonResidueWarning):
Mod(0x702bdafd3c1c837b23a1cb196ed7f9fadb333c5cfe4a462be32adcd67bfb6ac1, p).sqrt()
getconfig().ec.non_residue_action = "ignore"
Mod(0x702bdafd3c1c837b23a1cb196ed7f9fadb333c5cfe4a462be32adcd67bfb6ac1, p).sqrt()
with TemporaryConfig() as cfg:
cfg.ec.non_residue_action = "warning"
with self.assertRaises(NonResidueWarning):
Mod(0x702bdafd3c1c837b23a1cb196ed7f9fadb333c5cfe4a462be32adcd67bfb6ac1, p).sqrt()
self.assertEqual(Mod(0, p).sqrt(), Mod(0, p))
q = 0x75d44fee9a71841ae8403c0c251fbad
self.assertIn(Mod(0x591e0db18cf1bd81a11b2985a821eb3, q).sqrt(), (0x113b41a1a2b73f636e73be3f9a3716e, 0x64990e4cf7ba44b779cc7dcc8ae8a3f))
getconfig().ec.non_residue_action = "error"
def test_eq(self):
self.assertEqual(Mod(1, 7), 1)
self.assertNotEqual(Mod(1, 7), "1")
self.assertEqual(Mod(1, 7), Mod(1, 7))
self.assertNotEqual(Mod(1, 7), Mod(5, 7))
self.assertNotEqual(Mod(1, 7), Mod(1, 5))
def test_pow(self):
a = Mod(5, 7)
self.assertEqual(a**(-1), a.inverse())
self.assertEqual(a**0, Mod(1, 7))
self.assertEqual(a**(-2), a.inverse()**2)
def test_wrong_mod(self):
a = Mod(5, 7)
b = Mod(4, 11)
with self.assertRaises(ValueError):
a + b
def test_wrong_pow(self):
a = Mod(5, 7)
c = Mod(4, 11)
with self.assertRaises(TypeError):
a**c
def test_other(self):
a = Mod(5, 7)
b = Mod(3, 7)
self.assertEqual(int(-a), 2)
self.assertEqual(str(a), "5")
self.assertEqual(6 - a, Mod(1, 7))
self.assertNotEqual(a, b)
self.assertEqual(a / b, Mod(4, 7))
self.assertEqual(a // b, Mod(4, 7))
self.assertEqual(5 / b, Mod(4, 7))
self.assertEqual(5 // b, Mod(4, 7))
self.assertEqual(a / 3, Mod(4, 7))
self.assertEqual(a // 3, Mod(4, 7))
self.assertEqual(divmod(a, b), (Mod(1, 7), Mod(2, 7)))
self.assertEqual(a + b, Mod(1, 7))
self.assertEqual(5 + b, Mod(1, 7))
self.assertEqual(a + 3, Mod(1, 7))
self.assertNotEqual(a, 6)
self.assertIsNotNone(hash(a))
def test_undefined(self):
u = Undefined()
for k, meth in u.__class__.__dict__.items():
if k in ("__module__", "__new__", "__init__", "__doc__", "__hash__", "__abstractmethods__", "_abc_impl"):
continue
args = [5 for _ in range(meth.__code__.co_argcount - 1)]
if k == "__repr__":
self.assertEqual(meth(u), "Undefined")
elif k in ("__eq__", "__ne__"):
assert not meth(u, *args)
else:
with self.assertRaises(NotImplementedError):
meth(u, *args)
def test_implementation(self):
if not has_gmp:
self.skipTest("Only makes sense if more Mod implementations are available.")
with TemporaryConfig() as cfg:
cfg.ec.mod_implementation = "python"
self.assertIsInstance(Mod(5, 7), RawMod)
def test_symbolic(self):
x, y = symbols("x y")
p = 13
k = FF(p)
sx = SymbolicMod(x, p)
a = k(3)
b = k(5)
r = sx * a + b
self.assertIsInstance(r, SymbolicMod)
self.assertEqual(r.n, p)
sa = SymbolicMod(a, p)
sb = SymbolicMod(b, p)
self.assertEqual(sa, 3)
self.assertEqual(sa.inverse(), SymbolicMod(k(9), p))
self.assertEqual(1 / sa, SymbolicMod(k(9), p))
self.assertEqual(sa + sb, 8)
self.assertEqual(1 + sa, 4)
self.assertEqual(sa - 1, 2)
self.assertEqual(1 - sa, 11)
self.assertEqual(sa + 1, 4)
self.assertEqual(-sa, 10)
self.assertEqual(sa / 2, 8)
self.assertEqual(2 / sa, 5)
self.assertEqual(sa // 2, 8)
self.assertEqual(2 // sa, 5)
self.assertEqual(int(sa), 3)
self.assertNotEqual(sa, sb)
self.assertIsNotNone(hash(sa))
|
