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), '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_float(me):
 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)
 148     z = 1.0
 149     while z == z + 1: z *= 2.0
 150     me.assertNotEqual(C.MP(int(z)) + 1, z)
 151
 152   def test_bits(me):
 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))
 160
 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)
 170
 171     me.assertEqual(x.nbits, 8)
 172     me.assertEqual(y.nbits, 5)
 173     me.assertEqual(zero.nbits, 0)
 174
 175   def test_loadstore(me):
 176     x = C.MP(0x0123456789ab)
 177     y = -x
 178     u = C.MP(0xfedcba9876)
 179
 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)
 186
 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")))
 190
 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"))
 201
 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")))
 205
 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"))
 216
 217     me.assertEqual(x.tobuf(), C.bytes("00060123456789ab"))
 218     me.assertEqual((x, T.bin("abcd")),
 219                    C.MP.frombuf(C.bytes("00060123456789ab61626364")))
 220
 221   def test_numbertheory(me):
 222     p, x, y, z = C.MP(173), C.MP(169), C.MP(24), C.MP(20)
 223
 224     me.assertEqual(x.odd(), (0, x))
 225     me.assertEqual(y.odd(), (3, 3))
 226
 227     me.assertEqual(x.sqr(), 28561)
 228     me.assertEqual(x.sqrt(), 13)
 229     me.assertEqual(y.sqrt(), 4)
 230
 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)
 236
 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)
 244
 245     me.assertEqual(y.leastcongruent(x, 32), 184)
 246
 247     me.assertTrue(p.primep())
 248     me.assertFalse(x.primep())
 249
 250   def test_bang(me):
 251     me.assertEqual(C.MP.factorial(0), 1)
 252     me.assertEqual \
 253       (C.MP.factorial(50),
 254        30414093201713378043612608166064768844377641568960512000000000000)
 255     me.assertRaises((ValueError, OverflowError), C.MP.factorial, -1)
 256
 257   def test_fib(me):
 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)
 264
 265 ###--------------------------------------------------------------------------
 266 class TestMPMul (U.TestCase):
 267
 268   def test(me):
 269     m = C.MPMul()
 270     me.assertTrue(m.livep)
 271     m.factor(1, 2, 3)
 272     m.factor([4, 5, 6])
 273     me.assertEqual(m.done(), 720)
 274     me.assertFalse(m.livep)
 275
 276     me.assertEqual(C.MPMul(T.range(1, 7)).done(), 720)
 277     me.assertEqual(C.MP.factorial(6), 720)
 278
 279 ###--------------------------------------------------------------------------
 280 class TestMPMont (U.TestCase):
 281
 282   def test(me):
 283
 284     me.assertRaises(ValueError,
 285                     C.MPMont, 35315021952044908656941308411353985942)
 286     me.assertRaises(ValueError, C.MPMont, -9)
 287
 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())
 294     m = C.MPMont(p)
 295     me.assertEqual(m.m, p)
 296
 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.)
 300     t = p.modinv(m.r)
 301     for i in T.range(1025):
 302       if t == 1: break
 303       t *= 2
 304       if t >= p: t -= p
 305     else:
 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)
 310
 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)
 315
 316     me.assertEqual(m.exp(2, p - 1), 1)
 317     me.assertEqual(m.expr(m.int(2), p - 1), m.r)
 318
 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)
 322
 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)
 326
 327 ###--------------------------------------------------------------------------
 328 class TestMPBarrett (U.TestCase):
 329
 330   def test(me):
 331
 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())
 338     m = C.MPBarrett(p)
 339     me.assertEqual(m.m, p)
 340
 341     me.assertEqual(m.reduce(x*y), xy)
 342
 343     me.assertEqual(m.exp(2, p - 1), 1)
 344
 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)
 348
 349 ###--------------------------------------------------------------------------
 350 class TestMPReduce (U.TestCase):
 351
 352   def test(me):
 353
 354     p = C.MP(2)**127 - 1
 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())
 360     m = C.MPReduce(p)
 361     me.assertEqual(m.m, p)
 362
 363     me.assertEqual(m.reduce(x*y), xy)
 364
 365     me.assertEqual(m.exp(2, 127), 1)
 366
 367 ###--------------------------------------------------------------------------
 368 class TestMPCRT (U.TestCase):
 369
 370   def test(me):
 371
 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)
 377
 378     me.assertRaises(ValueError, C.MPCRT, [6, 15, 35])
 379
 380 ###--------------------------------------------------------------------------
 381 class TestGF (U.TestCase):
 382
 383   def test_make(me):
 384     x = C.GF(5)
 385     k = C.PrimeField(17)
 386     kk = C.BinPolyField(C.GF(0x13))
 387     E = k.ec(-3, 1)
 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())
 393
 394     me.assertEqual(int(x), 5)
 395     y = C.GF(0x4eeb684a0954ec4ceb255e3e9778d41)
 396     me.assertEqual(type(int(y)), T.long)
 397
 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
 401
 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)
 406
 407     t = C.GF(661438603)
 408     me.assertEqual(C.GF('0b100111011011001100000010001011'), t)
 409     me.assertEqual(C.GF('100111011011001100000010001011', 2), t)
 410
 411   def test_string(me):
 412     y = C.GF(0x4eeb684a0954ec4ceb255e3e9778d41)
 413     me.assertEqual(str(y), '0x4eeb684a0954ec4ceb255e3e9778d41')
 414     me.assertEqual(repr(y), 'GF(0x4eeb684a0954ec4ceb255e3e9778d41)')
 415     me.assertEqual(hex(y), '0x4eeb684a0954ec4ceb255e3e9778d41')
 416     me.assertEqual(oct(y), '047353320450112516611472622536175135706501')
 417
 418   def test_number(me):
 419     x, y, m, zero = C.GF(0xa9), C.GF(0x18), C.GF(0x11b), C.GF(0)
 420
 421     me.assertEqual(x, -x)
 422     me.assertEqual(abs(x), x)
 423
 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))
 430
 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))
 435
 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)
 444
 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))
 450
 451     me.assertTrue(x)
 452     me.assertFalse(zero)
 453
 454   def test_order(me):
 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)
 460     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)
 476     me.assertTrue(y < x)
 477     me.assertFalse(x < x)
 478     me.assertFalse(x < z)
 479     me.assertFalse(z < x)
 480
 481   def test_bits(me):
 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))
 486
 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)
 491
 492     me.assertEqual(x.nbits, 8)
 493     me.assertEqual(x.degree, 7)
 494     me.assertEqual(zero.nbits, 0)
 495     me.assertEqual(zero.degree, -1)
 496
 497   def test_loadstore(me):
 498     x = C.GF(0x0123456789ab)
 499
 500     me.assertEqual(x.noctets, 6)
 501
 502     me.assertEqual(x, C.GF.loadb(C.bytes("0123456789ab")))
 503
 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"))
 507
 508     me.assertEqual(x, C.GF.loadl(C.bytes("ab8967452301")))
 509
 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"))
 513
 514     me.assertEqual(x.tobuf(), C.bytes("00060123456789ab"))
 515     me.assertEqual((x, T.bin("abcd")),
 516                    C.GF.frombuf(C.bytes("00060123456789ab61626364")))
 517
 518   def test_numbertheory(me):
 519     p, x, y = C.GF(0x11b), C.GF(0xa9), C.GF(0x18)
 520
 521     me.assertEqual(x.sqr(), C.GF(0x4441))
 522
 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))
 526
 527     me.assertTrue(p.irreduciblep())
 528     me.assertFalse(x.irreduciblep())
 529
 530 ###--------------------------------------------------------------------------
 531 class TestGFReduce (U.TestCase):
 532
 533   def test(me):
 534     p = C.GF(0x87).setbit(128)
 535     me.assertTrue(p.irreduciblep())
 536     m = C.GFReduce(p)
 537
 538     x = C.GF(0xce46b4c1d3a1523520b1bb6eb5c61883)
 539     y = C.GF(0xb5b0b3566b8e03f4b4a2b1ac413f8566)
 540     xy = C.GF(0x28e5b895c11b08edc2fe7e1be5694c64)
 541
 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))
 548
 549 ###--------------------------------------------------------------------------
 550 class TestGFN (U.TestCase):
 551
 552   def test(me):
 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())
 559
 560     gfn = C.GFN(p, beta)
 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)
 569
 570     ## Doesn't generate a normal basis.
 571     me.assertRaises(ValueError, C.GFN, p, y)
 572
 573 ###----- That's all, folks --------------------------------------------------
 574
 575 if __name__ == "__main__": U.main()