, E(X) is irreducible. Morerover, gcd(n, p?1) = 4 divides y, hence four PMNS can be generated from E(X)
, Number of PMNS in the general case In this part, we propose a general method to count the minimum number of PMNS we can reach from a prime p and any irreducible polynomial in Z
, )) mod p can be done, in a reasonable time, in two steps : 1. we compute X p mod E(X) mod p with a square and multiply exponentiation algorithm, and we compute F (X) = X p ? X mod E(X) mod p, 2. then, we evaluate gcd(F (X), E(X)) mod p
, The first step represents at most log(p) squares and multiplications, and the second step represents at most n iterations of the Euclidean algorithm
, E(X) a polynomial of degree n and irreducible in Z[X], and D(X) = gcd(X p ? X, E(X)) mod p
, Polynomial Modular Number Systems (p, n, ? i , ?) E(X)
,
On Lovász' lattice reduction and the nearest lattice point problem, Combinatorica, vol.6, issue.1, pp.1-13, 1986. ,
Arithmetic operations in the polynomial modular number system, 17th IEEE Symposium on Computer Arithmetic (ARITH'05), pp.206-213, 2005. ,
URL : https://hal.archives-ouvertes.fr/lirmm-00387051
Modular number systems : Beyond the Mersenne family, Selected Areas in Cryptography, pp.159-169, 2005. ,
URL : https://hal.archives-ouvertes.fr/lirmm-00109208
Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor, Advances in Cryptology, Proc. Crypto'86, vol.263, pp.311-323, 1987. ,
On an irreducibility criterion of Perron for multivariate polynomials, Bull. Math. Soc. Sci. Math. Roumanie, vol.53, issue.101, pp.213-217, 2010. ,
Schönemann-Eisenstein-Dumas-type irreducibility conditions that use arbitrarily many prime numbers, Journal Communications in Algebra, vol.43, issue.8, 2015. ,
Randomization of Arithmetic over Polynomial Modular Number System, 26th IEEE International Symposium on Computer Arithmetic, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-02099713
Sur quelques cas d'irreductibilité des polynômes à coefficients rationnels, Journal de Mathématique Pure et Appliquée, vol.2, 1906. ,
On the irreducibility of -1,0,1-quadrinomials, INTE-GERS : Electronic Journal of Combinatorial Number Theory, issue.6, 2006. ,
Mathematics of Public Key Cryptography, 2012. ,
Algorithms for the shortest and closest lattice vector problems, International Conference on Coding and Cryptology, pp.159-190, 2011. ,
URL : https://hal.archives-ouvertes.fr/hal-00640637
Faster integer multiplication using short lattice vectors, Thirteenth Algorithmic Number Theory Symposium ANTS XIII, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-02350426
Solving hard lattice problems and the security of lattice-based cryptosystems, Cryptology ePrint Archive, 2012. ,
On the irreducibility of certain trinomials and quadrinomials, Mathematica Scandinavica, vol.8, issue.1, pp.65-70, 1960. ,
Handbook of Applied Cryptography, 1996. ,
Complexity of Lattice Problems : a cryptographic perspective, The Kluwer International Series in Engineering and Computer Science, vol.671, 2002. ,
The factorization of certain quadrinomials, Mathematica Scandinavica, vol.57, 1985. ,
Modular multiplication without trial division, Mathematics of Computation, vol.44, pp.519-521, 1985. ,
Univariate polynomial factorization over finite fields, Theoretical Computer Science, vol.191, issue.1-2, pp.1-36, 1998. ,
Arithmétique modulaire pour la cryptographie. Theses, 2005. ,
LLL for ideal lattices : re-evaluation of the security of gentry-halevi's fhe scheme. Designs, Codes and Cryptography, vol.76, pp.325-344, 2015. ,
Generalized Mersenne numbers, 1999. ,