Sagemath/C implementation of the Polynomial Modular Number
System using Babai's reduction algorithms. The main objective is to
provide a simple C code generator to perform arithmetic in the
PMNS.
It is available at https://plmlab.math.cnrs.fr/melon359/pmns
A PMNS is defined by 4 parameters:
p: a prime defining the finite field GF(p) we want to work onn: the degree of the external reduction polynomial E(X),
elements of GF(p) are represented as polynomial modulo E so that
n should be as small as possible to minimize arithmetic complexity
but larger that log_2(p)gamma: a root of E used to switch between standard
representation and PMNS. An interger a is represented by any
polynomial A(X) such that A(gamma) = a mod prho: an upper bound of the coefficient absolute value. It must be
large enough so that any element of GF(p) can be represented by a
polynomial with coeffient smaller than rhoload("pmns.load")
n,p,gamma = 4, 599497686217, 22899
E = X^n - 2
L = lattice_gen(n,p,gamma)
a,b = 111409747195,477347818871
A,B = int_to_pmns(a,L), int_to_pmns(b,L)
C = A*B % E
print(A)
print(B)
print(C)
print("rho =",babai_ns_rho(L))
-268*X^3 - 9*X^2 - 254*X - 174
382*X^3 - 378*X^2 + 291*X + 272
-45971*X^3 - 215342*X^2 + 76010*X - 390556
rho = 882
The coefficients of the polynomial C are larger than rho and must be reduced. The function babai_reduction is designed to output an equivalent polynomial with smaller coefficient using Babai's nearest plane algorithm.
C1 = babai_reduction(C, L)
print(C1)
72*X^3 - 557*X^2 + 264*X - 331
C implementationBabai's algorithms (nearest plane and rounding) are both slow and
require to perform arithmetic over large intergers. The codegen.sage
file provide a C code generator for modified version of those
algorithms targetting 64 bits architectures. They trade off some
precision (rho is usually larger) for huge speed improvements.
A few additional parameters and constraints are required to produce a
full C implementation.
E must be of the form X^n -l with l as small as
possiblerho must be smaller than 2^63 (so signed coefficients hold in a
long int)long long int. A "loose" bound on rho is
(rho^2)(1-(n-1)|l|) < 2^128 yet more precises bound can be
obtained in practiceh1 must be such that the shifted matrix coefficients
(Gram Schimdt for nearest plane and Inverse for rounding) hold in 64
bitsh2 must be such that, after a h2 bit right shift,
the 128 bit coefficients hold in 64 bits. Each algorithms have
specific constraints (yet very similar in practice)In order to build a good PMNS for a given prime p one must go
through the following process:
l so that there exists a root gamma
of the polynomial X^n-l. The param_search.sage script is a simple way to do
that given a prime parameter: $ sage param_search.sage -p 115792089237316195423570985008687907853269984665640564039457584007913129639747 --all --best
Nearest Plane parameters
------------------------
Best proven:
(5, 2, 76794080036964337559609571131357285081190159547914028654382067353176890555200, 114, 50, 1.7410680008462516, 12.779175631247)
Best practical:
(5, 2, 76794080036964337559609571131357285081190159547914028654382067353176890555200, 114, 50, 1.74106800084625, 12.3779175631247)
Rounding parameters
-------------------
Best proven:
(5, 2, 76794080036964337559609571131357285081190159547914028654382067353176890555200, 114, 50, 1.58594403035136, 16.7127631725992)
Best practical:
(5, 2, 76794080036964337559609571131357285081190159547914028654382067353176890555200, 114, 50, 1.58594403035136, 16.7127631725992)
It will output the best parameters it found. Proven parameters are parameters that ensure that the norm of the output of the corresponding reduction algorithm is lower than the rho parameter of the PMNS. Practical parameters do not necessarely ensure that property from a theoretical point of view but have been tested on a number of limit test cases.
sage load codegen.sage and execute the function
gen_files with the previous parameter.make commandmake tests and/or perform some timing measurements with make timing