-rw-r--r-- 3017 mceliece-sage-20221023/goppa.sage raw
# goppa_errors() copied from https://eprint.iacr.org/2022/473 Algorithm 6.2
# see Theorems 6.4 and 6.5 for proof

from interpolator import interpolator
from approximant import approximant

def goppa_errors(n,t,k,alpha,g,r):
  r'''
  Return the unique e in F_2^n
  with sum_i (r[i]-e[i]) A/(x-alpha[i]) in gk[x]
  and wt e <= t,
  or None if no such e exists.
  Here A = prod_i (x-alpha[i]).

  INPUTS:

  * "n" - a nonnegative integer

  * "t" - a nonnegative integer

  * "k" - a field containing F_2

  * "alpha" - a list of n distinct elements of k

  * "g" - a squarefree element of the polynomial ring k[x] with deg g = t and g(alpha[j]) nonzero for each j

  * "r" - a list of n elements of k
  '''

  alpha,r = list(alpha),list(r)
  assert k.is_field() and k.characteristic() == 2
  assert g.base_ring() == k and g.degree() == t and g.is_squarefree()
  assert len(alpha) == n and len(set(alpha)) == n and len(r) == n
  kpoly = g.parent()
  A = kpoly(prod(kpoly([-alpha[j],1]) for j in range(n)))
  Aprime = A.derivative()
  rtwist = [r[i]*Aprime(alpha[i])/g(alpha[i])^2 for i in range(n)]
  B = interpolator(n,k,alpha,rtwist)
  a,b = approximant(t,k,A,B)
  aprime = a.derivative()
  if a.divides(A):
    if a.divides(g^2*b-aprime):
      if a*B-b*A == 0 or (a*B-b*A).degree() < n-2*t+a.degree():
        return [k(a(alpha[j]) == 0) for j in range(n)]

# ---- miscellaneous tests
# copied from https://eprint.iacr.org/2022/473 Figure A.4

def test_smallrandom():
  for m in range(1,10):
    q = 2^m
    print('goppa_errors %d' % q)
    sys.stdout.flush()
    k = GF(q)
    kpoly.<x> = k[]
    for loop in range(100):
      while True:
        n = randrange(q+1)
        t = randrange(3+n//m)
        if t >= n: t = n
        a = list(k)
        shuffle(a)
        a = a[:n]
        g = kpoly([k.random_element() for j in range(t)]+[1])
        if g.is_squarefree(): 
          if all(g(aj) != 0 for aj in a):
            break
  
      assert g.degree() == t
      A = kpoly(prod(x-aj for aj in a))
      Aprime = A.derivative()
      for aj in a: assert Aprime(aj) != 0
  
      for known in True,False:
        if known:
          f = kpoly([k.random_element() for j in range(n-2*t)])
          r = [(f*g^2)(aj)/Aprime(aj) for aj in a]
          if randrange(2):
            e = [1]*t+[0]*(n-t)
          else:
            actualweight = randrange(t+1)
            e = [1]*actualweight+[0]*(n-actualweight)
          shuffle(e)
          assert len([ej for ej in e if ej != 0]) <= t
          for j in range(n): r[j] += e[j]
        else:
          e = 'unknown' # cut off data flow from previous iteration
          r = [k.random_element() for j in range(n)]
        e2 = goppa_errors(n,t,k,a,g,r)
        if e2 == None:
          assert not known
        else:
          assert len(e2) == n
          if known: assert e2 == e
          assert len([ej for ej in e2 if ej != 0]) <= t
          assert g.divides(sum((r[i]-e2[i])*A//(x-a[i]) for i in range(n)))

if __name__ == '__main__':
  test_smallrandom()