3 ### Testing multiprecision integer (and related) functionality
5 ### (c) 2019 Straylight/Edgeware
8 ###----- Licensing notice ---------------------------------------------------
10 ### This file is part of the Python interface to Catacomb.
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.
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.
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,
27 ###--------------------------------------------------------------------------
34 ###--------------------------------------------------------------------------
35 class TestMP (U
.TestCase
):
40 kk
= C
.BinPolyField(C
.GF(0x13))
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())
49 me
.assertEqual(int(x
), 5)
50 big
= 6556380541834372447694561492436749633
51 me
.assertEqual(type(big
), T
.long)
53 me
.assertEqual(y
, big
)
54 me
.assertEqual(int(y
), big
)
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
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
)
66 me
.assertEqual(C
.MP('0b100111011011001100000010001011'), 661438603)
67 me
.assertEqual(C
.MP('100111011011001100000010001011', 2), 661438603)
70 y
= C
.MP(6556380541834372447694561492436749633)
71 me
.assertEqual(str(y
), '6556380541834372447694561492436749633')
72 me
.assertEqual(repr(y
), 'MP(6556380541834372447694561492436749633)')
73 me
.assertEqual(hex(y
), '0x4eeb684a0954ec4ceb255e3e9778d41')
74 me
.assertEqual(oct(y
), T
.py23('0', '0o') +
75 '47353320450112516611472622536175135706501')
77 except NameError: pass
78 else: me
.assertEqual(bin(C
.MP(661438603)),
79 '0b100111011011001100000010001011')
82 x
, y
, m
, zero
= C
.MP(169), C
.MP(24), C
.MP(205), C
.MP(0)
84 me
.assertEqual(-x
, -169)
85 me
.assertEqual(~x
, -170)
86 me
.assertEqual(abs(x
), 169)
87 me
.assertEqual(abs(-x
), 169)
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)
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)
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
)
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)
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
)
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
)
141 me
.assertFalse(x
< x
)
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)
154 while z
== z
+ 1: z
*= 2.0
155 me
.assertNotEqual(C
.MP(int(z
)) + 1, z
)
158 x
, y
, zero
= C
.MP(169), C
.MP(-24), C
.MP(0)
159 me
.assertTrue(x
.testbit(0))
160 me
.assertFalse(x
.testbit(1))
161 me
.assertFalse(x
.testbit(1000))
162 me
.assertFalse(y
.testbit(0))
163 me
.assertTrue(y
.testbit(3))
164 me
.assertTrue(y
.testbit(1000))
166 me
.assertEqual(x
.setbit(0), x
)
167 me
.assertEqual(x
.clearbit(0), 168)
168 me
.assertEqual(x
.setbit(1), 171)
169 me
.assertEqual(x
.clearbit(1), x
)
170 me
.assertEqual(y
.setbit(0), -23)
171 me
.assertEqual(y
.clearbit(0), y
)
172 me
.assertEqual(y
.setbit(3), y
)
173 me
.assertEqual(y
.clearbit(3), -32)
174 me
.assertEqual(y
.setbit(1000), y
)
176 me
.assertEqual(x
.nbits
, 8)
177 me
.assertEqual(y
.nbits
, 5)
178 me
.assertEqual(zero
.nbits
, 0)
180 def test_loadstore(me
):
181 x
= C
.MP(0x0123456789ab)
183 u
= C
.MP(0xfedcba9876)
185 me
.assertEqual(x
.noctets
, 6)
186 me
.assertEqual(x
.noctets2c
, 6)
187 me
.assertEqual(y
.noctets
, 6)
188 me
.assertEqual(y
.noctets2c
, 6)
189 me
.assertEqual(u
.noctets
, 5)
190 me
.assertEqual(u
.noctets2c
, 6)
192 me
.assertEqual(x
, C
.MP
.loadb(C
.bytes("0123456789ab")))
193 me
.assertEqual(x
, C
.MP
.loadb2c(C
.bytes("0123456789ab")))
194 me
.assertEqual(y
, C
.MP
.loadb2c(C
.bytes("fedcba987655")))
196 me
.assertEqual(x
.storeb(), C
.bytes("0123456789ab"))
197 me
.assertEqual(x
.storeb(3), C
.bytes("6789ab"))
198 me
.assertEqual(x
.storeb(8), C
.bytes("00000123456789ab"))
199 me
.assertEqual(x
.storeb2c(), C
.bytes("0123456789ab"))
200 me
.assertEqual(x
.storeb2c(3), C
.bytes("6789ab"))
201 me
.assertEqual(x
.storeb2c(8), C
.bytes("00000123456789ab"))
202 me
.assertEqual(u
.storeb2c(), C
.bytes("00fedcba9876"))
203 me
.assertEqual(y
.storeb2c(), C
.bytes("fedcba987655"))
204 me
.assertEqual(y
.storeb2c(3), C
.bytes("987655"))
205 me
.assertEqual(y
.storeb2c(8), C
.bytes("fffffedcba987655"))
207 me
.assertEqual(x
, C
.MP
.loadl(C
.bytes("ab8967452301")))
208 me
.assertEqual(x
, C
.MP
.loadl2c(C
.bytes("ab8967452301")))
209 me
.assertEqual(y
, C
.MP
.loadl2c(C
.bytes("557698badcfe")))
211 me
.assertEqual(x
.storel(), C
.bytes("ab8967452301"))
212 me
.assertEqual(x
.storel(3), C
.bytes("ab8967"))
213 me
.assertEqual(x
.storel(8), C
.bytes("ab89674523010000"))
214 me
.assertEqual(x
.storel2c(), C
.bytes("ab8967452301"))
215 me
.assertEqual(x
.storel2c(3), C
.bytes("ab8967"))
216 me
.assertEqual(x
.storel2c(8), C
.bytes("ab89674523010000"))
217 me
.assertEqual(u
.storel2c(), C
.bytes("7698badcfe00"))
218 me
.assertEqual(y
.storel2c(), C
.bytes("557698badcfe"))
219 me
.assertEqual(y
.storel2c(3), C
.bytes("557698"))
220 me
.assertEqual(y
.storel2c(8), C
.bytes("557698badcfeffff"))
222 me
.assertEqual(x
.tobuf(), C
.bytes("00060123456789ab"))
223 me
.assertEqual((x
, T
.bin("abcd")),
224 C
.MP
.frombuf(C
.bytes("00060123456789ab61626364")))
226 def test_numbertheory(me
):
227 p
, x
, y
, z
= C
.MP(173), C
.MP(169), C
.MP(24), C
.MP(20)
229 me
.assertEqual(x
.odd(), (0, x
))
230 me
.assertEqual(y
.odd(), (3, 3))
232 me
.assertEqual(x
.sqr(), 28561)
233 me
.assertEqual(x
.sqrt(), 13)
234 me
.assertEqual(y
.sqrt(), 4)
236 me
.assertEqual(x
.gcd(y
), 1)
237 me
.assertEqual(x
.gcdx(y
), (1, -23, 162))
238 me
.assertEqual(y
.gcdx(x
), (1, -7, 1))
239 me
.assertEqual(x
.modinv(y
), 162)
240 me
.assertEqual(y
.modinv(x
), 1)
242 me
.assertEqual(x
.jacobi(y
), 1)
243 me
.assertEqual(x
.jacobi(13), 0)
244 me
.assertEqual(y
.jacobi(x
), 1)
245 me
.assertEqual(p
.jacobi(y
), 1)
246 me
.assertEqual(p
.jacobi(z
), -1)
247 me
.assertEqual(p
.modsqrt(y
), 71)
248 me
.assertRaises(ValueError, p
.modsqrt
, z
)
250 me
.assertEqual(y
.leastcongruent(x
, 32), 184)
252 me
.assertTrue(p
.primep())
253 me
.assertFalse(x
.primep())
256 me
.assertEqual(C
.MP
.factorial(0), 1)
259 30414093201713378043612608166064768844377641568960512000000000000)
260 me
.assertRaises((ValueError, OverflowError), C
.MP
.factorial
, -1)
263 me
.assertEqual(C
.MP
.fibonacci(-2), -1)
264 me
.assertEqual(C
.MP
.fibonacci(-1), +1)
265 me
.assertEqual(C
.MP
.fibonacci( 0), 0)
266 me
.assertEqual(C
.MP
.fibonacci(+1), +1)
267 me
.assertEqual(C
.MP
.fibonacci(+2), +1)
268 me
.assertEqual(C
.MP
.fibonacci(50), 12586269025)
270 ###--------------------------------------------------------------------------
271 class TestMPMul (U
.TestCase
):
275 me
.assertTrue(m
.livep
)
278 me
.assertEqual(m
.done(), 720)
279 me
.assertFalse(m
.livep
)
281 me
.assertEqual(C
.MPMul(T
.range(1, 7)).done(), 720)
282 me
.assertEqual(C
.MP
.factorial(6), 720)
284 ###--------------------------------------------------------------------------
285 class TestMPMont (U
.TestCase
):
289 me
.assertRaises(ValueError,
290 C
.MPMont
, 35315021952044908656941308411353985942)
291 me
.assertRaises(ValueError, C
.MPMont
, -9)
293 p
= C
.MP(269464705320809171350781605680038324101)
294 g
= C
.MP(2) # lucky chance
295 x
= C
.MP(211184293914316080585277908844600399612)
296 y
= C
.MP(154454671298730680774195646814344206562)
297 xy
= C
.MP(209444562478584646216087606217820187655)
298 me
.assertTrue(p
.primep())
300 me
.assertEqual(m
.m
, p
)
302 ## The precise values of m.r and m.r2 are dependent on the internal
303 ## bignum representation. But we expect m.r to be congruent to some
304 ## power of two. (It should be 2^128.)
306 for i
in T
.range(1025):
311 me
.fail("m.r is not a small-ish power of 2")
312 me
.assertEqual(m
.r2
, pow(2, 2*i
, p
))
313 me
.assertEqual(m
.ext(m
.r
), 1)
314 me
.assertEqual(m
.reduce(m
.r
), 1)
316 me
.assertEqual(m
.ext(m
.int(x
)), x
)
317 me
.assertEqual(m
.int(x
), m
.mul(x
, m
.r2
))
318 me
.assertEqual(m
.mul(m
.int(x
), y
), xy
)
319 me
.assertEqual(m
.ext(m
.mul(m
.int(x
), m
.int(y
))), xy
)
321 me
.assertEqual(m
.exp(2, p
- 1), 1)
322 me
.assertEqual(m
.expr(m
.int(2), p
- 1), m
.r
)
324 q
, r
, s
, z
= 32, 128, 2048, pow(g
, 156, p
)
325 me
.assertEqual(m
.mexp([(q
, 9), (r
, 8), (s
, 5)]), z
)
326 me
.assertEqual(m
.mexp(q
, 9, r
, 8, s
, 5), z
)
328 q
, r
, s
, z
= T
.imap(m
.int, [32, 128, 2048, pow(g
, 156, p
)])
329 me
.assertEqual(m
.mexpr([(q
, 9), (r
, 8), (s
, 5)]), z
)
330 me
.assertEqual(m
.mexpr(q
, 9, r
, 8, s
, 5), z
)
332 ###--------------------------------------------------------------------------
333 class TestMPBarrett (U
.TestCase
):
337 p
= C
.MP(269464705320809171350781605680038324101)
338 g
= C
.MP(2) # lucky chance
339 x
= C
.MP(211184293914316080585277908844600399612)
340 y
= C
.MP(154454671298730680774195646814344206562)
341 xy
= C
.MP(209444562478584646216087606217820187655)
342 me
.assertTrue(p
.primep())
344 me
.assertEqual(m
.m
, p
)
346 me
.assertEqual(m
.reduce(x
*y
), xy
)
348 me
.assertEqual(m
.exp(2, p
- 1), 1)
350 q
, r
, s
, z
= 32, 128, 2048, pow(g
, 156, p
)
351 me
.assertEqual(m
.mexp([(q
, 9), (r
, 8), (s
, 5)]), z
)
352 me
.assertEqual(m
.mexp(q
, 9, r
, 8, s
, 5), z
)
354 ###--------------------------------------------------------------------------
355 class TestMPReduce (U
.TestCase
):
360 g
= C
.MP(2) # lucky chance
361 x
= C
.MP(94827182170881245766374991987593163418)
362 y
= C
.MP(106025009945795266831396608563402138277)
363 xy
= C
.MP(80027041045616838298103413933629021123)
364 me
.assertTrue(p
.primep())
366 me
.assertEqual(m
.m
, p
)
368 me
.assertEqual(m
.reduce(x
*y
), xy
)
370 me
.assertEqual(m
.exp(2, 127), 1)
372 ###--------------------------------------------------------------------------
373 class TestMPCRT (U
.TestCase
):
377 c
= C
.MPCRT(5, 7, 11)
378 me
.assertEqual(c
.moduli
, [5, 7, 11])
379 me
.assertEqual(c
.product
, 385)
380 me
.assertEqual(c
.solve([2, 3, 4]), 367)
381 me
.assertEqual(c
.solve([2, -4, -7]), 367)
383 me
.assertRaises(ValueError, C
.MPCRT
, [6, 15, 35])
385 ###--------------------------------------------------------------------------
386 class TestGF (U
.TestCase
):
391 kk
= C
.BinPolyField(C
.GF(0x13))
393 me
.assertTrue(C
.GF(x
) is x
)
394 me
.assertEqual(C
.GF(k(8)), C
.GF(8))
395 me
.assertEqual(C
.GF(kk(8)), C
.GF(8))
396 me
.assertEqual(C
.GF(E(1, 4)), C
.GF(1))
397 me
.assertRaises(TypeError, C
.GF
, E())
399 me
.assertEqual(int(x
), 5)
400 y
= C
.GF(0x4eeb684a0954ec4ceb255e3e9778d41)
401 me
.assertEqual(type(int(y
)), T
.long)
403 me
.assertEqual(C
.GF('0x4eeb684a0954ec4ceb255e3e9778d41'), y
)
404 me
.assertEqual(C
.GF('4eeb684a0954ec4ceb255e3e9778d41', 16), y
)
405 me
.assertEqual(C
.GF('0b0', 16), C
.GF(176)) # not 0
407 me
.assertEqual(C
.GF('047353320450112516611472622536175135706501'), y
)
408 me
.assertEqual(C
.GF('0o47353320450112516611472622536175135706501'), y
)
409 me
.assertEqual(C
.GF('047353320450112516611472622536175135706501', 8), y
)
410 me
.assertEqual(C
.GF('47353320450112516611472622536175135706501', 8), y
)
413 me
.assertEqual(C
.GF('0b100111011011001100000010001011'), t
)
414 me
.assertEqual(C
.GF('100111011011001100000010001011', 2), t
)
417 y
= C
.GF(0x4eeb684a0954ec4ceb255e3e9778d41)
418 me
.assertEqual(str(y
), '0x4eeb684a0954ec4ceb255e3e9778d41')
419 me
.assertEqual(repr(y
), 'GF(0x4eeb684a0954ec4ceb255e3e9778d41)')
420 me
.assertEqual(hex(y
), '0x4eeb684a0954ec4ceb255e3e9778d41')
421 me
.assertEqual(oct(y
), T
.py23('0', '0o') +
422 '47353320450112516611472622536175135706501')
424 except NameError: pass
425 else: me
.assertEqual(bin(C
.GF(661438603)),
426 '0b100111011011001100000010001011')
429 x
, y
, m
, zero
= C
.GF(0xa9), C
.GF(0x18), C
.GF(0x11b), C
.GF(0)
431 me
.assertEqual(x
, -x
)
432 me
.assertEqual(abs(x
), x
)
434 me
.assertEqual(x
+ y
, C
.GF(0xb1))
435 me
.assertEqual(x
- y
, C
.GF(0xb1))
436 me
.assertEqual(x
*y
, C
.GF(0xfd8))
437 me
.assertEqual(x
&y
, C
.GF(0x8))
438 me
.assertEqual(x | y
, C
.GF(0xb9))
439 me
.assertEqual(x ^ y
, C
.GF(0xb1))
441 me
.assertEqual(x
<< 3, C
.GF(0x548))
442 me
.assertEqual(x
<< -2, C
.GF(0x2a))
443 me
.assertEqual(x
>> 2, C
.GF(0x2a))
444 me
.assertEqual(x
>> -3, C
.GF(0x548))
446 u
= x
/y
; me
.assertEqual((u
.numer
, u
.denom
), (C
.GF(0x67), C
.GF(0x8)))
447 me
.assertEqual(x
//y
, C
.GF(0xc))
448 me
.assertEqual(x
%y
, C
.GF(0x9))
449 me
.assertEqual(divmod(x
, y
), (C
.GF(0xc), C
.GF(0x9)))
450 me
.assertRaises(ZeroDivisionError, lambda: x
/zero
)
451 me
.assertRaises(ZeroDivisionError, lambda: x
//zero
)
452 me
.assertRaises(ZeroDivisionError, lambda: x
%zero
)
453 me
.assertRaises(ZeroDivisionError, divmod, x
, zero
)
455 me
.assertEqual(pow(x
, 24),
456 C
.GF(0x1000100000001010000010101000101010001000001))
457 me
.assertEqual(pow(x
, 24, m
), C
.GF(0x78))
458 me
.assertEqual(pow(x
, -24, m
), C
.GF(0xb6))
459 me
.assertRaises(ZeroDivisionError, pow, x
, -24, C
.GF(0x18))
465 x
, y
, z
= C
.GF(0xa9), C
.GF(0x18), C
.GF(0xb3)
466 me
.assertTrue(x
== x
)
467 me
.assertFalse(x
!= x
)
468 me
.assertFalse(x
== y
)
469 me
.assertTrue(x
!= y
)
471 me
.assertFalse(y
> x
)
472 me
.assertFalse(x
> x
)
473 me
.assertFalse(x
> z
)
474 me
.assertFalse(z
> x
)
475 me
.assertTrue(x
>= y
)
476 me
.assertFalse(y
>= x
)
477 me
.assertTrue(x
>= x
)
478 me
.assertTrue(x
>= z
)
479 me
.assertTrue(z
>= x
)
480 me
.assertFalse(x
<= y
)
481 me
.assertTrue(y
<= x
)
482 me
.assertTrue(x
<= x
)
483 me
.assertTrue(x
<= z
)
484 me
.assertTrue(z
<= x
)
485 me
.assertFalse(x
< y
)
487 me
.assertFalse(x
< x
)
488 me
.assertFalse(x
< z
)
489 me
.assertFalse(z
< x
)
492 x
, zero
= C
.GF(0xa9), C
.GF(0)
493 me
.assertTrue(x
.testbit(0))
494 me
.assertFalse(x
.testbit(1))
495 me
.assertFalse(x
.testbit(1000))
497 me
.assertEqual(x
.setbit(0), x
)
498 me
.assertEqual(x
.clearbit(0), C
.GF(0xa8))
499 me
.assertEqual(x
.setbit(1), C
.GF(0xab))
500 me
.assertEqual(x
.clearbit(1), x
)
502 me
.assertEqual(x
.nbits
, 8)
503 me
.assertEqual(x
.degree
, 7)
504 me
.assertEqual(zero
.nbits
, 0)
505 me
.assertEqual(zero
.degree
, -1)
507 def test_loadstore(me
):
508 x
= C
.GF(0x0123456789ab)
510 me
.assertEqual(x
.noctets
, 6)
512 me
.assertEqual(x
, C
.GF
.loadb(C
.bytes("0123456789ab")))
514 me
.assertEqual(x
.storeb(), C
.bytes("0123456789ab"))
515 me
.assertEqual(x
.storeb(3), C
.bytes("6789ab"))
516 me
.assertEqual(x
.storeb(8), C
.bytes("00000123456789ab"))
518 me
.assertEqual(x
, C
.GF
.loadl(C
.bytes("ab8967452301")))
520 me
.assertEqual(x
.storel(), C
.bytes("ab8967452301"))
521 me
.assertEqual(x
.storel(3), C
.bytes("ab8967"))
522 me
.assertEqual(x
.storel(8), C
.bytes("ab89674523010000"))
524 me
.assertEqual(x
.tobuf(), C
.bytes("00060123456789ab"))
525 me
.assertEqual((x
, T
.bin("abcd")),
526 C
.GF
.frombuf(C
.bytes("00060123456789ab61626364")))
528 def test_numbertheory(me
):
529 p
, x
, y
= C
.GF(0x11b), C
.GF(0xa9), C
.GF(0x18)
531 me
.assertEqual(x
.sqr(), C
.GF(0x4441))
533 me
.assertEqual(x
.gcd(y
), C
.GF(0x3))
534 me
.assertEqual(x
.gcdx(y
), (C
.GF(0x3), C
.GF(0x3), C
.GF(0x15)))
535 me
.assertEqual(p
.modinv(x
), C
.GF(0xc8))
537 me
.assertTrue(p
.irreduciblep())
538 me
.assertFalse(x
.irreduciblep())
540 ###--------------------------------------------------------------------------
541 class TestGFReduce (U
.TestCase
):
544 p
= C
.GF(0x87).setbit(128)
545 me
.assertTrue(p
.irreduciblep())
548 x
= C
.GF(0xce46b4c1d3a1523520b1bb6eb5c61883)
549 y
= C
.GF(0xb5b0b3566b8e03f4b4a2b1ac413f8566)
550 xy
= C
.GF(0x28e5b895c11b08edc2fe7e1be5694c64)
552 me
.assertEqual(m
.reduce(x
*y
), xy
)
553 me
.assertEqual(m
.trace(x
), 0)
554 me
.assertEqual(m
.trace(y
), 1)
555 me
.assertEqual(m
.sqrt(x
), C
.GF(0xa277ee4bf770e5974cf1e31b1ccb54a1))
556 me
.assertEqual(m
.halftrace(y
), C
.GF(0x9cea73e79ffd190dd3c81d33e58d8e6f))
557 me
.assertEqual(m
.quadsolve(x
), C
.GF(0x9664c09d23d168147a438de6a813c784))
559 ###--------------------------------------------------------------------------
560 class TestGFN (U
.TestCase
):
563 p
= C
.GF(0x87).setbit(128)
564 beta
= C
.GF(0xc50f387e37194d4a4b41e157a3e2b5e1)
565 y
= C
.GF(0xdaca76dc2578a63c788a2ce0fc7878f6)
566 yy
= C
.GF(0x298a98f955100f054fcee3433f96b00e)
567 zero
, one
, fff
= C
.GF(0), C
.GF(1), C
.GF(T
.long(2)**128 - 1)
568 me
.assertTrue(p
.irreduciblep())
571 me
.assertEqual(gfn
.p
, p
)
572 me
.assertEqual(gfn
.beta
, beta
)
573 me
.assertEqual(gfn
.pton(zero
), zero
)
574 me
.assertEqual(gfn
.ntop(zero
), zero
)
575 me
.assertEqual(gfn
.pton(one
), fff
)
576 me
.assertEqual(gfn
.ntop(fff
), one
)
577 me
.assertEqual(gfn
.pton(y
), yy
)
578 me
.assertEqual(gfn
.ntop(yy
), y
)
580 ## Doesn't generate a normal basis.
581 me
.assertRaises(ValueError, C
.GFN
, p
, y
)
583 ###----- That's all, folks --------------------------------------------------
585 if __name__
== "__main__": U
.main()