t/: Add a test suite.

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

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