Merge branch '1.2.x' into 1.3.x

[catacomb-python] / t / t-field.py

diff --git a/t/t-field.py b/t/t-field.py
new file mode 100644 (file)
index 0000000..3871b45
--- /dev/null
+++ b/t/t-field.py
@@ -0,0 +1,150 @@
+### -*-python-*-
+###
+### Testing finite-field functionality
+###
+### (c) 2019 Straylight/Edgeware
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This file is part of the Python interface to Catacomb.
+###
+### Catacomb/Python is free software: you can redistribute it and/or
+### modify it under the terms of the GNU General Public License as
+### published by the Free Software Foundation; either version 2 of the
+### License, or (at your option) any later version.
+###
+### Catacomb/Python is distributed in the hope that it will be useful, but
+### WITHOUT ANY WARRANTY; without even the implied warranty of
+### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+### General Public License for more details.
+###
+### You should have received a copy of the GNU General Public License
+### along with Catacomb/Python.  If not, write to the Free Software
+### Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+### USA.
+
+###--------------------------------------------------------------------------
+### Imported modules.
+
+import itertools as I
+
+import catacomb as C
+import unittest as U
+import testutils as T
+
+###--------------------------------------------------------------------------
+class TestFields (T.GenericTestMixin):
+  """Test finite fields."""
+
+  def _test_field(me, k):
+
+    ## Some initial values.
+    zero = k.zero
+    one = k.one
+    x = k(2760820866)
+    y = k(3757175895)
+    z = k(920571320)
+
+    ## Check that they're all different.
+    v = [zero, one, x, y, z]
+    for i in T.range(len(v)):
+      for j in T.range(len(v)):
+        if i == j: me.assertEqual(v[i], v[j])
+        else: me.assertNotEqual(v[i], v[j])
+
+    ## Basic arithmetic.  Knowing the answers is too hard.  For now, just
+    ## check that the field laws hold.
+    t = x + y; me.assertEqual(t - y, x); me.assertEqual(t - x, y)
+    t = x - y; me.assertEqual(t + y, x)
+    t = x*y; me.assertEqual(t/x, y); me.assertEqual(t/y, x)
+    me.assertEqual(+x, x)
+    me.assertEqual(x + -x, zero)
+    me.assertEqual(x - x, zero)
+    me.assertEqual(x*x.inv(), one)
+    me.assertEqual(x/x, one)
+    me.assertRaises(ZeroDivisionError, k.inv, zero)
+
+    ## Exponentiation.  At least we know the group exponent.
+    me.assertEqual(x**(k.q - 1), one)
+
+    ## Comparisons.  We've already done equality and inequality, and nothing
+    ## else should work.
+    me.assertRaises(TypeError, T.lt, x, y)
+    me.assertRaises(TypeError, T.le, x, y)
+    me.assertRaises(TypeError, T.ge, x, y)
+    me.assertRaises(TypeError, T.gt, x, y)
+
+    ## Conversion back to integer.
+    me.assertEqual(int(x), 2760820866)
+
+    ## Square and square-root.  In a prime field, we may need to search
+    ## around to find a quadratic residue.  In binary fields, squaring is
+    ## linear, and every element has a unique square root.
+    me.assertEqual(x*x, x.sqr())
+    for i in T.range(128):
+      t = k(int(x) + i)
+      q = t.sqrt()
+      if q is not None: break
+    else:
+      me.fail("no quadratic residue found")
+    me.assertEqual(q.sqr(), t)
+
+    ## Hex and octal conversions.
+    me.assertEqual(hex(x), hex(T.long(x.value)).rstrip("L"))
+    me.assertEqual(oct(x), oct(T.long(x.value)).rstrip("L"))
+
+    if isinstance(k, C.PrimeField):
+
+      ## Representation.
+      me.assertEqual(type(x.value), C.MP)
+      me.assertEqual(k.type, C.FTY_PRIME)
+
+      ## Properties.
+      me.assertEqual(k.p, k.q)
+
+      ## Operations.
+      me.assertEqual(x.dbl(), 2*x)
+      me.assertEqual(x.tpl(), 3*x)
+      me.assertEqual(x.qdl(), 4*x)
+      me.assertEqual(x.hlv(), x/2)
+
+    else:
+
+      ## Representation.
+      me.assertEqual(type(x.value), C.GF)
+      me.assertEqual(k.type, C.FTY_BINARY)
+
+      ## Properties.
+      me.assertEqual(k.m, k.nbits)
+      me.assertEqual(k.p.degree, k.m)
+      if isinstance(k, C.BinNormField):
+        l = C.BinPolyField(k.p)
+        a, b = l.zero, l(k.beta)
+        for i in T.range(k.m):
+          a += b
+          b = b.sqr()
+        me.assertEqual(a, l.one)
+
+      ## Operations.
+      for i in T.range(128):
+        t = k(int(x) + i)
+        u = t.quadsolve()
+        if u is not None: break
+      else:
+        me.fail("no quadratic solution found")
+      me.assertEqual(u*u + u, t)
+
+    ## Encoding.
+    me.assertEqual(k.nbits, (k.q - 1).nbits)
+    me.assertEqual(k.noctets, (k.q - 1).noctets)
+
+TestFields.generate_testcases \
+  (("%s-%s" % (name, suffix), getfn(C.eccurves[name]))
+   for suffix, getfn in [("coords", lambda einfo: einfo.curve.field),
+                         ("scalars", lambda einfo: C.PrimeField(einfo.r))]
+   for name in ["nist-p256", "nist-k233", "nist-b163", "nist-b283n"])
+
+###----- That's all, folks --------------------------------------------------
+
+if __name__ == "__main__": U.main()