Cryptography Reference
In-Depth Information
10.4 Square Roots in Residue Class Rings
Now that we have calculated square roots of whole numbers, or their integer
parts, we turn our attention once again to residue classes, where we shall do
the same thing, that is, calculate square roots. Under certain assumptions there
exist square roots in residue class rings, though in general they are not uniquely
determined (that is, an element may have more than one square root). Put
algebraically, the question is to determine whether for an element a ∈ Z m there
exist roots b for which b 2 = a . In number-theoretic notation (see Chapter 5) this
would appear in congruence notation, and we would ask whether the quadratic
congruence x 2
a mod m has any solutions, and if it does, what they are.
If gcd( a, m )=1 and there exists a solution b with b 2
≡ a mod m ,then a is
called a quadratic residue modulo m . If there is no solution to the congruence,
then a is called a quadratic nonresidue modulo m .If b is a solution to the
congruence, then so is b + m , and therefore we can restrict our attention to those
residues that differ modulo m .
Let us clarify the situation with the help of an example: 2 is a quadratic
residue modulo 7, since 3 2
9 2( mod 7) , while 3 is a quadratic nonresidue
modulo 5.
In the case that m is a prime number, then the determination of square
roots modulo m is easy, and in the next chapter we shall present the functions
required for this purpose. However, the calculation of square roots modulo a
composite number depends on whether the prime factorization of m is known. If
it is not, then the determination of square roots for large m is a mathematically
difficult problem in the complexity class NP (see page 103), and it is this level of
complexity that ensures the security of modern cryptographic systems. 3
We shall
return to more elucidative examples in Section 10.4.4
The determination of whether a number has the property of being a quadratic
residue and the calculation of square roots are two different computational
problems each with its own particular algorithm, and in the following sections
we will provide explanations and implementations. We first consider procedures
for determining whether a number is a quadratic residue modulo a given
number. Then we shall calculate square roots modulo prime numbers, and in a
later section we shall give approaches to calculating square roots of composite
numbers.
3
The analogy between mathematical and cryptographic complexity should be approached with
caution: In [Rein] we are informed that the question of whether P
= NP has little relevance in
cryptographic practice. A polynomial algorithm for factorization with running time O n 20
would still be insuperable for even relatively small values of n , while an exponential algorithm
with running time O e n 0 . 1 would conquer even relatively large moduli. The security of
cryptographic procedures in practice is really not dependent on whether P and NP are the
same, despite the fact that one often sees precisely this formulation.
 
Search WWH ::




Custom Search