| 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() |