Complete solving the quadratic equation mod 2n

S. M. Dehnavi, M. R. Mirzaee Shamsabad and A. Mahmoodi Rishakani
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 25, 2019, Number 1, Pages 75—83
DOI: 10.7546/nntdm.2019.25.1.75-83
Download full paper: PDF, 213 Kb

Details

Authors and affiliations

S. M. Dehnavi
Department of Mathematical and Computer Sciences
University of Kharazmi, Tehran, Iran

M. R. Mirzaee Shamsabad
Department of Mathematics
Shahid Beheshti University, Tehran, Iran

A. Mahmoodi Rishakani
Department of Sciences
Shahid Rajaee Teacher Training University, Tehran, Iran

Abstract

Quadratic functions have applications in cryptography. In this paper, we investigate the modular quadratic equation ax2 + bx + c = 0 (mod 2n), and provide a complete analysis of it. More precisely, we determine when this equation has a solution and in the case that it has a solution, we give not only the number of solutions, but also the set of solutions, in O(n) time. One of the interesting results of our research is that, if this equation has a solution, then the number of solutions is a power of two. Most notably, as an application, we characterize the number of fixed-points of quadratic permutation polynomials over ℤ2n, which are used in symmetric cryptography.

Keywords

  • Quadratic equation mod 2n
  • Number of solutions
  • Set of solutions
  • Number of fixedpoints
  • Cryptography

2010 Mathematics Subject Classification

  • 11Z05
  • 14G50

References

  1. Boesgaard, M., Vesterager, M., & Zenner, E. (2008). The Rabbit Stream Cipher. New Stream Cipher Designs – The eSTREAM Finalists, 69–83.
  2. Fraleigh, J. B. (1999). A First Course in Abstract Algebra. Sixth edition, Addison-Wesley Publishing Company Inc.
  3. Goresky, M., & Klapper, A. (2005). Algebraic Shift Register Sequences. Cambridge University Press.
  4. Rivest, R. L. (2001). Permutatin Polynomials modulo 2w. Finite Fields and Their Apllication, 7, 287–292.
  5. Rivest, R. L., Robshaw, M. J. B., Sidney, R., & Yin, Y. L. (1998). The RC6 Block Cipher. M.I.T., RSA Laboratories.
  6. Stinson, D. R. (2003). Cryptography – Theory and Practice. 3rd edn. Chapman and Hall/CRC, Boca Raton.
  7. Vincent, C. (2017). Notes on solving x2 = a (mod n), Available online: https://www.uvm.edu/~cvincen1/files/teaching/spring2017-math255/quadraticequation.pdf.
  8. Pommerening, K. (2000). Quadratic Equation in Finite Fields of Characteristic 2. English version (February 2012), Available online: http://www.klauspommerening.de/MathMisc/QuGlChar2.pdf.

Related papers

Cite this paper

Dehnavi, S. M., Mirzaee Shamsabad, M. R., & Mahmoodi Rishakani, A. (2019). Complete solving the quadratic equation mod 2n. Notes on Number Theory and Discrete Mathematics, 25(1), 75-83, doi: 10.7546/nntdm.2019.25.1.75-83.

Comments are closed.