, 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)

. Références,

L. Babai, On Lovász' lattice reduction and the nearest lattice point problem, Combinatorica, vol.6, issue.1, pp.1-13, 1986.

J. C. Bajard, L. Imbert, and T. Plantard, 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

J. C. Bajard, L. Imbert, and T. Plantard, Modular number systems : Beyond the Mersenne family, Selected Areas in Cryptography, pp.159-169, 2005.
URL : https://hal.archives-ouvertes.fr/lirmm-00109208

P. D. Barrett, 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.

N. C. Bonciocat, On an irreducibility criterion of Perron for multivariate polynomials, Bull. Math. Soc. Sci. Math. Roumanie, vol.53, issue.101, pp.213-217, 2010.

N. C. Bonciocat, Schönemann-Eisenstein-Dumas-type irreducibility conditions that use arbitrarily many prime numbers, Journal Communications in Algebra, vol.43, issue.8, 2015.

L. Didier, F. Dosso, N. E. Mrabet, J. Marrez, and P. Véron, Randomization of Arithmetic over Polynomial Modular Number System, 26th IEEE International Symposium on Computer Arithmetic, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02099713

G. Dumas, Sur quelques cas d'irreductibilité des polynômes à coefficients rationnels, Journal de Mathématique Pure et Appliquée, vol.2, 1906.

C. Finch and L. Jones, On the irreducibility of -1,0,1-quadrinomials, INTE-GERS : Electronic Journal of Combinatorial Number Theory, issue.6, 2006.

S. D. Galbraith, Mathematics of Public Key Cryptography, 2012.

G. Hanrot, X. Pujol, and D. Stehlé, 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

D. Harvey and J. Van-der-hoeven, Faster integer multiplication using short lattice vectors, Thirteenth Algorithmic Number Theory Symposium ANTS XIII, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02350426

T. Laarhoven, J. Van-de-pol, and B. De-weger, Solving hard lattice problems and the security of lattice-based cryptosystems, Cryptology ePrint Archive, 2012.

W. Ljunggren, On the irreducibility of certain trinomials and quadrinomials, Mathematica Scandinavica, vol.8, issue.1, pp.65-70, 1960.

A. Menezes, S. A. Vanstone, and P. C. Van-oorschot, Handbook of Applied Cryptography, 1996.

D. Micciancio and S. Goldwasser, Complexity of Lattice Problems : a cryptographic perspective, The Kluwer International Series in Engineering and Computer Science, vol.671, 2002.

W. H. Mills, The factorization of certain quadrinomials, Mathematica Scandinavica, vol.57, 1985.

P. L. Montgomery, Modular multiplication without trial division, Mathematics of Computation, vol.44, pp.519-521, 1985.

P. Naudin and C. Quitté, Univariate polynomial factorization over finite fields, Theoretical Computer Science, vol.191, issue.1-2, pp.1-36, 1998.

T. Plantard, Arithmétique modulaire pour la cryptographie. Theses, 2005.

T. Plantard, W. Susilo, and Z. Zhang, 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.

J. A. Solinas, Generalized Mersenne numbers, 1999.