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 *ax*^{2} + *bx* + *c* = 0 (mod 2^{n}), 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 2
^{n} - Number of solutions
- Set of solutions
- Number of fixedpoints
- Cryptography

### 2010 Mathematics Subject Classification

- 11Z05
- 14G50

### References

- 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 2
. Finite Fields and Their Apllication, 7, 287–292.^{w} - 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
*x*^{2}=*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.

## Related papers

## Cite this paper

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

Dehnavi, S. M., M. R. Mirzaee Shamsabad and A. Mahmoodi Rishakani. “Complete Solving the Quadratic Equation mod 2* ^{n}*.” Notes on Number Theory and Discrete Mathematics 25, no. 1 (2019): 75-83, doi: 10.7546/nntdm.2019.25.1.75-83.

Dehnavi, S. M., M. R. Mirzaee Shamsabad and A. Mahmoodi Rishakani. “Complete Solving the Quadratic Equation mod 2* ^{n}*.” Notes on Number Theory and Discrete Mathematics 25.1 (2019): 75-83. Print, doi: 10.7546/nntdm.2019.25.1.75-83.