An informal enumeration of squares of 2k using rooted trees arising from congruences
Abstract
Certain cryptographic algorithms rely heavily on the hardness of quadratic residue problem. These algorithms would fail to provide efficient security if an easy solution of the problem is provided. In this piece of work an attempt is made to provide an analytical solution to the quadratic residue problem which is far less computationally intensive as compared to its numerical solution. For this purpose, we investigate a class of rooted trees arising from quadratic congruences. It is proved that the subgraph assigned by odd vertices is a full 4-ary rooted tree. It has been characterized that a vertex v of the rooted tree G(n) is a quadratic residue of n if and only if it is a non-leaf node. Finally, alternative explicit formulas for the enumeration of squares of 2k have been determined. © 2017 Utilitas Mathematica Publishing Inc.. All rights reserved.
