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(6556380541834372447694561492436749633L)')
73 me
.assertEqual(hex(y
), '0x4eeb684a0954ec4ceb255e3e9778d41')
74 me
.assertEqual(oct(y
), '047353320450112516611472622536175135706501')
77 x
, y
, m
, zero
= C
.MP(169), C
.MP(24), C
.MP(205), C
.MP(0)
79 me
.assertEqual(-x
, -169)
80 me
.assertEqual(~x
, -170)
81 me
.assertEqual(abs(x
), 169)
82 me
.assertEqual(abs(-x
), 169)
84 me
.assertEqual(x
+ y
, 193)
85 me
.assertEqual(x
- y
, 145)
86 me
.assertEqual(x
*y
, 4056)
87 me
.assertEqual(x
&y
, 8)
88 me
.assertEqual(x
&-y
, 168)
89 me
.assertEqual(x | y
, 185)
90 me
.assertEqual(x |
-y
, -23)
91 me
.assertEqual(x ^ y
, 177)
92 me
.assertEqual(x ^
-y
, -191)
94 me
.assertEqual(x
<< 3, 1352)
95 me
.assertEqual(x
<< -2, 42)
96 me
.assertEqual(x
>> 2, 42)
97 me
.assertEqual(x
>> -3, 1352)
98 me
.assertEqual(-x
<< 3, -1352)
99 me
.assertEqual(-x
>> 2, -43)
101 u
= x
/y
; me
.assertEqual((u
.numer
, u
.denom
), (169, 24))
102 me
.assertEqual(x
//y
, 7)
103 me
.assertEqual(x
%y
, 1)
104 me
.assertEqual(divmod(x
, y
), (7, 1))
105 me
.assertRaises(ZeroDivisionError, lambda: x
/zero
)
106 me
.assertRaises(ZeroDivisionError, lambda: x
//zero
)
107 me
.assertRaises(ZeroDivisionError, lambda: x
%zero
)
108 me
.assertRaises(ZeroDivisionError, divmod, x
, zero
)
110 me
.assertEqual(pow(x
, y
), 294632676319010105335586872991323185304149065116720321)
111 me
.assertEqual(pow(x
, y
, m
), 51)
112 me
.assertRaises(ValueError, pow, x
, -y
)
113 me
.assertEqual(pow(x
, -y
, m
), 201)
114 me
.assertRaises(ZeroDivisionError, pow, x
, -y
, 208)
120 x
, y
= C
.MP(169), C
.MP(24)
121 me
.assertTrue(x
== x
)
122 me
.assertFalse(x
!= x
)
123 me
.assertFalse(x
== y
)
124 me
.assertTrue(x
!= y
)
126 me
.assertFalse(y
> x
)
127 me
.assertFalse(x
> x
)
128 me
.assertTrue(x
>= y
)
129 me
.assertFalse(y
>= x
)
130 me
.assertTrue(x
>= x
)
131 me
.assertFalse(x
<= y
)
132 me
.assertTrue(y
<= x
)
133 me
.assertTrue(x
<= x
)
134 me
.assertFalse(x
< y
)
136 me
.assertFalse(x
< x
)
139 x
, y
= C
.MP(169), 24.0
140 for fn
in [T
.add
, T
.sub
, T
.mul
, T
.div
]:
141 me
.assertEqual(type(fn(x
, y
)), float)
142 me
.assertEqual(type(fn(y
, x
)), float)
143 me
.assertEqual(x
, 169.0)
144 me
.assertNotEqual(x
, 169.1)
145 me
.assertNotEqual(x
, 168.9)
146 me
.assertTrue(x
> 168.9)
147 me
.assertTrue(x
< 169.1)
149 while z
== z
+ 1: z
*= 2.0
150 me
.assertNotEqual(C
.MP(int(z
)) + 1, z
)
153 x
, y
, zero
= C
.MP(169), C
.MP(-24), C
.MP(0)
154 me
.assertTrue(x
.testbit(0))
155 me
.assertFalse(x
.testbit(1))
156 me
.assertFalse(x
.testbit(1000))
157 me
.assertFalse(y
.testbit(0))
158 me
.assertTrue(y
.testbit(3))
159 me
.assertTrue(y
.testbit(1000))
161 me
.assertEqual(x
.setbit(0), x
)
162 me
.assertEqual(x
.clearbit(0), 168)
163 me
.assertEqual(x
.setbit(1), 171)
164 me
.assertEqual(x
.clearbit(1), x
)
165 me
.assertEqual(y
.setbit(0), -23)
166 me
.assertEqual(y
.clearbit(0), y
)
167 me
.assertEqual(y
.setbit(3), y
)
168 me
.assertEqual(y
.clearbit(3), -32)
169 me
.assertEqual(y
.setbit(1000), y
)
171 me
.assertEqual(x
.nbits
, 8)
172 me
.assertEqual(y
.nbits
, 5)
173 me
.assertEqual(zero
.nbits
, 0)
175 def test_loadstore(me
):
176 x
= C
.MP(0x0123456789ab)
178 u
= C
.MP(0xfedcba9876)
180 me
.assertEqual(x
.noctets
, 6)
181 me
.assertEqual(x
.noctets2c
, 6)
182 me
.assertEqual(y
.noctets
, 6)
183 me
.assertEqual(y
.noctets2c
, 6)
184 me
.assertEqual(u
.noctets
, 5)
185 me
.assertEqual(u
.noctets2c
, 6)
187 me
.assertEqual(x
, C
.MP
.loadb(C
.bytes("0123456789ab")))
188 me
.assertEqual(x
, C
.MP
.loadb2c(C
.bytes("0123456789ab")))
189 me
.assertEqual(y
, C
.MP
.loadb2c(C
.bytes("fedcba987655")))
191 me
.assertEqual(x
.storeb(), C
.bytes("0123456789ab"))
192 me
.assertEqual(x
.storeb(3), C
.bytes("6789ab"))
193 me
.assertEqual(x
.storeb(8), C
.bytes("00000123456789ab"))
194 me
.assertEqual(x
.storeb2c(), C
.bytes("0123456789ab"))
195 me
.assertEqual(x
.storeb2c(3), C
.bytes("6789ab"))
196 me
.assertEqual(x
.storeb2c(8), C
.bytes("00000123456789ab"))
197 me
.assertEqual(u
.storeb2c(), C
.bytes("00fedcba9876"))
198 me
.assertEqual(y
.storeb2c(), C
.bytes("fedcba987655"))
199 me
.assertEqual(y
.storeb2c(3), C
.bytes("987655"))
200 me
.assertEqual(y
.storeb2c(8), C
.bytes("fffffedcba987655"))
202 me
.assertEqual(x
, C
.MP
.loadl(C
.bytes("ab8967452301")))
203 me
.assertEqual(x
, C
.MP
.loadl2c(C
.bytes("ab8967452301")))
204 me
.assertEqual(y
, C
.MP
.loadl2c(C
.bytes("557698badcfe")))
206 me
.assertEqual(x
.storel(), C
.bytes("ab8967452301"))
207 me
.assertEqual(x
.storel(3), C
.bytes("ab8967"))
208 me
.assertEqual(x
.storel(8), C
.bytes("ab89674523010000"))
209 me
.assertEqual(x
.storel2c(), C
.bytes("ab8967452301"))
210 me
.assertEqual(x
.storel2c(3), C
.bytes("ab8967"))
211 me
.assertEqual(x
.storel2c(8), C
.bytes("ab89674523010000"))
212 me
.assertEqual(u
.storel2c(), C
.bytes("7698badcfe00"))
213 me
.assertEqual(y
.storel2c(), C
.bytes("557698badcfe"))
214 me
.assertEqual(y
.storel2c(3), C
.bytes("557698"))
215 me
.assertEqual(y
.storel2c(8), C
.bytes("557698badcfeffff"))
217 me
.assertEqual(x
.tobuf(), C
.bytes("00060123456789ab"))
218 me
.assertEqual((x
, T
.bin("abcd")),
219 C
.MP
.frombuf(C
.bytes("00060123456789ab61626364")))
221 def test_numbertheory(me
):
222 p
, x
, y
, z
= C
.MP(173), C
.MP(169), C
.MP(24), C
.MP(20)
224 me
.assertEqual(x
.odd(), (0, x
))
225 me
.assertEqual(y
.odd(), (3, 3))
227 me
.assertEqual(x
.sqr(), 28561)
228 me
.assertEqual(x
.sqrt(), 13)
229 me
.assertEqual(y
.sqrt(), 4)
231 me
.assertEqual(x
.gcd(y
), 1)
232 me
.assertEqual(x
.gcdx(y
), (1, -23, 162))
233 me
.assertEqual(y
.gcdx(x
), (1, -7, 1))
234 me
.assertEqual(x
.modinv(y
), 162)
235 me
.assertEqual(y
.modinv(x
), 1)
237 me
.assertEqual(x
.jacobi(y
), 1)
238 me
.assertEqual(x
.jacobi(13), 0)
239 me
.assertEqual(y
.jacobi(x
), 1)
240 me
.assertEqual(p
.jacobi(y
), 1)
241 me
.assertEqual(p
.jacobi(z
), -1)
242 me
.assertEqual(p
.modsqrt(y
), 71)
243 me
.assertRaises(ValueError, p
.modsqrt
, z
)
245 me
.assertEqual(y
.leastcongruent(x
, 32), 184)
247 me
.assertTrue(p
.primep())
248 me
.assertFalse(x
.primep())
251 me
.assertEqual(C
.MP
.factorial(0), 1)
254 30414093201713378043612608166064768844377641568960512000000000000)
255 me
.assertRaises((ValueError, OverflowError), C
.MP
.factorial
, -1)
258 me
.assertEqual(C
.MP
.fibonacci(-2), -1)
259 me
.assertEqual(C
.MP
.fibonacci(-1), +1)
260 me
.assertEqual(C
.MP
.fibonacci( 0), 0)
261 me
.assertEqual(C
.MP
.fibonacci(+1), +1)
262 me
.assertEqual(C
.MP
.fibonacci(+2), +1)
263 me
.assertEqual(C
.MP
.fibonacci(50), 12586269025)
265 ###--------------------------------------------------------------------------
266 class TestMPMul (U
.TestCase
):
270 me
.assertTrue(m
.livep
)
273 me
.assertEqual(m
.done(), 720)
274 me
.assertFalse(m
.livep
)
276 me
.assertEqual(C
.MPMul(T
.range(1, 7)).done(), 720)
277 me
.assertEqual(C
.MP
.factorial(6), 720)
279 ###--------------------------------------------------------------------------
280 class TestMPMont (U
.TestCase
):
284 me
.assertRaises(ValueError,
285 C
.MPMont
, 35315021952044908656941308411353985942)
286 me
.assertRaises(ValueError, C
.MPMont
, -9)
288 p
= C
.MP(269464705320809171350781605680038324101)
289 g
= C
.MP(2) # lucky chance
290 x
= C
.MP(211184293914316080585277908844600399612)
291 y
= C
.MP(154454671298730680774195646814344206562)
292 xy
= C
.MP(209444562478584646216087606217820187655)
293 me
.assertTrue(p
.primep())
295 me
.assertEqual(m
.m
, p
)
297 ## The precise values of m.r and m.r2 are dependent on the internal
298 ## bignum representation. But we expect m.r to be congruent to some
299 ## power of two. (It should be 2^128.)
301 for i
in T
.range(1025):
306 me
.fail("m.r is not a small-ish power of 2")
307 me
.assertEqual(m
.r2
, pow(2, 2*i
, p
))
308 me
.assertEqual(m
.ext(m
.r
), 1)
309 me
.assertEqual(m
.reduce(m
.r
), 1)
311 me
.assertEqual(m
.ext(m
.int(x
)), x
)
312 me
.assertEqual(m
.int(x
), m
.mul(x
, m
.r2
))
313 me
.assertEqual(m
.mul(m
.int(x
), y
), xy
)
314 me
.assertEqual(m
.ext(m
.mul(m
.int(x
), m
.int(y
))), xy
)
316 me
.assertEqual(m
.exp(2, p
- 1), 1)
317 me
.assertEqual(m
.expr(m
.int(2), p
- 1), m
.r
)
319 q
, r
, s
, z
= 32, 128, 2048, pow(g
, 156, p
)
320 me
.assertEqual(m
.mexp([(q
, 9), (r
, 8), (s
, 5)]), z
)
321 me
.assertEqual(m
.mexp(q
, 9, r
, 8, s
, 5), z
)
323 q
, r
, s
, z
= T
.imap(m
.int, [32, 128, 2048, pow(g
, 156, p
)])
324 me
.assertEqual(m
.mexpr([(q
, 9), (r
, 8), (s
, 5)]), z
)
325 me
.assertEqual(m
.mexpr(q
, 9, r
, 8, s
, 5), z
)
327 ###--------------------------------------------------------------------------
328 class TestMPBarrett (U
.TestCase
):
332 p
= C
.MP(269464705320809171350781605680038324101)
333 g
= C
.MP(2) # lucky chance
334 x
= C
.MP(211184293914316080585277908844600399612)
335 y
= C
.MP(154454671298730680774195646814344206562)
336 xy
= C
.MP(209444562478584646216087606217820187655)
337 me
.assertTrue(p
.primep())
339 me
.assertEqual(m
.m
, p
)
341 me
.assertEqual(m
.reduce(x
*y
), xy
)
343 me
.assertEqual(m
.exp(2, p
- 1), 1)
345 q
, r
, s
, z
= 32, 128, 2048, pow(g
, 156, p
)
346 me
.assertEqual(m
.mexp([(q
, 9), (r
, 8), (s
, 5)]), z
)
347 me
.assertEqual(m
.mexp(q
, 9, r
, 8, s
, 5), z
)
349 ###--------------------------------------------------------------------------
350 class TestMPReduce (U
.TestCase
):
355 g
= C
.MP(2) # lucky chance
356 x
= C
.MP(94827182170881245766374991987593163418)
357 y
= C
.MP(106025009945795266831396608563402138277)
358 xy
= C
.MP(80027041045616838298103413933629021123)
359 me
.assertTrue(p
.primep())
361 me
.assertEqual(m
.m
, p
)
363 me
.assertEqual(m
.reduce(x
*y
), xy
)
365 me
.assertEqual(m
.exp(2, 127), 1)
367 ###--------------------------------------------------------------------------
368 class TestMPCRT (U
.TestCase
):
372 c
= C
.MPCRT(5, 7, 11)
373 me
.assertEqual(c
.moduli
, [5, 7, 11])
374 me
.assertEqual(c
.product
, 385)
375 me
.assertEqual(c
.solve([2, 3, 4]), 367)
376 me
.assertEqual(c
.solve([2, -4, -7]), 367)
378 me
.assertRaises(ValueError, C
.MPCRT
, [6, 15, 35])
380 ###--------------------------------------------------------------------------
381 class TestGF (U
.TestCase
):
386 kk
= C
.BinPolyField(C
.GF(0x13))
388 me
.assertTrue(C
.GF(x
) is x
)
389 me
.assertEqual(C
.GF(k(8)), C
.GF(8))
390 me
.assertEqual(C
.GF(kk(8)), C
.GF(8))
391 me
.assertEqual(C
.GF(E(1, 4)), C
.GF(1))
392 me
.assertRaises(TypeError, C
.GF
, E())
394 me
.assertEqual(int(x
), 5)
395 y
= C
.GF(0x4eeb684a0954ec4ceb255e3e9778d41)
396 me
.assertEqual(type(int(y
)), T
.long)
398 me
.assertEqual(C
.GF('0x4eeb684a0954ec4ceb255e3e9778d41'), y
)
399 me
.assertEqual(C
.GF('4eeb684a0954ec4ceb255e3e9778d41', 16), y
)
400 me
.assertEqual(C
.GF('0b0', 16), C
.GF(176)) # not 0
402 me
.assertEqual(C
.GF('047353320450112516611472622536175135706501'), y
)
403 me
.assertEqual(C
.GF('0o47353320450112516611472622536175135706501'), y
)
404 me
.assertEqual(C
.GF('047353320450112516611472622536175135706501', 8), y
)
405 me
.assertEqual(C
.GF('47353320450112516611472622536175135706501', 8), y
)
408 me
.assertEqual(C
.GF('0b100111011011001100000010001011'), t
)
409 me
.assertEqual(C
.GF('100111011011001100000010001011', 2), t
)
412 y
= C
.GF(0x4eeb684a0954ec4ceb255e3e9778d41)
413 me
.assertEqual(str(y
), '0x4eeb684a0954ec4ceb255e3e9778d41')
414 me
.assertEqual(repr(y
), 'GF(0x4eeb684a0954ec4ceb255e3e9778d41L)')
415 me
.assertEqual(hex(y
), '0x4eeb684a0954ec4ceb255e3e9778d41')
416 me
.assertEqual(oct(y
), '047353320450112516611472622536175135706501')
419 x
, y
, m
, zero
= C
.GF(0xa9), C
.GF(0x18), C
.GF(0x11b), C
.GF(0)
421 me
.assertEqual(x
, -x
)
422 me
.assertEqual(abs(x
), x
)
424 me
.assertEqual(x
+ y
, C
.GF(0xb1))
425 me
.assertEqual(x
- y
, C
.GF(0xb1))
426 me
.assertEqual(x
*y
, C
.GF(0xfd8))
427 me
.assertEqual(x
&y
, C
.GF(0x8))
428 me
.assertEqual(x | y
, C
.GF(0xb9))
429 me
.assertEqual(x ^ y
, C
.GF(0xb1))
431 me
.assertEqual(x
<< 3, C
.GF(0x548))
432 me
.assertEqual(x
<< -2, C
.GF(0x2a))
433 me
.assertEqual(x
>> 2, C
.GF(0x2a))
434 me
.assertEqual(x
>> -3, C
.GF(0x548))
436 u
= x
/y
; me
.assertEqual((u
.numer
, u
.denom
), (C
.GF(0x67), C
.GF(0x8)))
437 me
.assertEqual(x
//y
, C
.GF(0xc))
438 me
.assertEqual(x
%y
, C
.GF(0x9))
439 me
.assertEqual(divmod(x
, y
), (C
.GF(0xc), C
.GF(0x9)))
440 me
.assertRaises(ZeroDivisionError, lambda: x
/zero
)
441 me
.assertRaises(ZeroDivisionError, lambda: x
//zero
)
442 me
.assertRaises(ZeroDivisionError, lambda: x
%zero
)
443 me
.assertRaises(ZeroDivisionError, divmod, x
, zero
)
445 me
.assertEqual(pow(x
, 24),
446 C
.GF(0x1000100000001010000010101000101010001000001))
447 me
.assertEqual(pow(x
, 24, m
), C
.GF(0x78))
448 me
.assertEqual(pow(x
, -24, m
), C
.GF(0xb6))
449 me
.assertRaises(ZeroDivisionError, pow, x
, -24, C
.GF(0x18))
455 x
, y
, z
= C
.GF(0xa9), C
.GF(0x18), C
.GF(0xb3)
456 me
.assertTrue(x
== x
)
457 me
.assertFalse(x
!= x
)
458 me
.assertFalse(x
== y
)
459 me
.assertTrue(x
!= y
)
461 me
.assertFalse(y
> x
)
462 me
.assertFalse(x
> x
)
463 me
.assertFalse(x
> z
)
464 me
.assertFalse(z
> x
)
465 me
.assertTrue(x
>= y
)
466 me
.assertFalse(y
>= x
)
467 me
.assertTrue(x
>= x
)
468 me
.assertTrue(x
>= z
)
469 me
.assertTrue(z
>= x
)
470 me
.assertFalse(x
<= y
)
471 me
.assertTrue(y
<= x
)
472 me
.assertTrue(x
<= x
)
473 me
.assertTrue(x
<= z
)
474 me
.assertTrue(z
<= x
)
475 me
.assertFalse(x
< y
)
477 me
.assertFalse(x
< x
)
478 me
.assertFalse(x
< z
)
479 me
.assertFalse(z
< x
)
482 x
, zero
= C
.GF(0xa9), C
.GF(0)
483 me
.assertTrue(x
.testbit(0))
484 me
.assertFalse(x
.testbit(1))
485 me
.assertFalse(x
.testbit(1000))
487 me
.assertEqual(x
.setbit(0), x
)
488 me
.assertEqual(x
.clearbit(0), C
.GF(0xa8))
489 me
.assertEqual(x
.setbit(1), C
.GF(0xab))
490 me
.assertEqual(x
.clearbit(1), x
)
492 me
.assertEqual(x
.nbits
, 8)
493 me
.assertEqual(x
.degree
, 7)
494 me
.assertEqual(zero
.nbits
, 0)
495 me
.assertEqual(zero
.degree
, -1)
497 def test_loadstore(me
):
498 x
= C
.GF(0x0123456789ab)
500 me
.assertEqual(x
.noctets
, 6)
502 me
.assertEqual(x
, C
.GF
.loadb(C
.bytes("0123456789ab")))
504 me
.assertEqual(x
.storeb(), C
.bytes("0123456789ab"))
505 me
.assertEqual(x
.storeb(3), C
.bytes("6789ab"))
506 me
.assertEqual(x
.storeb(8), C
.bytes("00000123456789ab"))
508 me
.assertEqual(x
, C
.GF
.loadl(C
.bytes("ab8967452301")))
510 me
.assertEqual(x
.storel(), C
.bytes("ab8967452301"))
511 me
.assertEqual(x
.storel(3), C
.bytes("ab8967"))
512 me
.assertEqual(x
.storel(8), C
.bytes("ab89674523010000"))
514 me
.assertEqual(x
.tobuf(), C
.bytes("00060123456789ab"))
515 me
.assertEqual((x
, T
.bin("abcd")),
516 C
.GF
.frombuf(C
.bytes("00060123456789ab61626364")))
518 def test_numbertheory(me
):
519 p
, x
, y
= C
.GF(0x11b), C
.GF(0xa9), C
.GF(0x18)
521 me
.assertEqual(x
.sqr(), C
.GF(0x4441))
523 me
.assertEqual(x
.gcd(y
), C
.GF(0x3))
524 me
.assertEqual(x
.gcdx(y
), (C
.GF(0x3), C
.GF(0x3), C
.GF(0x15)))
525 me
.assertEqual(p
.modinv(x
), C
.GF(0xc8))
527 me
.assertTrue(p
.irreduciblep())
528 me
.assertFalse(x
.irreduciblep())
530 ###--------------------------------------------------------------------------
531 class TestGFReduce (U
.TestCase
):
534 p
= C
.GF(0x87).setbit(128)
535 me
.assertTrue(p
.irreduciblep())
538 x
= C
.GF(0xce46b4c1d3a1523520b1bb6eb5c61883)
539 y
= C
.GF(0xb5b0b3566b8e03f4b4a2b1ac413f8566)
540 xy
= C
.GF(0x28e5b895c11b08edc2fe7e1be5694c64)
542 me
.assertEqual(m
.reduce(x
*y
), xy
)
543 me
.assertEqual(m
.trace(x
), 0)
544 me
.assertEqual(m
.trace(y
), 1)
545 me
.assertEqual(m
.sqrt(x
), C
.GF(0xa277ee4bf770e5974cf1e31b1ccb54a1))
546 me
.assertEqual(m
.halftrace(y
), C
.GF(0x9cea73e79ffd190dd3c81d33e58d8e6f))
547 me
.assertEqual(m
.quadsolve(x
), C
.GF(0x9664c09d23d168147a438de6a813c784))
549 ###--------------------------------------------------------------------------
550 class TestGFN (U
.TestCase
):
553 p
= C
.GF(0x87).setbit(128)
554 beta
= C
.GF(0xc50f387e37194d4a4b41e157a3e2b5e1)
555 y
= C
.GF(0xdaca76dc2578a63c788a2ce0fc7878f6)
556 yy
= C
.GF(0x298a98f955100f054fcee3433f96b00e)
557 zero
, one
, fff
= C
.GF(0), C
.GF(1), C
.GF(T
.long(2)**128 - 1)
558 me
.assertTrue(p
.irreduciblep())
561 me
.assertEqual(gfn
.p
, p
)
562 me
.assertEqual(gfn
.beta
, beta
)
563 me
.assertEqual(gfn
.pton(zero
), zero
)
564 me
.assertEqual(gfn
.ntop(zero
), zero
)
565 me
.assertEqual(gfn
.pton(one
), fff
)
566 me
.assertEqual(gfn
.ntop(fff
), one
)
567 me
.assertEqual(gfn
.pton(y
), yy
)
568 me
.assertEqual(gfn
.ntop(yy
), y
)
570 ## Doesn't generate a normal basis.
571 me
.assertRaises(ValueError, C
.GFN
, p
, y
)
573 ###----- That's all, folks --------------------------------------------------
575 if __name__
== "__main__": U
.main()