Problem 10 - A Computational Introduction to Number Theory and Algebra

Question

Show that the following two problems are deterministic, polytime equivalent (see discussion just above Exercise 11.10 in \(\S 11.3\) ): (a) Given an odd prime \(p\) and \(\alpha \in\left(\mathbb{Z}_{p}^{*}\right)^{2},\) find \(\beta \in \mathbb{Z}_{p}^{*}\) such that \(\beta^{2}=\alpha\). (b) Given an odd prime \(p,\) find an element of \(\mathbb{Z}_{p}^{*} \backslash\left(\mathbb{Z}_{p}^{*}\right)^{2}\).

Step-by-Step Solution

Answer

Explain your answer. Answer: Yes, problems (a) and (b) are deterministic, polytime equivalent. This is because we can construct the solution to one problem using the solution to the other problem in polynomial time. Given a deterministic, polytime solution to Problem (b), we can find a square root modulo \(p\) for Problem (a) by using the non-square found in Problem (b). Similarly, if we have a deterministic, polytime solution for Problem (a), we can find a non-square modulo \(p\) for Problem (b) by attempting to find square roots for different numbers. Thus, the equivalence between these two problems is established in polynomial time.

Step 1: Constructing the solution to Problem (a) from the solution to Problem (b)

Given a deterministic, polytime solution to Problem (b), it is possible to construct the solution to Problem (a). The solution to Problem (b) finds a non-square modulo \(p\). We can use this non-square to find \(\beta\) such that \(\beta^2 \equiv \alpha \pmod p\). Since the non-square we get from the solution to (b) has a square root modulo \(p\), we can multiply this square root with \(\alpha\) to get the square root for \(\beta\) in Problem (a).

Step 2: Constructing the solution to Problem (b) from the solution to Problem (a)

To show that solving Problem (a) polytime implies a polytime solution for Problem (b), we will use the provided deterministic, polytime solution to Problem (a) to find a non-square modulo \(p\). To find a non-square, we will first try to find a square root of \(1 \pmod p\), and if this attempt fails, it means that \(1 \pmod p\) is a non-square modulo \(p\). In case the sqrt of 1 is found the search for a non-square will continue for other numbers (like 2,...). Thus, given a deterministic, polytime solution to one of the problems, we can construct a deterministic, polytime solution to the other one. This proves that Problems (a) and (b) are deterministic, polytime equivalent.

Key Concepts

Deterministic Polynomial Time

Deterministic Polynomial Time is a concept in computational complexity theory. It indicates that an algorithm can consistently solve a problem within a time that is a polynomial function of the size of the input. For instance, if the size of the input to a problem is represented as "n," and the algorithm runs in time proportional to \(n^2, n^3\), etc., it is considered to operate in polynomial time.

A key aspect of deterministic polynomial time is determinism, meaning the algorithm gives the same correct outputs for the same inputs every time. In contrast to randomized algorithms, there is no place for chance or probability in deterministic algorithms.

When problems are solvable in deterministic polynomial time, it implies that they are efficiently solvable in practice. This is crucial in many fields like cryptography, where solutions need to be found quickly to be practical.

Prime Numbers

Prime numbers are integers greater than one that have no divisors other than one and themselves. They form the building blocks of number theory and have vital applications in areas such as cryptography. For example, the RSA encryption algorithm depends on the difficulty of factoring large prime numbers.

Prime numbers are uniquely interesting because each number has a unique prime factorization. This is known as the fundamental theorem of arithmetic.

When working with primes, especially in modular arithmetic, it is essential to consider whether elements are quadratic residues modulo a prime, or not, which often arises in problems like finding square roots modulo a prime number. An odd prime is a prime number greater than two, which is beneficial for ensuring distinct properties in modular arithmetic.

Quadratic Residue

A quadratic residue is an integer that is the square of another integer modulo some number. When dealing with a prime number \(p\), a number \(\alpha\) is a quadratic residue modulo \(p\) if there exists some integer \(\beta\) such that \(\beta^2 \equiv \alpha \pmod{p}\).

Determining whether a number is a quadratic residue is important in number theory and has applications in cryptography. It forms the basis for algorithms that involve finding square roots modulo a prime number.

When dealing with quadratic residues, the concept of non-squares or non-residues also arises. These are numbers that are not quadratic residues. The procedure to determine quadratic residues or non-residues determines whether numbers like \(1, 2,...\) are squares or not modulo a given prime \(p\). Understanding these concepts is essential for solving specific problems in a deterministic polynomial time, as demonstrated in exercises related to polynomial time equivalence.