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