Commit | Line | Data |
---|---|---|
553d59fe MW |
1 | ### -*-python-*- |
2 | ### | |
3 | ### Testing multiprecision integer (and related) functionality | |
4 | ### | |
5 | ### (c) 2019 Straylight/Edgeware | |
6 | ### | |
7 | ||
8 | ###----- Licensing notice --------------------------------------------------- | |
9 | ### | |
10 | ### This file is part of the Python interface to Catacomb. | |
11 | ### | |
12 | ### Catacomb/Python is free software: you can redistribute it and/or | |
13 | ### modify it under the terms of the GNU General Public License as | |
14 | ### published by the Free Software Foundation; either version 2 of the | |
15 | ### License, or (at your option) any later version. | |
16 | ### | |
17 | ### Catacomb/Python is distributed in the hope that it will be useful, but | |
18 | ### WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
20 | ### General Public License for more details. | |
21 | ### | |
22 | ### You should have received a copy of the GNU General Public License | |
23 | ### along with Catacomb/Python. If not, write to the Free Software | |
24 | ### Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
25 | ### USA. | |
26 | ||
27 | ###-------------------------------------------------------------------------- | |
28 | ### Imported modules. | |
29 | ||
30 | import catacomb as C | |
31 | import unittest as U | |
32 | import testutils as T | |
33 | ||
34 | ###-------------------------------------------------------------------------- | |
35 | class TestMP (U.TestCase): | |
36 | ||
37 | def test_make(me): | |
38 | x = C.MP(5) | |
39 | k = C.PrimeField(17) | |
40 | kk = C.BinPolyField(C.GF(0x13)) | |
41 | E = k.ec(-3, 1) | |
42 | me.assertEqual(x, 5) | |
43 | me.assertTrue(C.MP(x) is x) | |
44 | me.assertEqual(C.MP(k(8)), 8) | |
45 | me.assertEqual(C.MP(kk(8)), 8) | |
46 | me.assertEqual(C.MP(E(1, 4)), 1) | |
47 | me.assertRaises(TypeError, C.MP, E()) | |
48 | ||
49 | me.assertEqual(int(x), 5) | |
50 | big = 6556380541834372447694561492436749633 | |
51 | me.assertEqual(type(big), T.long) | |
52 | y = C.MP(big) | |
53 | me.assertEqual(y, big) | |
54 | me.assertEqual(int(y), big) | |
55 | ||
56 | me.assertEqual(C.MP(str(big)), big) | |
57 | me.assertEqual(C.MP('0x4eeb684a0954ec4ceb255e3e9778d41'), big) | |
58 | me.assertEqual(C.MP('4eeb684a0954ec4ceb255e3e9778d41', 16), big) | |
59 | me.assertEqual(C.MP('0b0', 16), 176) # not 0 | |
60 | ||
61 | me.assertEqual(C.MP('047353320450112516611472622536175135706501'), big) | |
62 | me.assertEqual(C.MP('0o47353320450112516611472622536175135706501'), big) | |
63 | me.assertEqual(C.MP('047353320450112516611472622536175135706501', 8), big) | |
64 | me.assertEqual(C.MP('47353320450112516611472622536175135706501', 8), big) | |
65 | ||
66 | me.assertEqual(C.MP('0b100111011011001100000010001011'), 661438603) | |
67 | me.assertEqual(C.MP('100111011011001100000010001011', 2), 661438603) | |
68 | ||
69 | def test_string(me): | |
70 | y = C.MP(6556380541834372447694561492436749633) | |
71 | me.assertEqual(str(y), '6556380541834372447694561492436749633') | |
e38168e2 | 72 | me.assertEqual(repr(y), 'MP(6556380541834372447694561492436749633)') |
553d59fe | 73 | me.assertEqual(hex(y), '0x4eeb684a0954ec4ceb255e3e9778d41') |
f7623015 MW |
74 | me.assertEqual(oct(y), T.py23('0', '0o') + |
75 | '47353320450112516611472622536175135706501') | |
a90a9c0e MW |
76 | try: bin |
77 | except NameError: pass | |
78 | else: me.assertEqual(bin(C.MP(661438603)), | |
79 | '0b100111011011001100000010001011') | |
553d59fe MW |
80 | |
81 | def test_number(me): | |
82 | x, y, m, zero = C.MP(169), C.MP(24), C.MP(205), C.MP(0) | |
83 | ||
84 | me.assertEqual(-x, -169) | |
85 | me.assertEqual(~x, -170) | |
86 | me.assertEqual(abs(x), 169) | |
87 | me.assertEqual(abs(-x), 169) | |
88 | ||
89 | me.assertEqual(x + y, 193) | |
90 | me.assertEqual(x - y, 145) | |
91 | me.assertEqual(x*y, 4056) | |
92 | me.assertEqual(x&y, 8) | |
93 | me.assertEqual(x&-y, 168) | |
94 | me.assertEqual(x | y, 185) | |
95 | me.assertEqual(x | -y, -23) | |
96 | me.assertEqual(x ^ y, 177) | |
97 | me.assertEqual(x ^ -y, -191) | |
98 | ||
99 | me.assertEqual(x << 3, 1352) | |
100 | me.assertEqual(x << -2, 42) | |
101 | me.assertEqual(x >> 2, 42) | |
102 | me.assertEqual(x >> -3, 1352) | |
103 | me.assertEqual(-x << 3, -1352) | |
104 | me.assertEqual(-x >> 2, -43) | |
105 | ||
106 | u = x/y; me.assertEqual((u.numer, u.denom), (169, 24)) | |
107 | me.assertEqual(x//y, 7) | |
108 | me.assertEqual(x%y, 1) | |
109 | me.assertEqual(divmod(x, y), (7, 1)) | |
110 | me.assertRaises(ZeroDivisionError, lambda: x/zero) | |
111 | me.assertRaises(ZeroDivisionError, lambda: x//zero) | |
112 | me.assertRaises(ZeroDivisionError, lambda: x%zero) | |
113 | me.assertRaises(ZeroDivisionError, divmod, x, zero) | |
114 | ||
115 | me.assertEqual(pow(x, y), 294632676319010105335586872991323185304149065116720321) | |
116 | me.assertEqual(pow(x, y, m), 51) | |
117 | me.assertRaises(ValueError, pow, x, -y) | |
118 | me.assertEqual(pow(x, -y, m), 201) | |
119 | me.assertRaises(ZeroDivisionError, pow, x, -y, 208) | |
120 | ||
121 | me.assertTrue(x) | |
122 | me.assertFalse(zero) | |
123 | ||
124 | def test_order(me): | |
125 | x, y = C.MP(169), C.MP(24) | |
126 | me.assertTrue(x == x) | |
127 | me.assertFalse(x != x) | |
128 | me.assertFalse(x == y) | |
129 | me.assertTrue(x != y) | |
130 | me.assertTrue(x > y) | |
131 | me.assertFalse(y > x) | |
132 | me.assertFalse(x > x) | |
133 | me.assertTrue(x >= y) | |
134 | me.assertFalse(y >= x) | |
135 | me.assertTrue(x >= x) | |
136 | me.assertFalse(x <= y) | |
137 | me.assertTrue(y <= x) | |
138 | me.assertTrue(x <= x) | |
139 | me.assertFalse(x < y) | |
140 | me.assertTrue(y < x) | |
141 | me.assertFalse(x < x) | |
142 | ||
77535854 MW |
143 | def test_float(me): |
144 | x, y = C.MP(169), 24.0 | |
145 | for fn in [T.add, T.sub, T.mul, T.div]: | |
146 | me.assertEqual(type(fn(x, y)), float) | |
147 | me.assertEqual(type(fn(y, x)), float) | |
148 | me.assertEqual(x, 169.0) | |
149 | me.assertNotEqual(x, 169.1) | |
150 | me.assertNotEqual(x, 168.9) | |
151 | me.assertTrue(x > 168.9) | |
152 | me.assertTrue(x < 169.1) | |
153 | z = 1.0 | |
154 | while z == z + 1: z *= 2.0 | |
155 | me.assertNotEqual(C.MP(int(z)) + 1, z) | |
156 | ||
e7d2e2e2 MW |
157 | def test_strconv(me): |
158 | x, y = C.MP(169), "24" | |
159 | for fn in [T.add, T.sub]: | |
160 | me.assertRaises(TypeError, fn, x, y) | |
161 | me.assertRaises(TypeError, fn, y, x) | |
162 | me.assertEqual(x*y, 169*"24") | |
163 | me.assertEqual(y*x, 169*"24") | |
164 | ||
553d59fe MW |
165 | def test_bits(me): |
166 | x, y, zero = C.MP(169), C.MP(-24), C.MP(0) | |
167 | me.assertTrue(x.testbit(0)) | |
168 | me.assertFalse(x.testbit(1)) | |
169 | me.assertFalse(x.testbit(1000)) | |
170 | me.assertFalse(y.testbit(0)) | |
171 | me.assertTrue(y.testbit(3)) | |
172 | me.assertTrue(y.testbit(1000)) | |
173 | ||
174 | me.assertEqual(x.setbit(0), x) | |
175 | me.assertEqual(x.clearbit(0), 168) | |
176 | me.assertEqual(x.setbit(1), 171) | |
177 | me.assertEqual(x.clearbit(1), x) | |
178 | me.assertEqual(y.setbit(0), -23) | |
179 | me.assertEqual(y.clearbit(0), y) | |
180 | me.assertEqual(y.setbit(3), y) | |
181 | me.assertEqual(y.clearbit(3), -32) | |
182 | me.assertEqual(y.setbit(1000), y) | |
183 | ||
184 | me.assertEqual(x.nbits, 8) | |
185 | me.assertEqual(y.nbits, 5) | |
186 | me.assertEqual(zero.nbits, 0) | |
187 | ||
188 | def test_loadstore(me): | |
189 | x = C.MP(0x0123456789ab) | |
190 | y = -x | |
191 | u = C.MP(0xfedcba9876) | |
192 | ||
193 | me.assertEqual(x.noctets, 6) | |
194 | me.assertEqual(x.noctets2c, 6) | |
195 | me.assertEqual(y.noctets, 6) | |
196 | me.assertEqual(y.noctets2c, 6) | |
197 | me.assertEqual(u.noctets, 5) | |
198 | me.assertEqual(u.noctets2c, 6) | |
199 | ||
200 | me.assertEqual(x, C.MP.loadb(C.bytes("0123456789ab"))) | |
201 | me.assertEqual(x, C.MP.loadb2c(C.bytes("0123456789ab"))) | |
202 | me.assertEqual(y, C.MP.loadb2c(C.bytes("fedcba987655"))) | |
203 | ||
204 | me.assertEqual(x.storeb(), C.bytes("0123456789ab")) | |
205 | me.assertEqual(x.storeb(3), C.bytes("6789ab")) | |
206 | me.assertEqual(x.storeb(8), C.bytes("00000123456789ab")) | |
207 | me.assertEqual(x.storeb2c(), C.bytes("0123456789ab")) | |
208 | me.assertEqual(x.storeb2c(3), C.bytes("6789ab")) | |
209 | me.assertEqual(x.storeb2c(8), C.bytes("00000123456789ab")) | |
210 | me.assertEqual(u.storeb2c(), C.bytes("00fedcba9876")) | |
211 | me.assertEqual(y.storeb2c(), C.bytes("fedcba987655")) | |
212 | me.assertEqual(y.storeb2c(3), C.bytes("987655")) | |
213 | me.assertEqual(y.storeb2c(8), C.bytes("fffffedcba987655")) | |
214 | ||
215 | me.assertEqual(x, C.MP.loadl(C.bytes("ab8967452301"))) | |
216 | me.assertEqual(x, C.MP.loadl2c(C.bytes("ab8967452301"))) | |
217 | me.assertEqual(y, C.MP.loadl2c(C.bytes("557698badcfe"))) | |
218 | ||
219 | me.assertEqual(x.storel(), C.bytes("ab8967452301")) | |
220 | me.assertEqual(x.storel(3), C.bytes("ab8967")) | |
221 | me.assertEqual(x.storel(8), C.bytes("ab89674523010000")) | |
222 | me.assertEqual(x.storel2c(), C.bytes("ab8967452301")) | |
223 | me.assertEqual(x.storel2c(3), C.bytes("ab8967")) | |
224 | me.assertEqual(x.storel2c(8), C.bytes("ab89674523010000")) | |
225 | me.assertEqual(u.storel2c(), C.bytes("7698badcfe00")) | |
226 | me.assertEqual(y.storel2c(), C.bytes("557698badcfe")) | |
227 | me.assertEqual(y.storel2c(3), C.bytes("557698")) | |
228 | me.assertEqual(y.storel2c(8), C.bytes("557698badcfeffff")) | |
229 | ||
230 | me.assertEqual(x.tobuf(), C.bytes("00060123456789ab")) | |
231 | me.assertEqual((x, T.bin("abcd")), | |
232 | C.MP.frombuf(C.bytes("00060123456789ab61626364"))) | |
233 | ||
234 | def test_numbertheory(me): | |
235 | p, x, y, z = C.MP(173), C.MP(169), C.MP(24), C.MP(20) | |
236 | ||
237 | me.assertEqual(x.odd(), (0, x)) | |
238 | me.assertEqual(y.odd(), (3, 3)) | |
239 | ||
240 | me.assertEqual(x.sqr(), 28561) | |
241 | me.assertEqual(x.sqrt(), 13) | |
242 | me.assertEqual(y.sqrt(), 4) | |
243 | ||
244 | me.assertEqual(x.gcd(y), 1) | |
245 | me.assertEqual(x.gcdx(y), (1, -23, 162)) | |
246 | me.assertEqual(y.gcdx(x), (1, -7, 1)) | |
247 | me.assertEqual(x.modinv(y), 162) | |
248 | me.assertEqual(y.modinv(x), 1) | |
249 | ||
250 | me.assertEqual(x.jacobi(y), 1) | |
251 | me.assertEqual(x.jacobi(13), 0) | |
252 | me.assertEqual(y.jacobi(x), 1) | |
253 | me.assertEqual(p.jacobi(y), 1) | |
254 | me.assertEqual(p.jacobi(z), -1) | |
255 | me.assertEqual(p.modsqrt(y), 71) | |
256 | me.assertRaises(ValueError, p.modsqrt, z) | |
257 | ||
258 | me.assertEqual(y.leastcongruent(x, 32), 184) | |
259 | ||
260 | me.assertTrue(p.primep()) | |
261 | me.assertFalse(x.primep()) | |
262 | ||
263 | def test_bang(me): | |
264 | me.assertEqual(C.MP.factorial(0), 1) | |
265 | me.assertEqual \ | |
266 | (C.MP.factorial(50), | |
267 | 30414093201713378043612608166064768844377641568960512000000000000) | |
268 | me.assertRaises((ValueError, OverflowError), C.MP.factorial, -1) | |
269 | ||
270 | def test_fib(me): | |
271 | me.assertEqual(C.MP.fibonacci(-2), -1) | |
272 | me.assertEqual(C.MP.fibonacci(-1), +1) | |
273 | me.assertEqual(C.MP.fibonacci( 0), 0) | |
274 | me.assertEqual(C.MP.fibonacci(+1), +1) | |
275 | me.assertEqual(C.MP.fibonacci(+2), +1) | |
276 | me.assertEqual(C.MP.fibonacci(50), 12586269025) | |
277 | ||
278 | ###-------------------------------------------------------------------------- | |
279 | class TestMPMul (U.TestCase): | |
280 | ||
281 | def test(me): | |
282 | m = C.MPMul() | |
283 | me.assertTrue(m.livep) | |
284 | m.factor(1, 2, 3) | |
285 | m.factor([4, 5, 6]) | |
286 | me.assertEqual(m.done(), 720) | |
287 | me.assertFalse(m.livep) | |
288 | ||
289 | me.assertEqual(C.MPMul(T.range(1, 7)).done(), 720) | |
290 | me.assertEqual(C.MP.factorial(6), 720) | |
291 | ||
292 | ###-------------------------------------------------------------------------- | |
293 | class TestMPMont (U.TestCase): | |
294 | ||
295 | def test(me): | |
296 | ||
297 | me.assertRaises(ValueError, | |
298 | C.MPMont, 35315021952044908656941308411353985942) | |
299 | me.assertRaises(ValueError, C.MPMont, -9) | |
300 | ||
301 | p = C.MP(269464705320809171350781605680038324101) | |
302 | g = C.MP(2) # lucky chance | |
303 | x = C.MP(211184293914316080585277908844600399612) | |
304 | y = C.MP(154454671298730680774195646814344206562) | |
305 | xy = C.MP(209444562478584646216087606217820187655) | |
306 | me.assertTrue(p.primep()) | |
307 | m = C.MPMont(p) | |
308 | me.assertEqual(m.m, p) | |
309 | ||
310 | ## The precise values of m.r and m.r2 are dependent on the internal | |
311 | ## bignum representation. But we expect m.r to be congruent to some | |
312 | ## power of two. (It should be 2^128.) | |
313 | t = p.modinv(m.r) | |
314 | for i in T.range(1025): | |
315 | if t == 1: break | |
316 | t *= 2 | |
317 | if t >= p: t -= p | |
318 | else: | |
319 | me.fail("m.r is not a small-ish power of 2") | |
320 | me.assertEqual(m.r2, pow(2, 2*i, p)) | |
321 | me.assertEqual(m.ext(m.r), 1) | |
322 | me.assertEqual(m.reduce(m.r), 1) | |
323 | ||
324 | me.assertEqual(m.ext(m.int(x)), x) | |
325 | me.assertEqual(m.int(x), m.mul(x, m.r2)) | |
326 | me.assertEqual(m.mul(m.int(x), y), xy) | |
327 | me.assertEqual(m.ext(m.mul(m.int(x), m.int(y))), xy) | |
328 | ||
329 | me.assertEqual(m.exp(2, p - 1), 1) | |
330 | me.assertEqual(m.expr(m.int(2), p - 1), m.r) | |
331 | ||
332 | q, r, s, z = 32, 128, 2048, pow(g, 156, p) | |
333 | me.assertEqual(m.mexp([(q, 9), (r, 8), (s, 5)]), z) | |
334 | me.assertEqual(m.mexp(q, 9, r, 8, s, 5), z) | |
335 | ||
336 | q, r, s, z = T.imap(m.int, [32, 128, 2048, pow(g, 156, p)]) | |
337 | me.assertEqual(m.mexpr([(q, 9), (r, 8), (s, 5)]), z) | |
338 | me.assertEqual(m.mexpr(q, 9, r, 8, s, 5), z) | |
339 | ||
340 | ###-------------------------------------------------------------------------- | |
341 | class TestMPBarrett (U.TestCase): | |
342 | ||
343 | def test(me): | |
344 | ||
345 | p = C.MP(269464705320809171350781605680038324101) | |
346 | g = C.MP(2) # lucky chance | |
347 | x = C.MP(211184293914316080585277908844600399612) | |
348 | y = C.MP(154454671298730680774195646814344206562) | |
349 | xy = C.MP(209444562478584646216087606217820187655) | |
350 | me.assertTrue(p.primep()) | |
351 | m = C.MPBarrett(p) | |
352 | me.assertEqual(m.m, p) | |
353 | ||
354 | me.assertEqual(m.reduce(x*y), xy) | |
355 | ||
356 | me.assertEqual(m.exp(2, p - 1), 1) | |
357 | ||
358 | q, r, s, z = 32, 128, 2048, pow(g, 156, p) | |
359 | me.assertEqual(m.mexp([(q, 9), (r, 8), (s, 5)]), z) | |
360 | me.assertEqual(m.mexp(q, 9, r, 8, s, 5), z) | |
361 | ||
362 | ###-------------------------------------------------------------------------- | |
363 | class TestMPReduce (U.TestCase): | |
364 | ||
365 | def test(me): | |
366 | ||
367 | p = C.MP(2)**127 - 1 | |
368 | g = C.MP(2) # lucky chance | |
369 | x = C.MP(94827182170881245766374991987593163418) | |
370 | y = C.MP(106025009945795266831396608563402138277) | |
371 | xy = C.MP(80027041045616838298103413933629021123) | |
372 | me.assertTrue(p.primep()) | |
373 | m = C.MPReduce(p) | |
374 | me.assertEqual(m.m, p) | |
375 | ||
376 | me.assertEqual(m.reduce(x*y), xy) | |
377 | ||
378 | me.assertEqual(m.exp(2, 127), 1) | |
379 | ||
380 | ###-------------------------------------------------------------------------- | |
381 | class TestMPCRT (U.TestCase): | |
382 | ||
383 | def test(me): | |
384 | ||
385 | c = C.MPCRT(5, 7, 11) | |
386 | me.assertEqual(c.moduli, [5, 7, 11]) | |
387 | me.assertEqual(c.product, 385) | |
388 | me.assertEqual(c.solve([2, 3, 4]), 367) | |
389 | me.assertEqual(c.solve([2, -4, -7]), 367) | |
390 | ||
391 | me.assertRaises(ValueError, C.MPCRT, [6, 15, 35]) | |
392 | ||
393 | ###-------------------------------------------------------------------------- | |
394 | class TestGF (U.TestCase): | |
395 | ||
396 | def test_make(me): | |
397 | x = C.GF(5) | |
398 | k = C.PrimeField(17) | |
399 | kk = C.BinPolyField(C.GF(0x13)) | |
400 | E = k.ec(-3, 1) | |
401 | me.assertTrue(C.GF(x) is x) | |
402 | me.assertEqual(C.GF(k(8)), C.GF(8)) | |
403 | me.assertEqual(C.GF(kk(8)), C.GF(8)) | |
404 | me.assertEqual(C.GF(E(1, 4)), C.GF(1)) | |
405 | me.assertRaises(TypeError, C.GF, E()) | |
406 | ||
e7d2e2e2 | 407 | me.assertNotEqual(x, 5) # no implicit conversion to int |
553d59fe MW |
408 | me.assertEqual(int(x), 5) |
409 | y = C.GF(0x4eeb684a0954ec4ceb255e3e9778d41) | |
410 | me.assertEqual(type(int(y)), T.long) | |
411 | ||
412 | me.assertEqual(C.GF('0x4eeb684a0954ec4ceb255e3e9778d41'), y) | |
413 | me.assertEqual(C.GF('4eeb684a0954ec4ceb255e3e9778d41', 16), y) | |
414 | me.assertEqual(C.GF('0b0', 16), C.GF(176)) # not 0 | |
415 | ||
416 | me.assertEqual(C.GF('047353320450112516611472622536175135706501'), y) | |
417 | me.assertEqual(C.GF('0o47353320450112516611472622536175135706501'), y) | |
418 | me.assertEqual(C.GF('047353320450112516611472622536175135706501', 8), y) | |
419 | me.assertEqual(C.GF('47353320450112516611472622536175135706501', 8), y) | |
420 | ||
421 | t = C.GF(661438603) | |
422 | me.assertEqual(C.GF('0b100111011011001100000010001011'), t) | |
423 | me.assertEqual(C.GF('100111011011001100000010001011', 2), t) | |
424 | ||
425 | def test_string(me): | |
426 | y = C.GF(0x4eeb684a0954ec4ceb255e3e9778d41) | |
427 | me.assertEqual(str(y), '0x4eeb684a0954ec4ceb255e3e9778d41') | |
e38168e2 | 428 | me.assertEqual(repr(y), 'GF(0x4eeb684a0954ec4ceb255e3e9778d41)') |
553d59fe | 429 | me.assertEqual(hex(y), '0x4eeb684a0954ec4ceb255e3e9778d41') |
f7623015 MW |
430 | me.assertEqual(oct(y), T.py23('0', '0o') + |
431 | '47353320450112516611472622536175135706501') | |
a90a9c0e MW |
432 | try: bin |
433 | except NameError: pass | |
434 | else: me.assertEqual(bin(C.GF(661438603)), | |
435 | '0b100111011011001100000010001011') | |
553d59fe MW |
436 | |
437 | def test_number(me): | |
438 | x, y, m, zero = C.GF(0xa9), C.GF(0x18), C.GF(0x11b), C.GF(0) | |
439 | ||
440 | me.assertEqual(x, -x) | |
441 | me.assertEqual(abs(x), x) | |
442 | ||
443 | me.assertEqual(x + y, C.GF(0xb1)) | |
444 | me.assertEqual(x - y, C.GF(0xb1)) | |
445 | me.assertEqual(x*y, C.GF(0xfd8)) | |
446 | me.assertEqual(x&y, C.GF(0x8)) | |
447 | me.assertEqual(x | y, C.GF(0xb9)) | |
448 | me.assertEqual(x ^ y, C.GF(0xb1)) | |
449 | ||
450 | me.assertEqual(x << 3, C.GF(0x548)) | |
451 | me.assertEqual(x << -2, C.GF(0x2a)) | |
452 | me.assertEqual(x >> 2, C.GF(0x2a)) | |
453 | me.assertEqual(x >> -3, C.GF(0x548)) | |
454 | ||
455 | u = x/y; me.assertEqual((u.numer, u.denom), (C.GF(0x67), C.GF(0x8))) | |
456 | me.assertEqual(x//y, C.GF(0xc)) | |
457 | me.assertEqual(x%y, C.GF(0x9)) | |
458 | me.assertEqual(divmod(x, y), (C.GF(0xc), C.GF(0x9))) | |
459 | me.assertRaises(ZeroDivisionError, lambda: x/zero) | |
460 | me.assertRaises(ZeroDivisionError, lambda: x//zero) | |
461 | me.assertRaises(ZeroDivisionError, lambda: x%zero) | |
462 | me.assertRaises(ZeroDivisionError, divmod, x, zero) | |
463 | ||
464 | me.assertEqual(pow(x, 24), | |
465 | C.GF(0x1000100000001010000010101000101010001000001)) | |
466 | me.assertEqual(pow(x, 24, m), C.GF(0x78)) | |
467 | me.assertEqual(pow(x, -24, m), C.GF(0xb6)) | |
468 | me.assertRaises(ZeroDivisionError, pow, x, -24, C.GF(0x18)) | |
469 | ||
470 | me.assertTrue(x) | |
471 | me.assertFalse(zero) | |
472 | ||
473 | def test_order(me): | |
474 | x, y, z = C.GF(0xa9), C.GF(0x18), C.GF(0xb3) | |
475 | me.assertTrue(x == x) | |
476 | me.assertFalse(x != x) | |
477 | me.assertFalse(x == y) | |
478 | me.assertTrue(x != y) | |
479 | me.assertTrue(x > y) | |
480 | me.assertFalse(y > x) | |
481 | me.assertFalse(x > x) | |
482 | me.assertFalse(x > z) | |
483 | me.assertFalse(z > x) | |
484 | me.assertTrue(x >= y) | |
485 | me.assertFalse(y >= x) | |
486 | me.assertTrue(x >= x) | |
487 | me.assertTrue(x >= z) | |
488 | me.assertTrue(z >= x) | |
489 | me.assertFalse(x <= y) | |
490 | me.assertTrue(y <= x) | |
491 | me.assertTrue(x <= x) | |
492 | me.assertTrue(x <= z) | |
493 | me.assertTrue(z <= x) | |
494 | me.assertFalse(x < y) | |
495 | me.assertTrue(y < x) | |
496 | me.assertFalse(x < x) | |
497 | me.assertFalse(x < z) | |
498 | me.assertFalse(z < x) | |
499 | ||
500 | def test_bits(me): | |
501 | x, zero = C.GF(0xa9), C.GF(0) | |
502 | me.assertTrue(x.testbit(0)) | |
503 | me.assertFalse(x.testbit(1)) | |
504 | me.assertFalse(x.testbit(1000)) | |
505 | ||
506 | me.assertEqual(x.setbit(0), x) | |
507 | me.assertEqual(x.clearbit(0), C.GF(0xa8)) | |
508 | me.assertEqual(x.setbit(1), C.GF(0xab)) | |
509 | me.assertEqual(x.clearbit(1), x) | |
510 | ||
511 | me.assertEqual(x.nbits, 8) | |
512 | me.assertEqual(x.degree, 7) | |
513 | me.assertEqual(zero.nbits, 0) | |
514 | me.assertEqual(zero.degree, -1) | |
515 | ||
516 | def test_loadstore(me): | |
517 | x = C.GF(0x0123456789ab) | |
518 | ||
519 | me.assertEqual(x.noctets, 6) | |
520 | ||
521 | me.assertEqual(x, C.GF.loadb(C.bytes("0123456789ab"))) | |
522 | ||
523 | me.assertEqual(x.storeb(), C.bytes("0123456789ab")) | |
524 | me.assertEqual(x.storeb(3), C.bytes("6789ab")) | |
525 | me.assertEqual(x.storeb(8), C.bytes("00000123456789ab")) | |
526 | ||
527 | me.assertEqual(x, C.GF.loadl(C.bytes("ab8967452301"))) | |
528 | ||
529 | me.assertEqual(x.storel(), C.bytes("ab8967452301")) | |
530 | me.assertEqual(x.storel(3), C.bytes("ab8967")) | |
531 | me.assertEqual(x.storel(8), C.bytes("ab89674523010000")) | |
532 | ||
533 | me.assertEqual(x.tobuf(), C.bytes("00060123456789ab")) | |
534 | me.assertEqual((x, T.bin("abcd")), | |
535 | C.GF.frombuf(C.bytes("00060123456789ab61626364"))) | |
536 | ||
537 | def test_numbertheory(me): | |
538 | p, x, y = C.GF(0x11b), C.GF(0xa9), C.GF(0x18) | |
539 | ||
540 | me.assertEqual(x.sqr(), C.GF(0x4441)) | |
541 | ||
542 | me.assertEqual(x.gcd(y), C.GF(0x3)) | |
543 | me.assertEqual(x.gcdx(y), (C.GF(0x3), C.GF(0x3), C.GF(0x15))) | |
544 | me.assertEqual(p.modinv(x), C.GF(0xc8)) | |
545 | ||
546 | me.assertTrue(p.irreduciblep()) | |
547 | me.assertFalse(x.irreduciblep()) | |
548 | ||
549 | ###-------------------------------------------------------------------------- | |
550 | class TestGFReduce (U.TestCase): | |
551 | ||
552 | def test(me): | |
553 | p = C.GF(0x87).setbit(128) | |
554 | me.assertTrue(p.irreduciblep()) | |
555 | m = C.GFReduce(p) | |
556 | ||
557 | x = C.GF(0xce46b4c1d3a1523520b1bb6eb5c61883) | |
558 | y = C.GF(0xb5b0b3566b8e03f4b4a2b1ac413f8566) | |
559 | xy = C.GF(0x28e5b895c11b08edc2fe7e1be5694c64) | |
560 | ||
561 | me.assertEqual(m.reduce(x*y), xy) | |
562 | me.assertEqual(m.trace(x), 0) | |
563 | me.assertEqual(m.trace(y), 1) | |
564 | me.assertEqual(m.sqrt(x), C.GF(0xa277ee4bf770e5974cf1e31b1ccb54a1)) | |
565 | me.assertEqual(m.halftrace(y), C.GF(0x9cea73e79ffd190dd3c81d33e58d8e6f)) | |
566 | me.assertEqual(m.quadsolve(x), C.GF(0x9664c09d23d168147a438de6a813c784)) | |
567 | ||
568 | ###-------------------------------------------------------------------------- | |
569 | class TestGFN (U.TestCase): | |
570 | ||
571 | def test(me): | |
572 | p = C.GF(0x87).setbit(128) | |
573 | beta = C.GF(0xc50f387e37194d4a4b41e157a3e2b5e1) | |
574 | y = C.GF(0xdaca76dc2578a63c788a2ce0fc7878f6) | |
575 | yy = C.GF(0x298a98f955100f054fcee3433f96b00e) | |
576 | zero, one, fff = C.GF(0), C.GF(1), C.GF(T.long(2)**128 - 1) | |
577 | me.assertTrue(p.irreduciblep()) | |
578 | ||
579 | gfn = C.GFN(p, beta) | |
580 | me.assertEqual(gfn.p, p) | |
581 | me.assertEqual(gfn.beta, beta) | |
582 | me.assertEqual(gfn.pton(zero), zero) | |
583 | me.assertEqual(gfn.ntop(zero), zero) | |
584 | me.assertEqual(gfn.pton(one), fff) | |
585 | me.assertEqual(gfn.ntop(fff), one) | |
586 | me.assertEqual(gfn.pton(y), yy) | |
587 | me.assertEqual(gfn.ntop(yy), y) | |
588 | ||
589 | ## Doesn't generate a normal basis. | |
590 | me.assertRaises(ValueError, C.GFN, p, y) | |
591 | ||
592 | ###----- That's all, folks -------------------------------------------------- | |
593 | ||
594 | if __name__ == "__main__": U.main() |