doi: 10.3934/amc.2022018
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

On Polynomial Modular Number Systems over $ \mathbb{Z}/{p}\mathbb{Z} $

1. 

Sorbonne Université, CNRS, Inria, Institut de Mathématiques de Jussieu, Paris Rive Gauche, France

2. 

Sorbonne Université, CNRS, Laboratoire d'informatique de Paris 6, Paris, France

3. 

Paypal, Emerging Technology Research Group, San Jose, USA

4. 

Laboratoire IMath, Université de Toulon, La Garde, France

Received  September 2021 Revised  February 2022 Early access March 2022

Since their introduction in 2004, Polynomial Modular Number Systems (PMNS) have become a very interesting tool for implementing cryptosystems relying on modular arithmetic in a secure and efficient way. However, while their implementation is simple, their parameterization is not trivial and relies on a suitable choice of the polynomial on which the PMNS operates. The initial proposals were based on particular binomials and trinomials. But these polynomials do not always provide systems with interesting characteristics such as small digits, fast reduction, etc.

In this work, we study a larger family of polynomials that can be exploited to design a safe and efficient PMNS. To do so, we first state a complete existence theorem for PMNS which provides bounds on the size of the digits for a generic polynomial, significantly improving previous bounds. Then, we present classes of suitable polynomials which provide numerous PMNS for safe and efficient arithmetic.

Citation: Jean-Claude Bajard, Jérémy Marrez, Thomas Plantard, Pascal Véron. On Polynomial Modular Number Systems over $ \mathbb{Z}/{p}\mathbb{Z} $. Advances in Mathematics of Communications, doi: 10.3934/amc.2022018
References:
[1]

M. Ajtai, The shortest vector problem in l2 is NP-hard for randomized reductions (extended abstract), Thirtieth Annual ACM Symposium on the Theory of Computing (STOC 1998), (1998), 10–19.

[2]

G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, J. Kelsey, Y.-K. Liu, C. Miller, D. Moody, R. Peralta, R. Perlner, A. Robinson and D. Smith-Tone, Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process, Tech. Report NIST IR 8309, National Institute of Standards and Technology, July 2020.

[3]

L. Babai, On Lovász' lattice reduction and the nearest lattice point problem, Combinatorica, 6 (1986), 1-13.  doi: 10.1007/BF02579403.

[4]

J. C. Bajard and S. Duquesne, Montgomery-friendly primes and applications to cryptography, Journal of Cryptographic Engineering, 11 (2021), 399-415.  doi: 10.1007/s13389-021-00260-z.

[5]

