Complete solving the quadratic equation mod 2ⁿ

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
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 ax² + bx + c = 0 (mod 2ⁿ), 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 ℤ_2ⁿ, which are used in symmetric cryptography.

Keywords

• Quadratic equation mod 2ⁿ
• 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 2^w. 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 x² = 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.