Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-28T05:22:08.061Z Has data issue: false hasContentIssue false
  • English
  • Français

On modular inverses of cyclotomic polynomials and the magnitude of their coefficients

Part of: Algebraic number theory: local and $p$-adic fields

Published online by Cambridge University Press:  01 April 2012

Clément Dunand
Clément Dunand*
Affiliation:
Institut de recherche mathématique de Rennes, Université de Rennes 1, Campus de Beaulieu F-35042 Rennes Cedex, France (email: [email protected])

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let p and r be two primes, and let n and m be two distinct divisors of pr. Consider Φn and Φm, the nth and mth cyclotomic polynomials. In this paper, we present lower and upper bounds for the coefficients of the inverse of Φn modulo Φm and discuss an application to torus-based cryptography.

MSC classification

Secondary: 11S05: Polynomials
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 15 , May 2012 , pp. 44 - 58
Copyright
Copyright © London Mathematical Society 2012

References

[1]Apostol, T. M., ‘Resultants of cyclotomic polynomials’, Proc. Amer. Math. Soc. 24 (1970) 457–462.CrossRefGoogle Scholar
[2]Bachman, G., ‘On the coefficients of ternary cyclotomic polynomials’, J. Number Theory 100 (2003) 104–116.CrossRefGoogle Scholar
[3]Bang, A. S., ‘Om Ligningen ϕn(x)=0’, Nyt Tidsskrift for Mathematic 6 (1895) 6–12.Google Scholar
[4]Bateman, P. T., ‘Note on the coefficients of the cyclotomic polynomial’, Bull. Amer. Math. Soc. 55 (1949) 1180–1181.CrossRefGoogle Scholar
[5]Beiter, M., ‘Magnitude of the coefficients of the cyclotomic polynomial F pqr’, Amer. Math. Monthly 75 (1968) 370–372.CrossRefGoogle Scholar
[6]Beiter, M., ‘Magnitude of the coefficients of the cyclotomic polynomial F pqr, II’, Duke Math. J. 38 (1971) 591–594.CrossRefGoogle Scholar
[7]Bloom, D. M., ‘On the coefficients of the cyclotomic polynomials’, Amer. Math. Monthly 75 (1968) 372–377.CrossRefGoogle Scholar
[8]Carlitz, L., ‘The number of terms in the cyclotomic polynomial F pqr’, Amer. Math. Monthly 73 (1966) 979–981.CrossRefGoogle Scholar
[9]Couveignes, J.-M., ‘Quelques mathématiques de la cryptologie à clés publiques’, Nouvelles méthodes mathématiques pour la cryptographie, Journée annuelle de la SMF 2007 (Société mathématique de France, Paris, 2007.Google Scholar
[10]Couveignes, J.-M. and Lercier, R., ‘Elliptic periods for finite fields’, Finite Fields Appl. 15 (2009) 1–22.CrossRefGoogle Scholar
[11]van Dijk, M. and Woodruff, D., ‘Asymptotically optimal communication for torus-based cryptography’, Crypto 2004, Lecture Notes in Computer Science 3152Springer, Berlin, 157–178.Google Scholar
[12]Dunand, C. and Lercier, R., ‘Elliptic bases and torus-based cryptography’, Ninth international conference on finite fields and applications (eds McGuire, G.et al.; American Mathematical Society, Providence, RI, 2009) 137–153.Google Scholar
[13]Erdös, P., ‘On the coefficients of the cyclotomic polynomial’, Bull. Amer. Math. Soc. 52 (1946) 179–184.CrossRefGoogle Scholar
[14]Gallot, Y. and Moree, P., ‘Ternary cyclotomic polynomials having a large coefficient’, J. reine angew. Math. 632 (2009) 105–125.Google Scholar
[15]Lam, T. Y. and Leung, K. H., ‘On the cyclotomic polynomial Φpq(X)’, Amer. Math. Monthly 103 (1996) 562–564.Google Scholar
[16]Lenstra, A. K. and Verheul, E. R., ‘The XTR public key system’, Advances in cryptology—Crypto 2000, Lecture Notes in Computer Science 1880 (ed. Bellare, M.; Springer, Berlin, 2000) 1–19.Google Scholar
[17]Migotti, A., ‘Zur Theorie der Kreisteilungsgleichung’, S.-B. der Math.-Naturwiss. Classe der Kaiserlichen Akademie der Wissenschaften, Wien 87 (1883) 7–14.Google Scholar
[18]Moree, P., ‘Inverse cyclotomic polynomials’, J. Number Theory 129 (2009) 667–680.CrossRefGoogle Scholar
[19]Rubin, K. and Silverberg, A., ‘Torus-based cryptography’, Crypto 2003, Lecture Notes in Computer Science 2729 (Springer, Berlin, 2003) 349–365.CrossRefGoogle Scholar
[20]Rubin, K. and Silverberg, A., ‘Algebraic tori in cryptography’, High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, Fields Institute Communications 41 (American Mathematical Society, Providence, RI, 2004) 317–326.Google Scholar
[21]Smith, P. J. and Lennon, M. J., ‘LUC: a new public key system’, Proceedings of the IFIP/SEC 1993 (Elsevier Science Publications, 1994).Google Scholar
[22]Voskresenskiĭ, V. E., Algebraic groups and their birational invariants, Translations of Mathematical Monographs 179 (American Mathematical Society, Providence, RI, 1991).Google Scholar
[23]Weil, A., Adeles and algebraic groups, Progress in Mathematics 23 (Birkhäuser, Boston, 1982).CrossRefGoogle Scholar
[24]von zur Gathen, J. and Gerhard, J., Modern computer algebra (Cambridge University Press, 1999).Google Scholar