chiark - git - mdw - catacomb-python/blob - t/t-mp.py

   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')
  72     me.assertEqual(repr(y), 'MP(6556380541834372447694561492436749633L)')
  73     me.assertEqual(hex(y), '0x4eeb684a0954ec4ceb255e3e9778d41')
  74     me.assertEqual(oct(y), '047353320450112516611472622536175135706501')
  75
  76   def test_number(me):
  77     x, y, m, zero = C.MP(169), C.MP(24), C.MP(205), C.MP(0)
  78
  79     me.assertEqual(-x, -169)
  80     me.assertEqual(~x, -170)
  81     me.assertEqual(abs(x), 169)
  82     me.assertEqual(abs(-x), 169)
  83
  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)
  93
  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)
 100
 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)
 109
 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)
 115
 116     me.assertTrue(x)
 117     me.assertFalse(zero)
 118
 119   def test_order(me):
 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)
 125     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)
 135     me.assertTrue(y < x)
 136     me.assertFalse(x < x)
 137
 138   def test_bits(me):
 139     x, y, zero = C.MP(169), C.MP(-24), C.MP(0)
 140     me.assertTrue(x.testbit(0))
 141     me.assertFalse(x.testbit(1))
 142     me.assertFalse(x.testbit(1000))
 143     me.assertFalse(y.testbit(0))
 144     me.assertTrue(y.testbit(3))
 145     me.assertTrue(y.testbit(1000))
 146
 147     me.assertEqual(x.setbit(0), x)
 148     me.assertEqual(x.clearbit(0), 168)
 149     me.assertEqual(x.setbit(1), 171)
 150     me.assertEqual(x.clearbit(1), x)
 151     me.assertEqual(y.setbit(0), -23)
 152     me.assertEqual(y.clearbit(0), y)
 153     me.assertEqual(y.setbit(3), y)
 154     me.assertEqual(y.clearbit(3), -32)
 155     me.assertEqual(y.setbit(1000), y)
 156
 157     me.assertEqual(x.nbits, 8)
 158     me.assertEqual(y.nbits, 5)
 159     me.assertEqual(zero.nbits, 0)
 160
 161   def test_loadstore(me):
 162     x = C.MP(0x0123456789ab)
 163     y = -x
 164     u = C.MP(0xfedcba9876)
 165
 166     me.assertEqual(x.noctets, 6)
 167     me.assertEqual(x.noctets2c, 6)
 168     me.assertEqual(y.noctets, 6)
 169     me.assertEqual(y.noctets2c, 6)
 170     me.assertEqual(u.noctets, 5)
 171     me.assertEqual(u.noctets2c, 6)
 172
 173     me.assertEqual(x, C.MP.loadb(C.bytes("0123456789ab")))
 174     me.assertEqual(x, C.MP.loadb2c(C.bytes("0123456789ab")))
 175     me.assertEqual(y, C.MP.loadb2c(C.bytes("fedcba987655")))
 176
 177     me.assertEqual(x.storeb(), C.bytes("0123456789ab"))
 178     me.assertEqual(x.storeb(3), C.bytes("6789ab"))
 179     me.assertEqual(x.storeb(8), C.bytes("00000123456789ab"))
 180     me.assertEqual(x.storeb2c(), C.bytes("0123456789ab"))
 181     me.assertEqual(x.storeb2c(3), C.bytes("6789ab"))
 182     me.assertEqual(x.storeb2c(8), C.bytes("00000123456789ab"))
 183     me.assertEqual(u.storeb2c(), C.bytes("00fedcba9876"))
 184     me.assertEqual(y.storeb2c(), C.bytes("fedcba987655"))
 185     me.assertEqual(y.storeb2c(3), C.bytes("987655"))
 186     me.assertEqual(y.storeb2c(8), C.bytes("fffffedcba987655"))
 187
 188     me.assertEqual(x, C.MP.loadl(C.bytes("ab8967452301")))
 189     me.assertEqual(x, C.MP.loadl2c(C.bytes("ab8967452301")))
 190     me.assertEqual(y, C.MP.loadl2c(C.bytes("557698badcfe")))
 191
 192     me.assertEqual(x.storel(), C.bytes("ab8967452301"))
 193     me.assertEqual(x.storel(3), C.bytes("ab8967"))
 194     me.assertEqual(x.storel(8), C.bytes("ab89674523010000"))
 195     me.assertEqual(x.storel2c(), C.bytes("ab8967452301"))
 196     me.assertEqual(x.storel2c(3), C.bytes("ab8967"))
 197     me.assertEqual(x.storel2c(8), C.bytes("ab89674523010000"))
 198     me.assertEqual(u.storel2c(), C.bytes("7698badcfe00"))
 199     me.assertEqual(y.storel2c(), C.bytes("557698badcfe"))
 200     me.assertEqual(y.storel2c(3), C.bytes("557698"))
 201     me.assertEqual(y.storel2c(8), C.bytes("557698badcfeffff"))
 202
 203     me.assertEqual(x.tobuf(), C.bytes("00060123456789ab"))
 204     me.assertEqual((x, T.bin("abcd")),
 205                    C.MP.frombuf(C.bytes("00060123456789ab61626364")))
 206
 207   def test_numbertheory(me):
 208     p, x, y, z = C.MP(173), C.MP(169), C.MP(24), C.MP(20)
 209
 210     me.assertEqual(x.odd(), (0, x))
 211     me.assertEqual(y.odd(), (3, 3))
 212
 213     me.assertEqual(x.sqr(), 28561)
 214     me.assertEqual(x.sqrt(), 13)
 215     me.assertEqual(y.sqrt(), 4)
 216
 217     me.assertEqual(x.gcd(y), 1)
 218     me.assertEqual(x.gcdx(y), (1, -23, 162))
 219     me.assertEqual(y.gcdx(x), (1, -7, 1))
 220     me.assertEqual(x.modinv(y), 162)
 221     me.assertEqual(y.modinv(x), 1)
 222
 223     me.assertEqual(x.jacobi(y), 1)
 224     me.assertEqual(x.jacobi(13), 0)
 225     me.assertEqual(y.jacobi(x), 1)
 226     me.assertEqual(p.jacobi(y), 1)
 227     me.assertEqual(p.jacobi(z), -1)
 228     me.assertEqual(p.modsqrt(y), 71)
 229     me.assertRaises(ValueError, p.modsqrt, z)
 230
 231     me.assertEqual(y.leastcongruent(x, 32), 184)
 232
 233     me.assertTrue(p.primep())
 234     me.assertFalse(x.primep())
 235
 236   def test_bang(me):
 237     me.assertEqual(C.MP.factorial(0), 1)
 238     me.assertEqual \
 239       (C.MP.factorial(50),
 240        30414093201713378043612608166064768844377641568960512000000000000)
 241     me.assertRaises((ValueError, OverflowError), C.MP.factorial, -1)
 242
 243   def test_fib(me):
 244     me.assertEqual(C.MP.fibonacci(-2), -1)
 245     me.assertEqual(C.MP.fibonacci(-1), +1)
 246     me.assertEqual(C.MP.fibonacci( 0),  0)
 247     me.assertEqual(C.MP.fibonacci(+1), +1)
 248     me.assertEqual(C.MP.fibonacci(+2), +1)
 249     me.assertEqual(C.MP.fibonacci(50), 12586269025)
 250
 251 ###--------------------------------------------------------------------------
 252 class TestMPMul (U.TestCase):
 253
 254   def test(me):
 255     m = C.MPMul()
 256     me.assertTrue(m.livep)
 257     m.factor(1, 2, 3)
 258     m.factor([4, 5, 6])
 259     me.assertEqual(m.done(), 720)
 260     me.assertFalse(m.livep)
 261
 262     me.assertEqual(C.MPMul(T.range(1, 7)).done(), 720)
 263     me.assertEqual(C.MP.factorial(6), 720)
 264
 265 ###--------------------------------------------------------------------------
 266 class TestMPMont (U.TestCase):
 267
 268   def test(me):
 269
 270     me.assertRaises(ValueError,
 271                     C.MPMont, 35315021952044908656941308411353985942)
 272     me.assertRaises(ValueError, C.MPMont, -9)
 273
 274     p = C.MP(269464705320809171350781605680038324101)
 275     g = C.MP(2) # lucky chance
 276     x = C.MP(211184293914316080585277908844600399612)
 277     y = C.MP(154454671298730680774195646814344206562)
 278     xy = C.MP(209444562478584646216087606217820187655)
 279     me.assertTrue(p.primep())
 280     m = C.MPMont(p)
 281     me.assertEqual(m.m, p)
 282
 283     ## The precise values of m.r and m.r2 are dependent on the internal
 284     ## bignum representation.  But we expect m.r to be congruent to some
 285     ## power of two.  (It should be 2^128.)
 286     t = p.modinv(m.r)
 287     for i in T.range(1025):
 288       if t == 1: break
 289       t *= 2
 290       if t >= p: t -= p
 291     else:
 292       me.fail("m.r is not a small-ish power of 2")
 293     me.assertEqual(m.r2, pow(2, 2*i, p))
 294     me.assertEqual(m.ext(m.r), 1)
 295     me.assertEqual(m.reduce(m.r), 1)
 296
 297     me.assertEqual(m.ext(m.int(x)), x)
 298     me.assertEqual(m.int(x), m.mul(x, m.r2))
 299     me.assertEqual(m.mul(m.int(x), y), xy)
 300     me.assertEqual(m.ext(m.mul(m.int(x), m.int(y))), xy)
 301
 302     me.assertEqual(m.exp(2, p - 1), 1)
 303     me.assertEqual(m.expr(m.int(2), p - 1), m.r)
 304
 305     q, r, s, z = 32, 128, 2048, pow(g, 156, p)
 306     me.assertEqual(m.mexp([(q, 9), (r, 8), (s, 5)]), z)
 307     me.assertEqual(m.mexp(q, 9, r, 8, s, 5), z)
 308
 309     q, r, s, z = T.imap(m.int, [32, 128, 2048, pow(g, 156, p)])
 310     me.assertEqual(m.mexpr([(q, 9), (r, 8), (s, 5)]), z)
 311     me.assertEqual(m.mexpr(q, 9, r, 8, s, 5), z)
 312
 313 ###--------------------------------------------------------------------------
 314 class TestMPBarrett (U.TestCase):
 315
 316   def test(me):
 317
 318     p = C.MP(269464705320809171350781605680038324101)
 319     g = C.MP(2) # lucky chance
 320     x = C.MP(211184293914316080585277908844600399612)
 321     y = C.MP(154454671298730680774195646814344206562)
 322     xy = C.MP(209444562478584646216087606217820187655)
 323     me.assertTrue(p.primep())
 324     m = C.MPBarrett(p)
 325     me.assertEqual(m.m, p)
 326
 327     me.assertEqual(m.reduce(x*y), xy)
 328
 329     me.assertEqual(m.exp(2, p - 1), 1)
 330
 331     q, r, s, z = 32, 128, 2048, pow(g, 156, p)
 332     me.assertEqual(m.mexp([(q, 9), (r, 8), (s, 5)]), z)
 333     me.assertEqual(m.mexp(q, 9, r, 8, s, 5), z)
 334
 335 ###--------------------------------------------------------------------------
 336 class TestMPReduce (U.TestCase):
 337
 338   def test(me):
 339
 340     p = C.MP(2)**127 - 1
 341     g = C.MP(2) # lucky chance
 342     x = C.MP(94827182170881245766374991987593163418)
 343     y = C.MP(106025009945795266831396608563402138277)
 344     xy = C.MP(80027041045616838298103413933629021123)
 345     me.assertTrue(p.primep())
 346     m = C.MPReduce(p)
 347     me.assertEqual(m.m, p)
 348
 349     me.assertEqual(m.reduce(x*y), xy)
 350
 351     me.assertEqual(m.exp(2, 127), 1)
 352
 353 ###--------------------------------------------------------------------------
 354 class TestMPCRT (U.TestCase):
 355
 356   def test(me):
 357
 358     c = C.MPCRT(5, 7, 11)
 359     me.assertEqual(c.moduli, [5, 7, 11])
 360     me.assertEqual(c.product, 385)
 361     me.assertEqual(c.solve([2, 3, 4]), 367)
 362     me.assertEqual(c.solve([2, -4, -7]), 367)
 363
 364     me.assertRaises(ValueError, C.MPCRT, [6, 15, 35])
 365
 366 ###--------------------------------------------------------------------------
 367 class TestGF (U.TestCase):
 368
 369   def test_make(me):
 370     x = C.GF(5)
 371     k = C.PrimeField(17)
 372     kk = C.BinPolyField(C.GF(0x13))
 373     E = k.ec(-3, 1)
 374     me.assertTrue(C.GF(x) is x)
 375     me.assertEqual(C.GF(k(8)), C.GF(8))
 376     me.assertEqual(C.GF(kk(8)), C.GF(8))
 377     me.assertEqual(C.GF(E(1, 4)), C.GF(1))
 378     me.assertRaises(TypeError, C.GF, E())
 379
 380     me.assertEqual(int(x), 5)
 381     y = C.GF(0x4eeb684a0954ec4ceb255e3e9778d41)
 382     me.assertEqual(type(int(y)), T.long)
 383
 384     me.assertEqual(C.GF('0x4eeb684a0954ec4ceb255e3e9778d41'), y)
 385     me.assertEqual(C.GF('4eeb684a0954ec4ceb255e3e9778d41', 16), y)
 386     me.assertEqual(C.GF('0b0', 16), C.GF(176)) # not 0
 387
 388     me.assertEqual(C.GF('047353320450112516611472622536175135706501'), y)
 389     me.assertEqual(C.GF('0o47353320450112516611472622536175135706501'), y)
 390     me.assertEqual(C.GF('047353320450112516611472622536175135706501', 8), y)
 391     me.assertEqual(C.GF('47353320450112516611472622536175135706501', 8), y)
 392
 393     t = C.GF(661438603)
 394     me.assertEqual(C.GF('0b100111011011001100000010001011'), t)
 395     me.assertEqual(C.GF('100111011011001100000010001011', 2), t)
 396
 397   def test_string(me):
 398     y = C.GF(0x4eeb684a0954ec4ceb255e3e9778d41)
 399     me.assertEqual(str(y), '0x4eeb684a0954ec4ceb255e3e9778d41')
 400     me.assertEqual(repr(y), 'GF(0x4eeb684a0954ec4ceb255e3e9778d41L)')
 401     me.assertEqual(hex(y), '0x4eeb684a0954ec4ceb255e3e9778d41')
 402     me.assertEqual(oct(y), '047353320450112516611472622536175135706501')
 403
 404   def test_number(me):
 405     x, y, m, zero = C.GF(0xa9), C.GF(0x18), C.GF(0x11b), C.GF(0)
 406
 407     me.assertEqual(x, -x)
 408     me.assertEqual(abs(x), x)
 409
 410     me.assertEqual(x + y, C.GF(0xb1))
 411     me.assertEqual(x - y, C.GF(0xb1))
 412     me.assertEqual(x*y, C.GF(0xfd8))
 413     me.assertEqual(x&y, C.GF(0x8))
 414     me.assertEqual(x | y, C.GF(0xb9))
 415     me.assertEqual(x ^ y, C.GF(0xb1))
 416
 417     me.assertEqual(x << 3, C.GF(0x548))
 418     me.assertEqual(x << -2, C.GF(0x2a))
 419     me.assertEqual(x >> 2, C.GF(0x2a))
 420     me.assertEqual(x >> -3, C.GF(0x548))
 421
 422     u = x/y; me.assertEqual((u.numer, u.denom), (C.GF(0x67), C.GF(0x8)))
 423     me.assertEqual(x//y, C.GF(0xc))
 424     me.assertEqual(x%y, C.GF(0x9))
 425     me.assertEqual(divmod(x, y), (C.GF(0xc), C.GF(0x9)))
 426     me.assertRaises(ZeroDivisionError, lambda: x/zero)
 427     me.assertRaises(ZeroDivisionError, lambda: x//zero)
 428     me.assertRaises(ZeroDivisionError, lambda: x%zero)
 429     me.assertRaises(ZeroDivisionError, divmod, x, zero)
 430
 431     me.assertEqual(pow(x, 24),
 432                    C.GF(0x1000100000001010000010101000101010001000001))
 433     me.assertEqual(pow(x, 24, m), C.GF(0x78))
 434     me.assertEqual(pow(x, -24, m), C.GF(0xb6))
 435     me.assertRaises(ZeroDivisionError, pow, x, -24, C.GF(0x18))
 436
 437     me.assertTrue(x)
 438     me.assertFalse(zero)
 439
 440   def test_order(me):
 441     x, y, z = C.GF(0xa9), C.GF(0x18), C.GF(0xb3)
 442     me.assertTrue(x == x)
 443     me.assertFalse(x != x)
 444     me.assertFalse(x == y)
 445     me.assertTrue(x != y)
 446     me.assertTrue(x > y)
 447     me.assertFalse(y > x)
 448     me.assertFalse(x > x)
 449     me.assertFalse(x > z)
 450     me.assertFalse(z > x)
 451     me.assertTrue(x >= y)
 452     me.assertFalse(y >= x)
 453     me.assertTrue(x >= x)
 454     me.assertTrue(x >= z)
 455     me.assertTrue(z >= x)
 456     me.assertFalse(x <= y)
 457     me.assertTrue(y <= x)
 458     me.assertTrue(x <= x)
 459     me.assertTrue(x <= z)
 460     me.assertTrue(z <= x)
 461     me.assertFalse(x < y)
 462     me.assertTrue(y < x)
 463     me.assertFalse(x < x)
 464     me.assertFalse(x < z)
 465     me.assertFalse(z < x)
 466
 467   def test_bits(me):
 468     x, zero = C.GF(0xa9), C.GF(0)
 469     me.assertTrue(x.testbit(0))
 470     me.assertFalse(x.testbit(1))
 471     me.assertFalse(x.testbit(1000))
 472
 473     me.assertEqual(x.setbit(0), x)
 474     me.assertEqual(x.clearbit(0), C.GF(0xa8))
 475     me.assertEqual(x.setbit(1), C.GF(0xab))
 476     me.assertEqual(x.clearbit(1), x)
 477
 478     me.assertEqual(x.nbits, 8)
 479     me.assertEqual(x.degree, 7)
 480     me.assertEqual(zero.nbits, 0)
 481     me.assertEqual(zero.degree, -1)
 482
 483   def test_loadstore(me):
 484     x = C.GF(0x0123456789ab)
 485
 486     me.assertEqual(x.noctets, 6)
 487
 488     me.assertEqual(x, C.GF.loadb(C.bytes("0123456789ab")))
 489
 490     me.assertEqual(x.storeb(), C.bytes("0123456789ab"))
 491     me.assertEqual(x.storeb(3), C.bytes("6789ab"))
 492     me.assertEqual(x.storeb(8), C.bytes("00000123456789ab"))
 493
 494     me.assertEqual(x, C.GF.loadl(C.bytes("ab8967452301")))
 495
 496     me.assertEqual(x.storel(), C.bytes("ab8967452301"))
 497     me.assertEqual(x.storel(3), C.bytes("ab8967"))
 498     me.assertEqual(x.storel(8), C.bytes("ab89674523010000"))
 499
 500     me.assertEqual(x.tobuf(), C.bytes("00060123456789ab"))
 501     me.assertEqual((x, T.bin("abcd")),
 502                    C.GF.frombuf(C.bytes("00060123456789ab61626364")))
 503
 504   def test_numbertheory(me):
 505     p, x, y = C.GF(0x11b), C.GF(0xa9), C.GF(0x18)
 506
 507     me.assertEqual(x.sqr(), C.GF(0x4441))
 508
 509     me.assertEqual(x.gcd(y), C.GF(0x3))
 510     me.assertEqual(x.gcdx(y), (C.GF(0x3), C.GF(0x3), C.GF(0x15)))
 511     me.assertEqual(p.modinv(x), C.GF(0xc8))
 512
 513     me.assertTrue(p.irreduciblep())
 514     me.assertFalse(x.irreduciblep())
 515
 516 ###--------------------------------------------------------------------------
 517 class TestGFReduce (U.TestCase):
 518
 519   def test(me):
 520     p = C.GF(0x87).setbit(128)
 521     me.assertTrue(p.irreduciblep())
 522     m = C.GFReduce(p)
 523
 524     x = C.GF(0xce46b4c1d3a1523520b1bb6eb5c61883)
 525     y = C.GF(0xb5b0b3566b8e03f4b4a2b1ac413f8566)
 526     xy = C.GF(0x28e5b895c11b08edc2fe7e1be5694c64)
 527
 528     me.assertEqual(m.reduce(x*y), xy)
 529     me.assertEqual(m.trace(x), 0)
 530     me.assertEqual(m.trace(y), 1)
 531     me.assertEqual(m.sqrt(x), C.GF(0xa277ee4bf770e5974cf1e31b1ccb54a1))
 532     me.assertEqual(m.halftrace(y), C.GF(0x9cea73e79ffd190dd3c81d33e58d8e6f))
 533     me.assertEqual(m.quadsolve(x), C.GF(0x9664c09d23d168147a438de6a813c784))
 534
 535 ###--------------------------------------------------------------------------
 536 class TestGFN (U.TestCase):
 537
 538   def test(me):
 539     p = C.GF(0x87).setbit(128)
 540     beta = C.GF(0xc50f387e37194d4a4b41e157a3e2b5e1)
 541     y = C.GF(0xdaca76dc2578a63c788a2ce0fc7878f6)
 542     yy = C.GF(0x298a98f955100f054fcee3433f96b00e)
 543     zero, one, fff = C.GF(0), C.GF(1), C.GF(T.long(2)**128 - 1)
 544     me.assertTrue(p.irreduciblep())
 545
 546     gfn = C.GFN(p, beta)
 547     me.assertEqual(gfn.p, p)
 548     me.assertEqual(gfn.beta, beta)
 549     me.assertEqual(gfn.pton(zero), zero)
 550     me.assertEqual(gfn.ntop(zero), zero)
 551     me.assertEqual(gfn.pton(one), fff)
 552     me.assertEqual(gfn.ntop(fff), one)
 553     me.assertEqual(gfn.pton(y), yy)
 554     me.assertEqual(gfn.ntop(yy), y)
 555
 556     ## Doesn't generate a normal basis.
 557     me.assertRaises(ValueError, C.GFN, p, y)
 558
 559 ###----- That's all, folks --------------------------------------------------
 560
 561 if __name__ == "__main__": U.main()