Efficient Generation of Roots of Power Residues Modulo Powers of Two
Ferucio Laurenţiu Ţiplea · Mathematics · 2022
We propose a characterization for the roots of power residues modulo powers of two. By this characterization, the remainder of dividing a root by a power of two is uniformly distributed in a set with two odd integers, while the quotient is uniformly distributed in an initial segment of positive integers. This property allows us to generate roots of power residues modulo powers of two efficiently.