-rw-r--r-- 2145 mceliece-sage-20221023/fixedweight.sage raw
import parameters def fixedweight(randombits,params): r''' Return the output of the Classic McEliece FixedWeight function using the specified source of random bits for the specified parameters. INPUT: "randombits" - a function that, on input r, returns a list of r bits "params" - a Classic McEliece parameter set ''' assert isinstance(params,parameters.parameters) m = params.m q = params.q n = params.n t = params.t sigma1 = params.sigma1 # "The integer tau is defined as t if n=q; # as 2t if q/2 <= n < q; as 4t if q/4 <= n < q/2; etc." tau = t while tau*n < t*q: tau *= 2 # "All of the selected parameter sets have q/2 <= n <= q, # so tau in {t,2t}." assert q/2 <= n assert n <= q assert tau == t or tau == 2*t while True: # "Generate sigma_1 tau uniform random bits b_0,b_1,...,b_{sigma_1 tau - 1}." b = randombits(sigma1*tau) # "Define d_j = sum_{i=0}^{m-1} b_{sigma_1 j + i} 2^i for each j in {0,1,...,tau-1}." d = [sum(b[sigma1*j+i]<<i for i in range(m)) for j in range(tau)] # "Define a_0,a_1,...,a_{t-1} as the first t entries in d_0,d_1,...,d_{tau-1} # in the range {0,1,...,n-1}. # If there are fewer than t such entries, restart the algorithm." a = [dj for dj in d if dj<n] if len(a) < t: continue a = a[:t] # "If a_0,a_1,...,a_{t-1} are not all distinct, restart the algorithm." if len(set(a)) < t: continue # "Define e = (e_0,e_1,...,e_{n-1}) in F_2^n # as the weight-t vector such that e_{a_i} = 1 for each i." e = [0]*n for ai in a: e[ai] = 1 # "Return e." return e # ----- miscellaneous tests def test1(): def randombits(r): return [randrange(2) for j in range(r)] for system in parameters.alltests: P = parameters.parameters(system,allowtestparams=True) n = P.n t = P.t print('fixedweight %s' % system) sys.stdout.flush() for loop in range(10): e = fixedweight(randombits,P) "outputs a vector e in F_2^n of weight t" assert len(e) == n assert sum(1 if ej else 0 for ej in e) == t if __name__ == '__main__': test1()