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

   1 ### -*-python-*-
   2 ###
   3 ### Testing finite-field 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 itertools as I
  31
  32 import catacomb as C
  33 import unittest as U
  34 import testutils as T
  35
  36 ###--------------------------------------------------------------------------
  37 class TestFields (T.GenericTestMixin):
  38   """Test finite fields."""
  39
  40   def _test_field(me, k):
  41
  42     ## Some initial values.
  43     zero = k.zero
  44     one = k.one
  45     x = k(2760820866)
  46     y = k(3757175895)
  47     z = k(920571320)
  48
  49     ## Check that they're all different.
  50     v = [zero, one, x, y, z]
  51     for i in T.range(len(v)):
  52       for j in T.range(len(v)):
  53         if i == j: me.assertEqual(v[i], v[j])
  54         else: me.assertNotEqual(v[i], v[j])
  55
  56     ## Basic arithmetic.  Knowing the answers is too hard.  For now, just
  57     ## check that the field laws hold.
  58     t = x + y; me.assertEqual(t - y, x); me.assertEqual(t - x, y)
  59     t = x - y; me.assertEqual(t + y, x)
  60     t = x*y; me.assertEqual(t/x, y); me.assertEqual(t/y, x)
  61     me.assertEqual(+x, x)
  62     me.assertEqual(x + -x, zero)
  63     me.assertEqual(x - x, zero)
  64     me.assertEqual(x*x.inv(), one)
  65     me.assertEqual(x/x, one)
  66     me.assertRaises(ZeroDivisionError, k.inv, zero)
  67
  68     ## Exponentiation.  At least we know the group exponent.
  69     me.assertEqual(x**(k.q - 1), one)
  70
  71     ## Comparisons.  We've already done equality and inequality, and nothing
  72     ## else should work.
  73     me.assertRaises(TypeError, T.lt, x, y)
  74     me.assertRaises(TypeError, T.le, x, y)
  75     me.assertRaises(TypeError, T.ge, x, y)
  76     me.assertRaises(TypeError, T.gt, x, y)
  77
  78     ## Conversion back to integer.
  79     me.assertEqual(int(x), 2760820866)
  80
  81     ## Square and square-root.  In a prime field, we may need to search
  82     ## around to find a quadratic residue.  In binary fields, squaring is
  83     ## linear, and every element has a unique square root.
  84     me.assertEqual(x*x, x.sqr())
  85     for i in T.range(128):
  86       t = k(int(x) + i)
  87       q = t.sqrt()
  88       if q is not None: break
  89     else:
  90       me.fail("no quadratic residue found")
  91     me.assertEqual(q.sqr(), t)
  92
  93     ## Hex and octal conversions.
  94     me.assertEqual(hex(x), hex(T.long(x.value)).rstrip("L"))
  95     me.assertEqual(oct(x), oct(T.long(x.value)).rstrip("L"))
  96
  97     if isinstance(k, C.PrimeField):
  98
  99       ## Representation.
 100       me.assertEqual(type(x.value), C.MP)
 101       me.assertEqual(k.type, C.FTY_PRIME)
 102
 103       ## Properties.
 104       me.assertEqual(k.p, k.q)
 105
 106       ## Operations.
 107       me.assertEqual(x.dbl(), 2*x)
 108       me.assertEqual(x.tpl(), 3*x)
 109       me.assertEqual(x.qdl(), 4*x)
 110       me.assertEqual(x.hlv(), x/2)
 111
 112     else:
 113
 114       ## Representation.
 115       me.assertEqual(type(x.value), C.GF)
 116       me.assertEqual(k.type, C.FTY_BINARY)
 117
 118       ## Properties.
 119       me.assertEqual(k.m, k.nbits)
 120       me.assertEqual(k.p.degree, k.m)
 121       if isinstance(k, C.BinNormField):
 122         l = C.BinPolyField(k.p)
 123         a, b = l.zero, l(k.beta)
 124         for i in T.range(k.m):
 125           a += b
 126           b = b.sqr()
 127         me.assertEqual(a, l.one)
 128
 129       ## Operations.
 130       for i in T.range(128):
 131         t = k(int(x) + i)
 132         u = t.quadsolve()
 133         if u is not None: break
 134       else:
 135         me.fail("no quadratic solution found")
 136       me.assertEqual(u*u + u, t)
 137
 138     ## Encoding.
 139     me.assertEqual(k.nbits, (k.q - 1).nbits)
 140     me.assertEqual(k.noctets, (k.q - 1).noctets)
 141
 142 TestFields.generate_testcases \
 143   (("%s-%s" % (name, suffix), getfn(C.eccurves[name]))
 144    for suffix, getfn in [("coords", lambda einfo: einfo.curve.field),
 145                          ("scalars", lambda einfo: C.PrimeField(einfo.r))]
 146    for name in ["nist-p256", "nist-k233", "nist-b163", "nist-b283n"])
 147
 148 ###----- That's all, folks --------------------------------------------------
 149
 150 if __name__ == "__main__": U.main()