-rw-r--r-- 2014 mceliece-sage-20221023/fieldordering.sage raw
import parameters

def fieldordering(b,params):
  r'''
  Return the output of the Classic McEliece FieldOrdering function
  on input b for the specified parameters.

  INPUT:

  "b" - a list of sigma2*t bits

  "params" - a Classic McEliece parameter set
  '''

  assert isinstance(params,parameters.parameters)
  m = params.m
  q = params.q
  Fq = params.Fq
  z = Fq.gen()
  sigma2 = params.sigma2

  # "takes a string of sigma_2 input bits"
  b = list(b)
  assert len(b) == sigma2*q

  # "Take the first sigma_2 input bits b_0,b_1,...,b_{sigma_2-1}
  #  as a sigma_2-bit integer a_0 = b_0 + 2b_1 + ... + 2^{sigma_2-1} b_{sigma_2-1},
  #  take the next sigma_2 bits as a sigma_2-bit integer a_1,
  #  and so on through a_{q-1}."
  a = [sum(b[j*sigma2+i]<<i for i in range(sigma2)) for j in range(q)]

  # "If a_0,a_1,...a_{q-1} are not distinct, return False."
  if len(set(a)) < q: return False

  # "Sort the pairs (a_i,i) in lexicographic order
  #  to obtain pairs (a_{pi(i)},pi(i))
  #  where pi is a permutation of {0,1,...,q-1}."
  api = sorted((a[i],i) for i in range(q))
  # now api[i] is (a[pi[i]],pi[i])

  # "Define alpha_i = sum_{j=0}^{m-1} pi(i)_j*z^{m-1-j}
  #  where pi(i)_j denotes the jth least significant bit of pi(i)."
  alpha = [sum((1&(api[i][1]>>j))*z^(m-1-j) for j in range(m))
           for i in range(q)]

  # "Output (alpha_0,alpha_1,...,alpha_{q-1})."
  return alpha

# ----- miscellaneous tests

def test1():
  for system in parameters.alltests:
    P = parameters.parameters(system,allowtestparams=True)
    m = P.m
    q = P.q
    Fq = P.Fq
    sigma2 = P.sigma2

    numsuccess = 0
    for loop in range(10):
      b = [randrange(2) for j in range(sigma2*q)]
      alpha = fieldordering(b,P)
      if alpha != False:
        numsuccess += 1
        assert len(alpha) == q
        assert len(set(alpha)) == q
        assert sorted(alpha) == sorted(Fq)

    print('fieldordering %s numsuccess %d' % (system,numsuccess))
    sys.stdout.flush()

if __name__ == '__main__':
  test1()