J.-C. Bajard, L. Imbert and T. Plantard, Arithmetic operations in the polynomial modular number system, 17th IEEE Symposium on Computer Arithmetic (ARITH'05), IEEE, (2005), 206–213. doi: 10.1109/ARITH.2005.11.

[6]

——, Modular number systems: Beyond the Mersenne family, Selected Areas in Cryptography, Springer, (2005), 159–169.

[7]

J.-C. Bajard, L. Imbert, P.-Y. Liardet and Y. Teglia, Leak resistant arithmetic, Cryptographic Hardware and Embedded Systems - CHES 2004 (Berlin, Heidelberg) (Marc Joye and Jean-Jacques Quisquater, eds.), Springer Berlin Heidelberg, (2004), 62–75. doi: 10.1007/978-3-540-28632-5_5.

[8]

P. Van Emde Boas, Another NP-Complete Problem and the Complexity of Computing Short Vectors in Lattices, Tech. Report 81-04, Mathematics Department, University of Amsterdam, 1981.

[9]

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

[10]

——, Schönemann–Eisenstein–Dumas-type irreducibility conditions that use arbitrarily many prime numbers, Journal Communications in Algebra, 43 (2015).

[11]

D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, Advances in Cryptology—CRYPTO 2001 (Santa Barbara, CA), Lecture Notes in Comput. Sci., Springer, Berlin, 2139 (2001), 213-229.  doi: 10.1007/3-540-44647-8_13.

[12]

J. W. BosC. CostelloH. Hisil and K. E. Lauter, Fast cryptography in genus 2, Advances in cryptology—EUROCRYPT 2013, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7881 (2013), 194-210.  doi: 10.1007/978-3-642-38348-9_12.

[13]

J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler and D. Stehle, Crystals–kyber: A CCA-secure module-lattice-based KEM, 3rd IEEE European Symposium on Security and Privacy, (2018), 353–367. doi: 10.1109/EuroSP.2018.00032.

[14]

C. Bouvier and L. Imbert, An alternative approach for SIDH arithmetic, Public-key cryptography—PKC 2021, Part I, Lecture Notes in Comput. Sci., Springer, Cham, 12710 (2021), 27-44.  doi: 10.1007/978-3-030-75245-3_2.

[15]

D. G. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Mathematics of Computation, 36 (1981), 587-592.  doi: 10.1090/S0025-5718-1981-0606517-5.

[16]

J. W. S. Cassels, An Introduction to the Geometry of Numbers, Classics in Mathematics, Springer-Verlag, Berlin, 1997.

[17]

A. ChaouchL.-S. DidierF. Y. DossoN. El MrabetB. Bouallegue and B. Ouni, Two hardware implementations for modular multiplication in the AMNS: Sequential and semi-parallel, J. Inf. Secur. Appl., 58 (2021), 102770.  doi: 10.1016/j.jisa.2021.102770.

[18]

T. Coladon, P. Elbaz-Vincent and C. Hugounenq, Mphell: A fast and robust library with unified and versatile arithmetics for elliptic curves cryptography, 2021 IEEE 28th Symposium on Computer Arithmetic (ARITH), (2021), 78–85. doi: 10.1109/ARITH51176.2021.00026.

[19]

J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, Grundlehren der mathematischen Wissenschaften, 290. Springer-Verlag, New York, 1988. doi: 10.1007/978-1-4757-2016-7.

[20]

R. Crandall, Method and Apparatus for Public Key Exchange in a Cryptographic System, U.S. Patent number 5159632, 1992.

[21]

J.-P. D'AnversA. KarmakarS. Sinha Roy and F. Vercauteren, Saber: Module-lwr based key exchange, CPA-secure encryption and CCA-secure KEM, Progress in cryptology—AFRICACRYPT 2018, Lecture Notes in Comput. Sci., Springer, Cham, 10831 (2018), 282-305.  doi: 10.1007/978-3-319-89339-6_16.

[22]

L.-S. DidierF.-Y. DossoN. El MrabetJ. Marrez and P. Véron, Randomization of arithmetic over polynomial modular number system, 26th IEEE International Symposium on Computer Arithmetic, IEEE Computer Society, 1 (2019), 199-206.  doi: 10.1109/ARITH.2019.00048.

[23]

L.-S. DidierF.-Y. Dosso and P. Véron, Efficient modular operations using the adapted modular number system, Journal of Cryptographic Engineering, 10 (2020), 111-133.  doi: 10.1007/s13389-019-00221-7.

[24]

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

[25]

N. El Mrabet and N. Gama, Efficient multiplication over extension fields, Arithmetic of Finite Fields, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7369 (2012), 136-151.  doi: 10.1007/978-3-642-31662-3_10.

[26]

N. El Mrabet and C. Nègre, Finite field multiplication combining AMNS and DFT approach for pairing cryptography, ACISP, Lecture Notes in Computer Science, Springer, 5594 (2009), 422-436. 

[27]

C. Finch and L. Jones, On the irreducibility of $\{-1, 0, 1\}$-quadrinomials, INTEGERS: Electronic Journal of Combinatorial Number Theory, 6 (2006), A16, 4 pp.

[28] S. D. Galbraith, Mathematics of Public Key Cryptography, Cambridge University Press, Cambridge, 2012.  doi: 10.1017/CBO9781139012843.
[29]

V. Guruswami, D. Micciancio and O. Regev, The complexity of the covering radius problem on lattices and codes, IEEE Conference on Computational Complexity, (2004), 161–173.

[30]

M. Hamburg, Fast and compact elliptic-curve cryptography, IACR Cryptol. ePrint Arch., 2012 (2012), 309. 

[31]

G. HanrotX. Pujol and D. Stehlé, Algorithms for the shortest and closest lattice vector problems, Coding and Cryptology, Lecture Notes in Comput. Sci., Springer, Heidelberg, 6639 (2011), 159-190.  doi: 10.1007/978-3-642-20901-7_10.

[32]

G. Hanrot and D. Stehle, Improved analysis of Kannan's shortest lattice vector algorithm, Advances in Cryptology—CRYPTO 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4622 (2007), 170-186.  doi: 10.1007/978-3-540-74143-5_10.

[33]

D. Harvey and J. van der Hoeven, Faster integer multiplication using short lattice vectors, Proceedings of the Thirteenth Algorithmic Number Theory Symposium, Open Book Ser., Math. Sci. Publ., Berkeley, CA, 2 2019,293–310.

[34]

J. HoffsteinJ. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, Algorithmic Number Theory (ANTS 1998), LNCS, Springer, 1423 (1998), 267-288.  doi: 10.1007/BFb0054868.

[35]

D. Jao, R. Azarderakhsh, M. Campagna, C. Costello, L. De Feo, B. Hess, A. Jalali, B. Koziel, B. LaMacchia, P. Longa, M. Naehrig, G. Pereira, J. Renes, V. Soukharev and D. Urbanik, SIKE: Supersingular Isogeny Key Encapsulation, Submission to the NIST's Post-Quantum Cryptography Standardization Process, 2019.

[36]

N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, 48 (1987), 203-209.  doi: 10.1090/S0025-5718-1987-0866109-5.

[37]

A. Korkine and G. Zolotareff, Sur les formes quadratiques, Mathematische Annalen, 6 (1873), 366-389.  doi: 10.1007/BF01442795.

[38]

J. C. LagariasH. W. Lenstra and C.-P. Schnorr, Korkin-zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica, 10 (1990), 333-348.  doi: 10.1007/BF02128669.

[39]

A. K. LenstraH. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 513-534.  doi: 10.1007/BF01457454.

[40]

W. Ljunggren, On the irreducibility of certain trinomials and quadrinomials, Mathematica Scandinavica, 8 (1960), 65-70.  doi: 10.7146/math.scand.a-10593.

[41]

L. Lovász, An Algorithmic Theory of Numbers, Graphs and Convexity, CBMS-NSF Regional Conference Series in Applied Mathematics, 50, SIAM Publications, 1986. doi: 10.1137/1.9781611970203.

[42]

V. S. Miller, Use of elliptic curves in cryptography, Advances in Cryptology—CRYPTO '85 (Santa Barbara, Calif., 1985), Lecture Notes in Comput. Sci., Springer, Berlin, 218 (1986), 417–426. doi: 10.1007/3-540-39799-X_31.

[43]

W. H. Mills, The factorization of certain quadrinomials, Mathematica Scandinavica, 57 (1985), 44-50.  doi: 10.7146/math.scand.a-12105.

[44]

H. Minkowski, Geometrie der Zahlen, B. G. Teubner, Leipzig, 1896.

[45]

P. L. Montgomery, Modular multiplication without trial division, Mathematics of Computation, 44 (1985), 519-521.  doi: 10.1090/S0025-5718-1985-0777282-X.

[46]

D. Moody, G. Alagic, D. Apon, D. Cooper, Q. Dang, J. Kelsey, Y.-K. Liu, C. Miller, R. Peralta, Ra. Perlner, A. Robinson, D. Smith-Tone and J. Alperin-Sheriff, Status Report on the Second Round of the Nist Post-Quantum Cryptography Standardization Process, 2020-07-22 2020. doi: 10.6028/NIST.IR.8309.

[47]

National Institute for Standards and Technology, Digital Signature Standard (DSS), Jun 2009.

[48]

C. Negre and T. Plantard, Efficient modular arithmetic in adapted modular number system using lagrange representation, ACISP 2008: Information Security and Privacy, 463–477. doi: 10.1007/978-3-540-70500-0_34.

[49]

C. Negre, Side Channel Counter-Measures Based on Randomized AMNS Modular Multiplication, Proceedings of the 18th International Conference on Security and Cryptography, SCITEPRESS - Science and Technology Publications, 2021.

[50]

T. Plantard, Arithmétique Modulaire Pour la Cryptographie, Theses, Université Montpellier II - Sciences et Techniques du Languedoc, 2005.

[51]

T. PlantardW. Susilo and Z. Zhang, LLL for ideal lattices: Re-evaluation of the security of gentry–halevi's fhe scheme, Designs, Codes and Cryptography, 76 (2015), 325-344.  doi: 10.1007/s10623-014-9957-1.

[52]

T. Prest, P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Ricosset, G. Seiler, W. Whyte and Z. Zhang, Falcon: Fast-Fourier Lattice-Based Compact Signatures Over NTRU, Submission to the NIST's post-quantum cryptography standardization process, 2017.

[53]

R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 21 (1978), 120–126. doi: 10.1145/359340.359342.

[54]

C.-P. Schnorr, Block reduced lattice bases and successive minima, Combin. Probab. Comput., 3 (1994), 507-522.  doi: 10.1017/S0963548300001371.

[55]

J. A. Solinas, Generalized Mersenne Numbers, Research Report CORR-99-39, Center for Applied Cryptographic Research, University of Waterloo, Waterloo, ON, Canada, 1999.

[56]

D. R. Stinson and M. Paterson, Cryptography Theory and Practice, Fourth edition ed., Chapman and Hall/CRC, 2018.

show all references

References:
[1]

M. Ajtai, The shortest vector problem in l2 is NP-hard for randomized reductions (extended abstract), Thirtieth Annual ACM Symposium on the Theory of Computing (STOC 1998), (1998), 10–19.

[2]

G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, J. Kelsey, Y.-K. Liu, C. Miller, D. Moody, R. Peralta, R. Perlner, A. Robinson and D. Smith-Tone, Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process, Tech. Report NIST IR 8309, National Institute of Standards and Technology, July 2020.

[3]

L. Babai, On Lovász' lattice reduction and the nearest lattice point problem, Combinatorica, 6 (1986), 1-13.  doi: 10.1007/BF02579403.

[4]

J. C. Bajard and S. Duquesne, Montgomery-friendly primes and applications to cryptography, Journal of Cryptographic Engineering, 11 (2021), 399-415.  doi: 10.1007/s13389-021-00260-z.

[5]

J.-C. Bajard, L. Imbert and T. Plantard, Arithmetic operations in the polynomial modular number system, 17th IEEE Symposium on Computer Arithmetic (ARITH'05), IEEE, (2005), 206–213. doi: 10.1109/ARITH.2005.11.

[6]

——, Modular number systems: Beyond the Mersenne family, Selected Areas in Cryptography, Springer, (2005), 159–169.

[7]

J.-C. Bajard, L. Imbert, P.-Y. Liardet and Y. Teglia, Leak resistant arithmetic, Cryptographic Hardware and Embedded Systems - CHES 2004 (Berlin, Heidelberg) (Marc Joye and Jean-Jacques Quisquater, eds.), Springer Berlin Heidelberg, (2004), 62–75. doi: 10.1007/978-3-540-28632-5_5.

[8]

P. Van Emde Boas, Another NP-Complete Problem and the Complexity of Computing Short Vectors in Lattices, Tech. Report 81-04, Mathematics Department, University of Amsterdam, 1981.

[9]

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

[10]

——, Schönemann–Eisenstein–Dumas-type irreducibility conditions that use arbitrarily many prime numbers, Journal Communications in Algebra, 43 (2015).

[11]

D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, Advances in Cryptology—CRYPTO 2001 (Santa Barbara, CA), Lecture Notes in Comput. Sci., Springer, Berlin, 2139 (2001), 213-229.  doi: 10.1007/3-540-44647-8_13.

[12]

J. W. BosC. CostelloH. Hisil and K. E. Lauter, Fast cryptography in genus 2, Advances in cryptology—EUROCRYPT 2013, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7881 (2013), 194-210.  doi: 10.1007/978-3-642-38348-9_12.

[13]

J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler and D. Stehle, Crystals–kyber: A CCA-secure module-lattice-based KEM, 3rd IEEE European Symposium on Security and Privacy, (2018), 353–367. doi: 10.1109/EuroSP.2018.00032.

[14]

C. Bouvier and L. Imbert, An alternative approach for SIDH arithmetic, Public-key cryptography—PKC 2021, Part I, Lecture Notes in Comput. Sci., Springer, Cham, 12710 (2021), 27-44.  doi: 10.1007/978-3-030-75245-3_2.

[15]

D. G. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Mathematics of Computation, 36 (1981), 587-592.  doi: 10.1090/S0025-5718-1981-0606517-5.

[16]

J. W. S. Cassels, An Introduction to the Geometry of Numbers, Classics in Mathematics, Springer-Verlag, Berlin, 1997.

[17]

A. ChaouchL.-S. DidierF. Y. DossoN. El MrabetB. Bouallegue and B. Ouni, Two hardware implementations for modular multiplication in the AMNS: Sequential and semi-parallel, J. Inf. Secur. Appl., 58 (2021), 102770.  doi: 10.1016/j.jisa.2021.102770.

[18]

T. Coladon, P. Elbaz-Vincent and C. Hugounenq, Mphell: A fast and robust library with unified and versatile arithmetics for elliptic curves cryptography, 2021 IEEE 28th Symposium on Computer Arithmetic (ARITH), (2021), 78–85. doi: 10.1109/ARITH51176.2021.00026.

[19]

J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, Grundlehren der mathematischen Wissenschaften, 290. Springer-Verlag, New York, 1988. doi: 10.1007/978-1-4757-2016-7.

[20]

R. Crandall, Method and Apparatus for Public Key Exchange in a Cryptographic System, U.S. Patent number 5159632, 1992.

[21]

J.-P. D'AnversA. KarmakarS. Sinha Roy and F. Vercauteren, Saber: Module-lwr based key exchange, CPA-secure encryption and CCA-secure KEM, Progress in cryptology—AFRICACRYPT 2018, Lecture Notes in Comput. Sci., Springer, Cham, 10831 (2018), 282-305.  doi: 10.1007/978-3-319-89339-6_16.

[22]

L.-S. DidierF.-Y. DossoN. El MrabetJ. Marrez and P. Véron, Randomization of arithmetic over polynomial modular number system, 26th IEEE International Symposium on Computer Arithmetic, IEEE Computer Society, 1 (2019), 199-206.  doi: 10.1109/ARITH.2019.00048.

[23]

L.-S. DidierF.-Y. Dosso and P. Véron, Efficient modular operations using the adapted modular number system, Journal of Cryptographic Engineering, 10 (2020), 111-133.  doi: 10.1007/s13389-019-00221-7.

[24]

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

[25]

N. El Mrabet and N. Gama, Efficient multiplication over extension fields, Arithmetic of Finite Fields, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7369 (2012), 136-151.  doi: 10.1007/978-3-642-31662-3_10.

[26]

N. El Mrabet and C. Nègre, Finite field multiplication combining AMNS and DFT approach for pairing cryptography, ACISP, Lecture Notes in Computer Science, Springer, 5594 (2009), 422-436. 

[27]

C. Finch and L. Jones, On the irreducibility of $\{-1, 0, 1\}$-quadrinomials, INTEGERS: Electronic Journal of Combinatorial Number Theory, 6 (2006), A16, 4 pp.

[28] S. D. Galbraith, Mathematics of Public Key Cryptography, Cambridge University Press, Cambridge, 2012.  doi: 10.1017/CBO9781139012843.
[29]

V. Guruswami, D. Micciancio and O. Regev, The complexity of the covering radius problem on lattices and codes, IEEE Conference on Computational Complexity, (2004), 161–173.

[30]

M. Hamburg, Fast and compact elliptic-curve cryptography, IACR Cryptol. ePrint Arch., 2012 (2012), 309. 

[31]

G. HanrotX. Pujol and D. Stehlé, Algorithms for the shortest and closest lattice vector problems, Coding and Cryptology, Lecture Notes in Comput. Sci., Springer, Heidelberg, 6639 (2011), 159-190.  doi: 10.1007/978-3-642-20901-7_10.

[32]

G. Hanrot and D. Stehle, Improved analysis of Kannan's shortest lattice vector algorithm, Advances in Cryptology—CRYPTO 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4622 (2007), 170-186.  doi: 10.1007/978-3-540-74143-5_10.

[33]

D. Harvey and J. van der Hoeven, Faster integer multiplication using short lattice vectors, Proceedings of the Thirteenth Algorithmic Number Theory Symposium, Open Book Ser., Math. Sci. Publ., Berkeley, CA, 2 2019,293–310.

[34]

J. HoffsteinJ. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, Algorithmic Number Theory (ANTS 1998), LNCS, Springer, 1423 (1998), 267-288.  doi: 10.1007/BFb0054868.

[35]

D. Jao, R. Azarderakhsh, M. Campagna, C. Costello, L. De Feo, B. Hess, A. Jalali, B. Koziel, B. LaMacchia, P. Longa, M. Naehrig, G. Pereira, J. Renes, V. Soukharev and D. Urbanik, SIKE: Supersingular Isogeny Key Encapsulation, Submission to the NIST's Post-Quantum Cryptography Standardization Process, 2019.

[36]

N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, 48 (1987), 203-209.  doi: 10.1090/S0025-5718-1987-0866109-5.

[37]

A. Korkine and G. Zolotareff, Sur les formes quadratiques, Mathematische Annalen, 6 (1873), 366-389.  doi: 10.1007/BF01442795.

[38]

J. C. LagariasH. W. Lenstra and C.-P. Schnorr, Korkin-zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica, 10 (1990), 333-348.  doi: 10.1007/BF02128669.

[39]

A. K. LenstraH. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 513-534.  doi: 10.1007/BF01457454.

[40]

W. Ljunggren, On the irreducibility of certain trinomials and quadrinomials, Mathematica Scandinavica, 8 (1960), 65-70.  doi: 10.7146/math.scand.a-10593.

[41]

L. Lovász, An Algorithmic Theory of Numbers, Graphs and Convexity, CBMS-NSF Regional Conference Series in Applied Mathematics, 50, SIAM Publications, 1986. doi: 10.1137/1.9781611970203.

[42]

V. S. Miller, Use of elliptic curves in cryptography, Advances in Cryptology—CRYPTO '85 (Santa Barbara, Calif., 1985), Lecture Notes in Comput. Sci., Springer, Berlin, 218 (1986), 417–426. doi: 10.1007/3-540-39799-X_31.

[43]

W. H. Mills, The factorization of certain quadrinomials, Mathematica Scandinavica, 57 (1985), 44-50.  doi: 10.7146/math.scand.a-12105.

[44]

H. Minkowski, Geometrie der Zahlen, B. G. Teubner, Leipzig, 1896.

[45]

P. L. Montgomery, Modular multiplication without trial division, Mathematics of Computation, 44 (1985), 519-521.  doi: 10.1090/S0025-5718-1985-0777282-X.

[46]

D. Moody, G. Alagic, D. Apon, D. Cooper, Q. Dang, J. Kelsey, Y.-K. Liu, C. Miller, R. Peralta, Ra. Perlner, A. Robinson, D. Smith-Tone and J. Alperin-Sheriff, Status Report on the Second Round of the Nist Post-Quantum Cryptography Standardization Process, 2020-07-22 2020. doi: 10.6028/NIST.IR.8309.

[47]

National Institute for Standards and Technology, Digital Signature Standard (DSS), Jun 2009.

[48]

C. Negre and T. Plantard, Efficient modular arithmetic in adapted modular number system using lagrange representation, ACISP 2008: Information Security and Privacy, 463–477. doi: 10.1007/978-3-540-70500-0_34.

[49]

C. Negre, Side Channel Counter-Measures Based on Randomized AMNS Modular Multiplication, Proceedings of the 18th International Conference on Security and Cryptography, SCITEPRESS - Science and Technology Publications, 2021.

[50]

T. Plantard, Arithmétique Modulaire Pour la Cryptographie, Theses, Université Montpellier II - Sciences et Techniques du Languedoc, 2005.

[51]

T. PlantardW. Susilo and Z. Zhang, LLL for ideal lattices: Re-evaluation of the security of gentry–halevi's fhe scheme, Designs, Codes and Cryptography, 76 (2015), 325-344.  doi: 10.1007/s10623-014-9957-1.

[52]

T. Prest, P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Ricosset, G. Seiler, W. Whyte and Z. Zhang, Falcon: Fast-Fourier Lattice-Based Compact Signatures Over NTRU, Submission to the NIST's post-quantum cryptography standardization process, 2017.

[53]

R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 21 (1978), 120–126. doi: 10.1145/359340.359342.

[54]

C.-P. Schnorr, Block reduced lattice bases and successive minima, Combin. Probab. Comput., 3 (1994), 507-522.  doi: 10.1017/S0963548300001371.

[55]

J. A. Solinas, Generalized Mersenne Numbers, Research Report CORR-99-39, Center for Applied Cryptographic Research, University of Waterloo, Waterloo, ON, Canada, 1999.

[56]

D. R. Stinson and M. Paterson, Cryptography Theory and Practice, Fourth edition ed., Chapman and Hall/CRC, 2018.

Table 1.  Elements of $ \mathbb{Z}/31\mathbb{Z} $ are represented as polynomials in $ \gamma $, noted as vectors with lowest degree first. The reduction polynomial is $ E(X) = X^4-2 $ and $ {\gamma = 15} $ is a root of $ E(X) $. The digit set is $ \{ -1, 0, 1\} $ (i.e., $ \rho = 2 $)
0 1 2 3 4 5
(0, 0, 0, 0) (1, 0, 0, 0) (-1, 1, -1, 1) \begin{array}{*{20}{c}} (-1, -1, -1, 1)\\ (-1, 0, 0, -1)\\ (-1, 0, 1, 1)\\ (0, 1, -1, 1) \end{array} \begin{array}{*{20}{c}} (0, -1, -1, 1)\\ (0, 0, 0, -1)\\ (0, 0, 1, 1)\\ (1, 1, -1, 1) \end{array} \begin{array}{*{20}{c}} (1, -1, -1, 1)\\ (1, 0, 0, -1)\\ (1, 0, 1, 1) \end{array}
6 7 8 9 10 11
(-1, 1, -1, 0) \begin{array}{*{20}{c}} (-1, -1, -1, 0)\\ (-1, 0, 1, 0)\\ (0, 1, -1, 0) \end{array} \begin{array}{*{20}{c}} (0, -1, -1, 0)\\ (0, 0, 1, 0)\\ (1, 1, -1, 0) \end{array} \begin{array}{*{20}{c}} (1, -1, -1, 0)\\ (1, 0, 1, 0) \end{array} \begin{array}{*{20}{c}} (-1, 1, -1, -1)\\ (-1, 1, 0, 1) \end{array} \begin{array}{*{20}{c}} (-1, -1, -1, -1)\\ (-1, -1, 0, 1)\\ (-1, 0, 1, -1)\\ (0, 1, -1, -1)\\ (0, 1, 0, 1) \end{array}
12 13 14 15 16 17
\begin{array}{*{20}{c}} (0, -1, -1, -1)\\ (0, -1, 0, 1)\\ (0, 0, 1, -1)\\ (1, 1, -1, -1)\\ (1, 1, 0, 1) \end{array} \begin{array}{*{20}{c}} (1, -1, -1, -1)\\ (1, -1, 0, 1)\\ (1, 0, 1, -1) \end{array} (-1, 1, 0, 0) \begin{array}{*{20}{c}} (-1, -1, 0, 0)\\ (0, 1, 0, 0) \end{array} \begin{array}{*{20}{c}} (0, -1, 0, 0)\\ (1, 1, 0, 0) \end{array} (1, -1, 0, 0)
18 19 20 21 22 23
\begin{array}{*{20}{c}} (-1, 0, -1, 1)\\ (-1, 1, 0, -1)\\ (-1, 1, 1, 1) \end{array} \begin{array}{*{20}{c}} (-1, -1, 0, -1)\\ (-1, -1, 1, 1)\\ (0, 0, -1, 1)\\ (0, 1, 0, -1)\\ (0, 1, 1, 1) \end{array} \begin{array}{*{20}{c}} (0, -1, 0, -1)\\ (0, -1, 1, 1)\\ (1, 0, -1, 1)\\ (1, 1, 0, -1)\\ (1, 1, 1, 1) \end{array} \begin{array}{*{20}{c}} (1, -1, 0, -1)\\ (1, -1, 1, 1) \end{array} \begin{array}{*{20}{c}} (-1, 0, -1, 0)\\ (-1, 1, 1, 0) \end{array} \begin{array}{*{20}{c}} (-1, -1, 1, 0)\\ (0, 0, -1, 0)\\ (0, 1, 1, 0) \end{array}
24 25 26 27 28 29
\begin{array}{*{20}{c}} (0, -1, 1, 0)\\ (1, 0, -1, 0)\\ (1, 1, 1, 0) \end{array} (1, -1, 1, 0) \begin{array}{*{20}{c}} (-1, 0, -1, -1)\\ (-1, 0, 0, 1)\\ (-1, 1, 1, -1) \end{array} \begin{array}{*{20}{c}} (-1, -1, 1, -1)\\ (0, 0, -1, -1)\\ (0, 0, 0, 1)\\ (0, 1, 1, -1) \end{array} \begin{array}{*{20}{c}} (0, -1, 1, -1)\\ (1, 0, -1, -1)\\ (1, 0, 0, 1)\\ (1, 1, 1, -1) \end{array} (1, -1, 1, -1)
30
(-1, 0, 0, 0)
0 1 2 3 4 5
(0, 0, 0, 0) (1, 0, 0, 0) (-1, 1, -1, 1) \begin{array}{*{20}{c}} (-1, -1, -1, 1)\\ (-1, 0, 0, -1)\\ (-1, 0, 1, 1)\\ (0, 1, -1, 1) \end{array} \begin{array}{*{20}{c}} (0, -1, -1, 1)\\ (0, 0, 0, -1)\\ (0, 0, 1, 1)\\ (1, 1, -1, 1) \end{array} \begin{array}{*{20}{c}} (1, -1, -1, 1)\\ (1, 0, 0, -1)\\ (1, 0, 1, 1) \end{array}
6 7 8 9 10 11
(-1, 1, -1, 0) \begin{array}{*{20}{c}} (-1, -1, -1, 0)\\ (-1, 0, 1, 0)\\ (0, 1, -1, 0) \end{array} \begin{array}{*{20}{c}} (0, -1, -1, 0)\\ (0, 0, 1, 0)\\ (1, 1, -1, 0) \end{array} \begin{array}{*{20}{c}} (1, -1, -1, 0)\\ (1, 0, 1, 0) \end{array} \begin{array}{*{20}{c}} (-1, 1, -1, -1)\\ (-1, 1, 0, 1) \end{array} \begin{array}{*{20}{c}} (-1, -1, -1, -1)\\ (-1, -1, 0, 1)\\ (-1, 0, 1, -1)\\ (0, 1, -1, -1)\\ (0, 1, 0, 1) \end{array}
12 13 14 15 16 17
\begin{array}{*{20}{c}} (0, -1, -1, -1)\\ (0, -1, 0, 1)\\ (0, 0, 1, -1)\\ (1, 1, -1, -1)\\ (1, 1, 0, 1) \end{array} \begin{array}{*{20}{c}} (1, -1, -1, -1)\\ (1, -1, 0, 1)\\ (1, 0, 1, -1) \end{array} (-1, 1, 0, 0) \begin{array}{*{20}{c}} (-1, -1, 0, 0)\\ (0, 1, 0, 0) \end{array} \begin{array}{*{20}{c}} (0, -1, 0, 0)\\ (1, 1, 0, 0) \end{array} (1, -1, 0, 0)
18 19 20 21 22 23
\begin{array}{*{20}{c}} (-1, 0, -1, 1)\\ (-1, 1, 0, -1)\\ (-1, 1, 1, 1) \end{array} \begin{array}{*{20}{c}} (-1, -1, 0, -1)\\ (-1, -1, 1, 1)\\ (0, 0, -1, 1)\\ (0, 1, 0, -1)\\ (0, 1, 1, 1) \end{array} \begin{array}{*{20}{c}} (0, -1, 0, -1)\\ (0, -1, 1, 1)\\ (1, 0, -1, 1)\\ (1, 1, 0, -1)\\ (1, 1, 1, 1) \end{array} \begin{array}{*{20}{c}} (1, -1, 0, -1)\\ (1, -1, 1, 1) \end{array} \begin{array}{*{20}{c}} (-1, 0, -1, 0)\\ (-1, 1, 1, 0) \end{array} \begin{array}{*{20}{c}} (-1, -1, 1, 0)\\ (0, 0, -1, 0)\\ (0, 1, 1, 0) \end{array}
24 25 26 27 28 29
\begin{array}{*{20}{c}} (0, -1, 1, 0)\\ (1, 0, -1, 0)\\ (1, 1, 1, 0) \end{array} (1, -1, 1, 0) \begin{array}{*{20}{c}} (-1, 0, -1, -1)\\ (-1, 0, 0, 1)\\ (-1, 1, 1, -1) \end{array} \begin{array}{*{20}{c}} (-1, -1, 1, -1)\\ (0, 0, -1, -1)\\ (0, 0, 0, 1)\\ (0, 1, 1, -1) \end{array} \begin{array}{*{20}{c}} (0, -1, 1, -1)\\ (1, 0, -1, -1)\\ (1, 0, 0, 1)\\ (1, 1, 1, -1) \end{array} (1, -1, 1, -1)
30
(-1, 0, 0, 0)
[1]

Wenzhi Luo, Zeév Rudnick, Peter Sarnak. The variance of arithmetic measures associated to closed geodesics on the modular surface. Journal of Modern Dynamics, 2009, 3 (2) : 271-309. doi: 10.3934/jmd.2009.3.271

[2]

Min Li, Maoan Han. On the number of limit cycles of a quartic polynomial system. Discrete and Continuous Dynamical Systems - S, 2021, 14 (9) : 3167-3181. doi: 10.3934/dcdss.2020337

[3]

Palash Sarkar, Shashank Singh. A unified polynomial selection method for the (tower) number field sieve algorithm. Advances in Mathematics of Communications, 2019, 13 (3) : 435-455. doi: 10.3934/amc.2019028

[4]

Igor E. Shparlinski. Close values of shifted modular inversions and the decisional modular inversion hidden number problem. Advances in Mathematics of Communications, 2015, 9 (2) : 169-176. doi: 10.3934/amc.2015.9.169

[5]

Sergey Shemyakov, Roman Chernov, Dzmitry Rumiantsau, Dierk Schleicher, Simon Schmitt, Anton Shemyakov. Finding polynomial roots by dynamical systems – A case study. Discrete and Continuous Dynamical Systems, 2020, 40 (12) : 6945-6965. doi: 10.3934/dcds.2020261

[6]

Antonio Garijo, Xavier Jarque. The secant map applied to a real polynomial with multiple roots. Discrete and Continuous Dynamical Systems, 2020, 40 (12) : 6783-6794. doi: 10.3934/dcds.2020133

[7]

Xiaolu Hou, Frédérique Oggier. Modular lattices from a variation of construction a over number fields. Advances in Mathematics of Communications, 2017, 11 (4) : 719-745. doi: 10.3934/amc.2017053

[8]

Manish K. Gupta, Chinnappillai Durairajan. On the covering radius of some modular codes. Advances in Mathematics of Communications, 2014, 8 (2) : 129-137. doi: 10.3934/amc.2014.8.129

[9]

John Fogarty. On Noether's bound for polynomial invariants of a finite group. Electronic Research Announcements, 2001, 7: 5-7.

[10]

Freddy Dumortier. Sharp upperbounds for the number of large amplitude limit cycles in polynomial Lienard systems. Discrete and Continuous Dynamical Systems, 2012, 32 (5) : 1465-1479. doi: 10.3934/dcds.2012.32.1465

[11]

Armengol Gasull, Hector Giacomini. Upper bounds for the number of limit cycles of some planar polynomial differential systems. Discrete and Continuous Dynamical Systems, 2010, 27 (1) : 217-229. doi: 10.3934/dcds.2010.27.217

[12]

Dubi Kelmer. Quadratic irrationals and linking numbers of modular knots. Journal of Modern Dynamics, 2012, 6 (4) : 539-561. doi: 10.3934/jmd.2012.6.539

[13]

Robert L. Griess Jr., Ching Hung Lam. Groups of Lie type, vertex algebras, and modular moonshine. Electronic Research Announcements, 2014, 21: 167-176. doi: 10.3934/era.2014.21.167

[14]

Eric Dubach, Robert Luce, Jean-Marie Thomas. Pseudo-Conform Polynomial Lagrange Finite Elements on Quadrilaterals and Hexahedra. Communications on Pure and Applied Analysis, 2009, 8 (1) : 237-254. doi: 10.3934/cpaa.2009.8.237

[15]

László Mérai, Igor E. Shparlinski. Unlikely intersections over finite fields: Polynomial orbits in small subgroups. Discrete and Continuous Dynamical Systems, 2020, 40 (2) : 1065-1073. doi: 10.3934/dcds.2020070

[16]

Gheorghe Craciun, Baltazar Aguda, Avner Friedman. Mathematical Analysis Of A Modular Network Coordinating The Cell Cycle And Apoptosis. Mathematical Biosciences & Engineering, 2005, 2 (3) : 473-485. doi: 10.3934/mbe.2005.2.473

[17]

Bram van Asch, Frans Martens. A note on the minimum Lee distance of certain self-dual modular codes. Advances in Mathematics of Communications, 2012, 6 (1) : 65-68. doi: 10.3934/amc.2012.6.65

[18]

Antoni Ferragut, Jaume Llibre, Adam Mahdi. Polynomial inverse integrating factors for polynomial vector fields. Discrete and Continuous Dynamical Systems, 2007, 17 (2) : 387-395. doi: 10.3934/dcds.2007.17.387

[19]

Laura DeMarco, Kevin Pilgrim. Hausdorffization and polynomial twists. Discrete and Continuous Dynamical Systems, 2011, 29 (4) : 1405-1417. doi: 10.3934/dcds.2011.29.1405

[20]

Azniv Kasparian, Ivan Marinov. Duursma's reduced polynomial. Advances in Mathematics of Communications, 2017, 11 (4) : 647-669. doi: 10.3934/amc.2017048

2021 Impact Factor: 1.015

Article outline

Figures and Tables

[Back to Top]