mdw@git.distorted.org.uk Git - 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(6556380541834372447694561492436749633)')
  73     me.assertEqual(hex(y), '0x4eeb684a0954ec4ceb255e3e9778d41')
  74     me.assertEqual(oct(y), T.py23('0', '0o') +
  75                    '47353320450112516611472622536175135706501')
  76     try: bin
  77     except NameError: pass
  78     else: me.assertEqual(bin(C.MP(661438603)),
  79                          '0b100111011011001100000010001011')
  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
 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
 157   def test_bits(me):
 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))
 165
 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)
 175
 176     me.assertEqual(x.nbits, 8)
 177     me.assertEqual(y.nbits, 5)
 178     me.assertEqual(zero.nbits, 0)
 179
 180   def test_loadstore(me):
 181     x = C.MP(0x0123456789ab)
 182     y = -x
 183     u = C.MP(0xfedcba9876)
 184
 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)
 191
 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")))
 195
 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"))
 206
 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")))
 210
 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"))
 221
 222     me.assertEqual(x.tobuf(), C.bytes("00060123456789ab"))
 223     me.assertEqual((x, T.bin("abcd")),
 224                    C.MP.frombuf(C.bytes("00060123456789ab61626364")))
 225
 226   def test_numbertheory(me):
 227     p, x, y, z = C.MP(173), C.MP(169), C.MP(24), C.MP(20)
 228
 229     me.assertEqual(x.odd(), (0, x))
 230     me.assertEqual(y.odd(), (3, 3))
 231
 232     me.assertEqual(x.sqr(), 28561)
 233     me.assertEqual(x.sqrt(), 13)
 234     me.assertEqual(y.sqrt(), 4)
 235
 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)
 241
 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)
 249
 250     me.assertEqual(y.leastcongruent(x, 32), 184)
 251
 252     me.assertTrue(p.primep())
 253     me.assertFalse(x.primep())
 254
 255   def test_bang(me):
 256     me.assertEqual(C.MP.factorial(0), 1)
 257     me.assertEqual \
 258       (C.MP.factorial(50),
 259        30414093201713378043612608166064768844377641568960512000000000000)
 260     me.assertRaises((ValueError, OverflowError), C.MP.factorial, -1)
 261
 262   def test_fib(me):
 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)
 269
 270 ###--------------------------------------------------------------------------
 271 class TestMPMul (U.TestCase):
 272
 273   def test(me):
 274     m = C.MPMul()
 275     me.assertTrue(m.livep)
 276     m.factor(1, 2, 3)
 277     m.factor([4, 5, 6])
 278     me.assertEqual(m.done(), 720)
 279     me.assertFalse(m.livep)
 280
 281     me.assertEqual(C.MPMul(T.range(1, 7)).done(), 720)
 282     me.assertEqual(C.MP.factorial(6), 720)
 283
 284 ###--------------------------------------------------------------------------
 285 class TestMPMont (U.TestCase):
 286
 287   def test(me):
 288
 289     me.assertRaises(ValueError,
 290                     C.MPMont, 35315021952044908656941308411353985942)
 291     me.assertRaises(ValueError, C.MPMont, -9)
 292
 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())
 299     m = C.MPMont(p)
 300     me.assertEqual(m.m, p)
 301
 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.)
 305     t = p.modinv(m.r)
 306     for i in T.range(1025):
 307       if t == 1: break
 308       t *= 2
 309       if t >= p: t -= p
 310     else:
 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)
 315
 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)
 320
 321     me.assertEqual(m.exp(2, p - 1), 1)
 322     me.assertEqual(m.expr(m.int(2), p - 1), m.r)
 323
 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)
 327
 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)
 331
 332 ###--------------------------------------------------------------------------
 333 class TestMPBarrett (U.TestCase):
 334
 335   def test(me):
 336
 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())
 343     m = C.MPBarrett(p)
 344     me.assertEqual(m.m, p)
 345
 346     me.assertEqual(m.reduce(x*y), xy)
 347
 348     me.assertEqual(m.exp(2, p - 1), 1)
 349
 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)
 353
 354 ###--------------------------------------------------------------------------
 355 class TestMPReduce (U.TestCase):
 356
 357   def test(me):
 358
 359     p = C.MP(2)**127 - 1
 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())
 365     m = C.MPReduce(p)
 366     me.assertEqual(m.m, p)
 367
 368     me.assertEqual(m.reduce(x*y), xy)
 369
 370     me.assertEqual(m.exp(2, 127), 1)
 371
 372 ###--------------------------------------------------------------------------
 373 class TestMPCRT (U.TestCase):
 374
 375   def test(me):
 376
 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)
 382
 383     me.assertRaises(ValueError, C.MPCRT, [6, 15, 35])
 384
 385 ###--------------------------------------------------------------------------
 386 class TestGF (U.TestCase):
 387
 388   def test_make(me):
 389     x = C.GF(5)
 390     k = C.PrimeField(17)
 391     kk = C.BinPolyField(C.GF(0x13))
 392     E = k.ec(-3, 1)
 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())
 398
 399     me.assertEqual(int(x), 5)
 400     y = C.GF(0x4eeb684a0954ec4ceb255e3e9778d41)
 401     me.assertEqual(type(int(y)), T.long)
 402
 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
 406
 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)
 411
 412     t = C.GF(661438603)
 413     me.assertEqual(C.GF('0b100111011011001100000010001011'), t)
 414     me.assertEqual(C.GF('100111011011001100000010001011', 2), t)
 415
 416   def test_string(me):
 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')
 423     try: bin
 424     except NameError: pass
 425     else: me.assertEqual(bin(C.GF(661438603)),
 426                          '0b100111011011001100000010001011')
 427
 428   def test_number(me):
 429     x, y, m, zero = C.GF(0xa9), C.GF(0x18), C.GF(0x11b), C.GF(0)
 430
 431     me.assertEqual(x, -x)
 432     me.assertEqual(abs(x), x)
 433
 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))
 440
 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))
 445
 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)
 454
 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))
 460
 461     me.assertTrue(x)
 462     me.assertFalse(zero)
 463
 464   def test_order(me):
 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)
 470     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)
 486     me.assertTrue(y < x)
 487     me.assertFalse(x < x)
 488     me.assertFalse(x < z)
 489     me.assertFalse(z < x)
 490
 491   def test_bits(me):
 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))
 496
 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)
 501
 502     me.assertEqual(x.nbits, 8)
 503     me.assertEqual(x.degree, 7)
 504     me.assertEqual(zero.nbits, 0)
 505     me.assertEqual(zero.degree, -1)
 506
 507   def test_loadstore(me):
 508     x = C.GF(0x0123456789ab)
 509
 510     me.assertEqual(x.noctets, 6)
 511
 512     me.assertEqual(x, C.GF.loadb(C.bytes("0123456789ab")))
 513
 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"))
 517
 518     me.assertEqual(x, C.GF.loadl(C.bytes("ab8967452301")))
 519
 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"))
 523
 524     me.assertEqual(x.tobuf(), C.bytes("00060123456789ab"))
 525     me.assertEqual((x, T.bin("abcd")),
 526                    C.GF.frombuf(C.bytes("00060123456789ab61626364")))
 527
 528   def test_numbertheory(me):
 529     p, x, y = C.GF(0x11b), C.GF(0xa9), C.GF(0x18)
 530
 531     me.assertEqual(x.sqr(), C.GF(0x4441))
 532
 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))
 536
 537     me.assertTrue(p.irreduciblep())
 538     me.assertFalse(x.irreduciblep())
 539
 540 ###--------------------------------------------------------------------------
 541 class TestGFReduce (U.TestCase):
 542
 543   def test(me):
 544     p = C.GF(0x87).setbit(128)
 545     me.assertTrue(p.irreduciblep())
 546     m = C.GFReduce(p)
 547
 548     x = C.GF(0xce46b4c1d3a1523520b1bb6eb5c61883)
 549     y = C.GF(0xb5b0b3566b8e03f4b4a2b1ac413f8566)
 550     xy = C.GF(0x28e5b895c11b08edc2fe7e1be5694c64)
 551
 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))
 558
 559 ###--------------------------------------------------------------------------
 560 class TestGFN (U.TestCase):
 561
 562   def test(me):
 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())
 569
 570     gfn = C.GFN(p, beta)
 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)
 579
 580     ## Doesn't generate a normal basis.
 581     me.assertRaises(ValueError, C.GFN, p, y)
 582
 583 ###----- That's all, folks --------------------------------------------------
 584
 585 if __name__ == "__main__": U.main()