93a1e2f8970b381f23e7f289e6888066791d67d5
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
), '047353320450112516611472622536175135706501')
76 except NameError: pass
77 else: me
.assertEqual(bin(C
.MP(661438603)),
78 '0b100111011011001100000010001011')
81 x
, y
, m
, zero
= C
.MP(169), C
.MP(24), C
.MP(205), C
.MP(0)
83 me
.assertEqual(-x
, -169)
84 me
.assertEqual(~x
, -170)
85 me
.assertEqual(abs(x
), 169)
86 me
.assertEqual(abs(-x
), 169)
88 me
.assertEqual(x
+ y
, 193)
89 me
.assertEqual(x
- y
, 145)
90 me
.assertEqual(x
*y
, 4056)
91 me
.assertEqual(x
&y
, 8)
92 me
.assertEqual(x
&-y
, 168)
93 me
.assertEqual(x | y
, 185)
94 me
.assertEqual(x |
-y
, -23)
95 me
.assertEqual(x ^ y
, 177)
96 me
.assertEqual(x ^
-y
, -191)
98 me
.assertEqual(x
<< 3, 1352)
99 me
.assertEqual(x
<< -2, 42)
100 me
.assertEqual(x
>> 2, 42)
101 me
.assertEqual(x
>> -3, 1352)
102 me
.assertEqual(-x
<< 3, -1352)
103 me
.assertEqual(-x
>> 2, -43)
105 u
= x
/y
; me
.assertEqual((u
.numer
, u
.denom
), (169, 24))
106 me
.assertEqual(x
//y
, 7)
107 me
.assertEqual(x
%y
, 1)
108 me
.assertEqual(divmod(x
, y
), (7, 1))
109 me
.assertRaises(ZeroDivisionError, lambda: x
/zero
)
110 me
.assertRaises(ZeroDivisionError, lambda: x
//zero
)
111 me
.assertRaises(ZeroDivisionError, lambda: x
%zero
)
112 me
.assertRaises(ZeroDivisionError, divmod, x
, zero
)
114 me
.assertEqual(pow(x
, y
), 294632676319010105335586872991323185304149065116720321)
115 me
.assertEqual(pow(x
, y
, m
), 51)
116 me
.assertRaises(ValueError, pow, x
, -y
)
117 me
.assertEqual(pow(x
, -y
, m
), 201)
118 me
.assertRaises(ZeroDivisionError, pow, x
, -y
, 208)
124 x
, y
= C
.MP(169), C
.MP(24)
125 me
.assertTrue(x
== x
)
126 me
.assertFalse(x
!= x
)
127 me
.assertFalse(x
== y
)
128 me
.assertTrue(x
!= y
)
130 me
.assertFalse(y
> x
)
131 me
.assertFalse(x
> x
)
132 me
.assertTrue(x
>= y
)
133 me
.assertFalse(y
>= x
)
134 me
.assertTrue(x
>= x
)
135 me
.assertFalse(x
<= y
)
136 me
.assertTrue(y
<= x
)
137 me
.assertTrue(x
<= x
)
138 me
.assertFalse(x
< y
)
140 me
.assertFalse(x
< x
)
143 x
, y
= C
.MP(169), 24.0
144 for fn
in [T
.add
, T
.sub
, T
.mul
, T
.div
]:
145 me
.assertEqual(type(fn(x
, y
)), float)
146 me
.assertEqual(type(fn(y
, x
)), float)
147 me
.assertEqual(x
, 169.0)
148 me
.assertNotEqual(x
, 169.1)
149 me
.assertNotEqual(x
, 168.9)
150 me
.assertTrue(x
> 168.9)
151 me
.assertTrue(x
< 169.1)
153 while z
== z
+ 1: z
*= 2.0
154 me
.assertNotEqual(C
.MP(int(z
)) + 1, z
)
157 x
, y
, zero
= C
.MP(169), C
.MP(-24), C
.MP(0)
158 me
.assertTrue(x
.testbit(0))
159 me
.assertFalse(x
.testbit(1))
160 me
.assertFalse(x
.testbit(1000))
161 me
.assertFalse(y
.testbit(0))
162 me
.assertTrue(y
.testbit(3))
163 me
.assertTrue(y
.testbit(1000))
165 me
.assertEqual(x
.setbit(0), x
)
166 me
.assertEqual(x
.clearbit(0), 168)
167 me
.assertEqual(x
.setbit(1), 171)
168 me
.assertEqual(x
.clearbit(1), x
)
169 me
.assertEqual(y
.setbit(0), -23)
170 me
.assertEqual(y
.clearbit(0), y
)
171 me
.assertEqual(y
.setbit(3), y
)
172 me
.assertEqual(y
.clearbit(3), -32)
173 me
.assertEqual(y
.setbit(1000), y
)
175 me
.assertEqual(x
.nbits
, 8)
176 me
.assertEqual(y
.nbits
, 5)
177 me
.assertEqual(zero
.nbits
, 0)
179 def test_loadstore(me
):
180 x
= C
.MP(0x0123456789ab)
182 u
= C
.MP(0xfedcba9876)
184 me
.assertEqual(x
.noctets
, 6)
185 me
.assertEqual(x
.noctets2c
, 6)
186 me
.assertEqual(y
.noctets
, 6)
187 me
.assertEqual(y
.noctets2c
, 6)
188 me
.assertEqual(u
.noctets
, 5)
189 me
.assertEqual(u
.noctets2c
, 6)
191 me
.assertEqual(x
, C
.MP
.loadb(C
.bytes("0123456789ab")))
192 me
.assertEqual(x
, C
.MP
.loadb2c(C
.bytes("0123456789ab")))
193 me
.assertEqual(y
, C
.MP
.loadb2c(C
.bytes("fedcba987655")))
195 me
.assertEqual(x
.storeb(), C
.bytes("0123456789ab"))
196 me
.assertEqual(x
.storeb(3), C
.bytes("6789ab"))
197 me
.assertEqual(x
.storeb(8), C
.bytes("00000123456789ab"))
198 me
.assertEqual(x
.storeb2c(), C
.bytes("0123456789ab"))
199 me
.assertEqual(x
.storeb2c(3), C
.bytes("6789ab"))
200 me
.assertEqual(x
.storeb2c(8), C
.bytes("00000123456789ab"))
201 me
.assertEqual(u
.storeb2c(), C
.bytes("00fedcba9876"))
202 me
.assertEqual(y
.storeb2c(), C
.bytes("fedcba987655"))
203 me
.assertEqual(y
.storeb2c(3), C
.bytes("987655"))
204 me
.assertEqual(y
.storeb2c(8), C
.bytes("fffffedcba987655"))
206 me
.assertEqual(x
, C
.MP
.loadl(C
.bytes("ab8967452301")))
207 me
.assertEqual(x
, C
.MP
.loadl2c(C
.bytes("ab8967452301")))
208 me
.assertEqual(y
, C
.MP
.loadl2c(C
.bytes("557698badcfe")))
210 me
.assertEqual(x
.storel(), C
.bytes("ab8967452301"))
211 me
.assertEqual(x
.storel(3), C
.bytes("ab8967"))
212 me
.assertEqual(x
.storel(8), C
.bytes("ab89674523010000"))
213 me
.assertEqual(x
.storel2c(), C
.bytes("ab8967452301"))
214 me
.assertEqual(x
.storel2c(3), C
.bytes("ab8967"))
215 me
.assertEqual(x
.storel2c(8), C
.bytes("ab89674523010000"))
216 me
.assertEqual(u
.storel2c(), C
.bytes("7698badcfe00"))
217 me
.assertEqual(y
.storel2c(), C
.bytes("557698badcfe"))
218 me
.assertEqual(y
.storel2c(3), C
.bytes("557698"))
219 me
.assertEqual(y
.storel2c(8), C
.bytes("557698badcfeffff"))
221 me
.assertEqual(x
.tobuf(), C
.bytes("00060123456789ab"))
222 me
.assertEqual((x
, T
.bin("abcd")),
223 C
.MP
.frombuf(C
.bytes("00060123456789ab61626364")))
225 def test_numbertheory(me
):
226 p
, x
, y
, z
= C
.MP(173), C
.MP(169), C
.MP(24), C
.MP(20)
228 me
.assertEqual(x
.odd(), (0, x
))
229 me
.assertEqual(y
.odd(), (3, 3))
231 me
.assertEqual(x
.sqr(), 28561)
232 me
.assertEqual(x
.sqrt(), 13)
233 me
.assertEqual(y
.sqrt(), 4)
235 me
.assertEqual(x
.gcd(y
), 1)
236 me
.assertEqual(x
.gcdx(y
), (1, -23, 162))
237 me
.assertEqual(y
.gcdx(x
), (1, -7, 1))
238 me
.assertEqual(x
.modinv(y
), 162)
239 me
.assertEqual(y
.modinv(x
), 1)
241 me
.assertEqual(x
.jacobi(y
), 1)
242 me
.assertEqual(x
.jacobi(13), 0)
243 me
.assertEqual(y
.jacobi(x
), 1)
244 me
.assertEqual(p
.jacobi(y
), 1)
245 me
.assertEqual(p
.jacobi(z
), -1)
246 me
.assertEqual(p
.modsqrt(y
), 71)
247 me
.assertRaises(ValueError, p
.modsqrt
, z
)
249 me
.assertEqual(y
.leastcongruent(x
, 32), 184)
251 me
.assertTrue(p
.primep())
252 me
.assertFalse(x
.primep())
255 me
.assertEqual(C
.MP
.factorial(0), 1)
258 30414093201713378043612608166064768844377641568960512000000000000)
259 me
.assertRaises((ValueError, OverflowError), C
.MP
.factorial
, -1)
262 me
.assertEqual(C
.MP
.fibonacci(-2), -1)
263 me
.assertEqual(C
.MP
.fibonacci(-1), +1)
264 me
.assertEqual(C
.MP
.fibonacci( 0), 0)
265 me
.assertEqual(C
.MP
.fibonacci(+1), +1)
266 me
.assertEqual(C
.MP
.fibonacci(+2), +1)
267 me
.assertEqual(C
.MP
.fibonacci(50), 12586269025)
269 ###--------------------------------------------------------------------------
270 class TestMPMul (U
.TestCase
):
274 me
.assertTrue(m
.livep
)
277 me
.assertEqual(m
.done(), 720)
278 me
.assertFalse(m
.livep
)
280 me
.assertEqual(C
.MPMul(T
.range(1, 7)).done(), 720)
281 me
.assertEqual(C
.MP
.factorial(6), 720)
283 ###--------------------------------------------------------------------------
284 class TestMPMont (U
.TestCase
):
288 me
.assertRaises(ValueError,
289 C
.MPMont
, 35315021952044908656941308411353985942)
290 me
.assertRaises(ValueError, C
.MPMont
, -9)
292 p
= C
.MP(269464705320809171350781605680038324101)
293 g
= C
.MP(2) # lucky chance
294 x
= C
.MP(211184293914316080585277908844600399612)
295 y
= C
.MP(154454671298730680774195646814344206562)
296 xy
= C
.MP(209444562478584646216087606217820187655)
297 me
.assertTrue(p
.primep())
299 me
.assertEqual(m
.m
, p
)
301 ## The precise values of m.r and m.r2 are dependent on the internal
302 ## bignum representation. But we expect m.r to be congruent to some
303 ## power of two. (It should be 2^128.)
305 for i
in T
.range(1025):
310 me
.fail("m.r is not a small-ish power of 2")
311 me
.assertEqual(m
.r2
, pow(2, 2*i
, p
))
312 me
.assertEqual(m
.ext(m
.r
), 1)
313 me
.assertEqual(m
.reduce(m
.r
), 1)
315 me
.assertEqual(m
.ext(m
.int(x
)), x
)
316 me
.assertEqual(m
.int(x
), m
.mul(x
, m
.r2
))
317 me
.assertEqual(m
.mul(m
.int(x
), y
), xy
)
318 me
.assertEqual(m
.ext(m
.mul(m
.int(x
), m
.int(y
))), xy
)
320 me
.assertEqual(m
.exp(2, p
- 1), 1)
321 me
.assertEqual(m
.expr(m
.int(2), p
- 1), m
.r
)
323 q
, r
, s
, z
= 32, 128, 2048, pow(g
, 156, p
)
324 me
.assertEqual(m
.mexp([(q
, 9), (r
, 8), (s
, 5)]), z
)
325 me
.assertEqual(m
.mexp(q
, 9, r
, 8, s
, 5), z
)
327 q
, r
, s
, z
= T
.imap(m
.int, [32, 128, 2048, pow(g
, 156, p
)])
328 me
.assertEqual(m
.mexpr([(q
, 9), (r
, 8), (s
, 5)]), z
)
329 me
.assertEqual(m
.mexpr(q
, 9, r
, 8, s
, 5), z
)
331 ###--------------------------------------------------------------------------
332 class TestMPBarrett (U
.TestCase
):
336 p
= C
.MP(269464705320809171350781605680038324101)
337 g
= C
.MP(2) # lucky chance
338 x
= C
.MP(211184293914316080585277908844600399612)
339 y
= C
.MP(154454671298730680774195646814344206562)
340 xy
= C
.MP(209444562478584646216087606217820187655)
341 me
.assertTrue(p
.primep())
343 me
.assertEqual(m
.m
, p
)
345 me
.assertEqual(m
.reduce(x
*y
), xy
)
347 me
.assertEqual(m
.exp(2, p
- 1), 1)
349 q
, r
, s
, z
= 32, 128, 2048, pow(g
, 156, p
)
350 me
.assertEqual(m
.mexp([(q
, 9), (r
, 8), (s
, 5)]), z
)
351 me
.assertEqual(m
.mexp(q
, 9, r
, 8, s
, 5), z
)
353 ###--------------------------------------------------------------------------
354 class TestMPReduce (U
.TestCase
):
359 g
= C
.MP(2) # lucky chance
360 x
= C
.MP(94827182170881245766374991987593163418)
361 y
= C
.MP(106025009945795266831396608563402138277)
362 xy
= C
.MP(80027041045616838298103413933629021123)
363 me
.assertTrue(p
.primep())
365 me
.assertEqual(m
.m
, p
)
367 me
.assertEqual(m
.reduce(x
*y
), xy
)
369 me
.assertEqual(m
.exp(2, 127), 1)
371 ###--------------------------------------------------------------------------
372 class TestMPCRT (U
.TestCase
):
376 c
= C
.MPCRT(5, 7, 11)
377 me
.assertEqual(c
.moduli
, [5, 7, 11])
378 me
.assertEqual(c
.product
, 385)
379 me
.assertEqual(c
.solve([2, 3, 4]), 367)
380 me
.assertEqual(c
.solve([2, -4, -7]), 367)
382 me
.assertRaises(ValueError, C
.MPCRT
, [6, 15, 35])
384 ###--------------------------------------------------------------------------
385 class TestGF (U
.TestCase
):
390 kk
= C
.BinPolyField(C
.GF(0x13))
392 me
.assertTrue(C
.GF(x
) is x
)
393 me
.assertEqual(C
.GF(k(8)), C
.GF(8))
394 me
.assertEqual(C
.GF(kk(8)), C
.GF(8))
395 me
.assertEqual(C
.GF(E(1, 4)), C
.GF(1))
396 me
.assertRaises(TypeError, C
.GF
, E())
398 me
.assertEqual(int(x
), 5)
399 y
= C
.GF(0x4eeb684a0954ec4ceb255e3e9778d41)
400 me
.assertEqual(type(int(y
)), T
.long)
402 me
.assertEqual(C
.GF('0x4eeb684a0954ec4ceb255e3e9778d41'), y
)
403 me
.assertEqual(C
.GF('4eeb684a0954ec4ceb255e3e9778d41', 16), y
)
404 me
.assertEqual(C
.GF('0b0', 16), C
.GF(176)) # not 0
406 me
.assertEqual(C
.GF('047353320450112516611472622536175135706501'), y
)
407 me
.assertEqual(C
.GF('0o47353320450112516611472622536175135706501'), y
)
408 me
.assertEqual(C
.GF('047353320450112516611472622536175135706501', 8), y
)
409 me
.assertEqual(C
.GF('47353320450112516611472622536175135706501', 8), y
)
412 me
.assertEqual(C
.GF('0b100111011011001100000010001011'), t
)
413 me
.assertEqual(C
.GF('100111011011001100000010001011', 2), t
)
416 y
= C
.GF(0x4eeb684a0954ec4ceb255e3e9778d41)
417 me
.assertEqual(str(y
), '0x4eeb684a0954ec4ceb255e3e9778d41')
418 me
.assertEqual(repr(y
), 'GF(0x4eeb684a0954ec4ceb255e3e9778d41)')
419 me
.assertEqual(hex(y
), '0x4eeb684a0954ec4ceb255e3e9778d41')
420 me
.assertEqual(oct(y
), '047353320450112516611472622536175135706501')
422 except NameError: pass
423 else: me
.assertEqual(bin(C
.GF(661438603)),
424 '0b100111011011001100000010001011')
427 x
, y
, m
, zero
= C
.GF(0xa9), C
.GF(0x18), C
.GF(0x11b), C
.GF(0)
429 me
.assertEqual(x
, -x
)
430 me
.assertEqual(abs(x
), x
)
432 me
.assertEqual(x
+ y
, C
.GF(0xb1))
433 me
.assertEqual(x
- y
, C
.GF(0xb1))
434 me
.assertEqual(x
*y
, C
.GF(0xfd8))
435 me
.assertEqual(x
&y
, C
.GF(0x8))
436 me
.assertEqual(x | y
, C
.GF(0xb9))
437 me
.assertEqual(x ^ y
, C
.GF(0xb1))
439 me
.assertEqual(x
<< 3, C
.GF(0x548))
440 me
.assertEqual(x
<< -2, C
.GF(0x2a))
441 me
.assertEqual(x
>> 2, C
.GF(0x2a))
442 me
.assertEqual(x
>> -3, C
.GF(0x548))
444 u
= x
/y
; me
.assertEqual((u
.numer
, u
.denom
), (C
.GF(0x67), C
.GF(0x8)))
445 me
.assertEqual(x
//y
, C
.GF(0xc))
446 me
.assertEqual(x
%y
, C
.GF(0x9))
447 me
.assertEqual(divmod(x
, y
), (C
.GF(0xc), C
.GF(0x9)))
448 me
.assertRaises(ZeroDivisionError, lambda: x
/zero
)
449 me
.assertRaises(ZeroDivisionError, lambda: x
//zero
)
450 me
.assertRaises(ZeroDivisionError, lambda: x
%zero
)
451 me
.assertRaises(ZeroDivisionError, divmod, x
, zero
)
453 me
.assertEqual(pow(x
, 24),
454 C
.GF(0x1000100000001010000010101000101010001000001))
455 me
.assertEqual(pow(x
, 24, m
), C
.GF(0x78))
456 me
.assertEqual(pow(x
, -24, m
), C
.GF(0xb6))
457 me
.assertRaises(ZeroDivisionError, pow, x
, -24, C
.GF(0x18))
463 x
, y
, z
= C
.GF(0xa9), C
.GF(0x18), C
.GF(0xb3)
464 me
.assertTrue(x
== x
)
465 me
.assertFalse(x
!= x
)
466 me
.assertFalse(x
== y
)
467 me
.assertTrue(x
!= y
)
469 me
.assertFalse(y
> x
)
470 me
.assertFalse(x
> x
)
471 me
.assertFalse(x
> z
)
472 me
.assertFalse(z
> x
)
473 me
.assertTrue(x
>= y
)
474 me
.assertFalse(y
>= x
)
475 me
.assertTrue(x
>= x
)
476 me
.assertTrue(x
>= z
)
477 me
.assertTrue(z
>= x
)
478 me
.assertFalse(x
<= y
)
479 me
.assertTrue(y
<= x
)
480 me
.assertTrue(x
<= x
)
481 me
.assertTrue(x
<= z
)
482 me
.assertTrue(z
<= x
)
483 me
.assertFalse(x
< y
)
485 me
.assertFalse(x
< x
)
486 me
.assertFalse(x
< z
)
487 me
.assertFalse(z
< x
)
490 x
, zero
= C
.GF(0xa9), C
.GF(0)
491 me
.assertTrue(x
.testbit(0))
492 me
.assertFalse(x
.testbit(1))
493 me
.assertFalse(x
.testbit(1000))
495 me
.assertEqual(x
.setbit(0), x
)
496 me
.assertEqual(x
.clearbit(0), C
.GF(0xa8))
497 me
.assertEqual(x
.setbit(1), C
.GF(0xab))
498 me
.assertEqual(x
.clearbit(1), x
)
500 me
.assertEqual(x
.nbits
, 8)
501 me
.assertEqual(x
.degree
, 7)
502 me
.assertEqual(zero
.nbits
, 0)
503 me
.assertEqual(zero
.degree
, -1)
505 def test_loadstore(me
):
506 x
= C
.GF(0x0123456789ab)
508 me
.assertEqual(x
.noctets
, 6)
510 me
.assertEqual(x
, C
.GF
.loadb(C
.bytes("0123456789ab")))
512 me
.assertEqual(x
.storeb(), C
.bytes("0123456789ab"))
513 me
.assertEqual(x
.storeb(3), C
.bytes("6789ab"))
514 me
.assertEqual(x
.storeb(8), C
.bytes("00000123456789ab"))
516 me
.assertEqual(x
, C
.GF
.loadl(C
.bytes("ab8967452301")))
518 me
.assertEqual(x
.storel(), C
.bytes("ab8967452301"))
519 me
.assertEqual(x
.storel(3), C
.bytes("ab8967"))
520 me
.assertEqual(x
.storel(8), C
.bytes("ab89674523010000"))
522 me
.assertEqual(x
.tobuf(), C
.bytes("00060123456789ab"))
523 me
.assertEqual((x
, T
.bin("abcd")),
524 C
.GF
.frombuf(C
.bytes("00060123456789ab61626364")))
526 def test_numbertheory(me
):
527 p
, x
, y
= C
.GF(0x11b), C
.GF(0xa9), C
.GF(0x18)
529 me
.assertEqual(x
.sqr(), C
.GF(0x4441))
531 me
.assertEqual(x
.gcd(y
), C
.GF(0x3))
532 me
.assertEqual(x
.gcdx(y
), (C
.GF(0x3), C
.GF(0x3), C
.GF(0x15)))
533 me
.assertEqual(p
.modinv(x
), C
.GF(0xc8))
535 me
.assertTrue(p
.irreduciblep())
536 me
.assertFalse(x
.irreduciblep())
538 ###--------------------------------------------------------------------------
539 class TestGFReduce (U
.TestCase
):
542 p
= C
.GF(0x87).setbit(128)
543 me
.assertTrue(p
.irreduciblep())
546 x
= C
.GF(0xce46b4c1d3a1523520b1bb6eb5c61883)
547 y
= C
.GF(0xb5b0b3566b8e03f4b4a2b1ac413f8566)
548 xy
= C
.GF(0x28e5b895c11b08edc2fe7e1be5694c64)
550 me
.assertEqual(m
.reduce(x
*y
), xy
)
551 me
.assertEqual(m
.trace(x
), 0)
552 me
.assertEqual(m
.trace(y
), 1)
553 me
.assertEqual(m
.sqrt(x
), C
.GF(0xa277ee4bf770e5974cf1e31b1ccb54a1))
554 me
.assertEqual(m
.halftrace(y
), C
.GF(0x9cea73e79ffd190dd3c81d33e58d8e6f))
555 me
.assertEqual(m
.quadsolve(x
), C
.GF(0x9664c09d23d168147a438de6a813c784))
557 ###--------------------------------------------------------------------------
558 class TestGFN (U
.TestCase
):
561 p
= C
.GF(0x87).setbit(128)
562 beta
= C
.GF(0xc50f387e37194d4a4b41e157a3e2b5e1)
563 y
= C
.GF(0xdaca76dc2578a63c788a2ce0fc7878f6)
564 yy
= C
.GF(0x298a98f955100f054fcee3433f96b00e)
565 zero
, one
, fff
= C
.GF(0), C
.GF(1), C
.GF(T
.long(2)**128 - 1)
566 me
.assertTrue(p
.irreduciblep())
569 me
.assertEqual(gfn
.p
, p
)
570 me
.assertEqual(gfn
.beta
, beta
)
571 me
.assertEqual(gfn
.pton(zero
), zero
)
572 me
.assertEqual(gfn
.ntop(zero
), zero
)
573 me
.assertEqual(gfn
.pton(one
), fff
)
574 me
.assertEqual(gfn
.ntop(fff
), one
)
575 me
.assertEqual(gfn
.pton(y
), yy
)
576 me
.assertEqual(gfn
.ntop(yy
), y
)
578 ## Doesn't generate a normal basis.
579 me
.assertRaises(ValueError, C
.GFN
, p
, y
)
581 ###----- That's all, folks --------------------------------------------------
583 if __name__
== "__main__": U
.main()