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