Problem 6 - A Computational Introduction to Number Theory and Algebra

Question

This exercise develops a probabilistic primality test based on the Jacobi symbol. For odd integer \(n>1,\) define $$ G_{n}:=\left\\{\alpha \in \mathbb{Z}_{n}^{*}: \alpha^{(n-1) / 2}=J_{n}(\alpha)\right\\} $$ where \(J_{n}: \mathbb{Z}_{n}^{*} \rightarrow\\{\pm 1\\}\) is the Jacobi map. (a) Show that \(G_{n}\) is a subgroup of \(\mathbb{Z}_{n}^{*}\). (b) Show that if \(n\) is prime, then \(G_{n}=\mathbb{Z}_{n}^{*}\). (c) Show that if \(n\) is composite, then \(G_{n} \subseteq \mathbb{Z}_{n}^{*}\). (d) Based on parts (a)-(c), design and analyze an efficient probabilistic primality test that works by choosing a random, non-zero element \(\alpha \in \mathbb{Z}_{n},\) and testing if \(\alpha \in G_{n}\)

Step-by-Step Solution

Answer

#tag_title# Short Answer For a given odd integer \(n > 1\), we can create a probabilistic primality test by: 1. Choosing a random, non-zero element \(\alpha \in \mathbb{Z}_n\). 2. Calculating the Jacobi symbol \(J_n(\alpha)\). 3. Calculating \(\alpha^{(n-1)/2} \pmod{n}\). 4. Comparing \(\alpha^{(n-1)/2}\) and \(J_n(\alpha)\); if they are congruent modulo \(n\), then \(n\) has a higher probability of being prime; otherwise, \(n\) is composite. 5. Repeating steps 1-4 for multiple random choices of \(\alpha\) to improve the accuracy of the test. This test is efficient, as it relies on calculating the Jacobi symbol and exponentiation in modular arithmetic. By increasing the number of random \(\alpha\)s tested, we improve the overall accuracy of the test.

Step 1: Part (a): Proving \(G_n\) is a subgroup of \(\mathbb{Z}_{n}^{*}\)

To prove that \(G_n\) is a subgroup of \(\mathbb{Z}_{n}^{*}\), we need to show that it satisfies the three group conditions (closure, identity, and inverses). 1. Closure: If \(\alpha, \beta \in G_n\), then \(\alpha \beta \in G_n\). Let \(\alpha, \beta \in G_n\). Then, $$ \alpha^{(n-1) / 2}=J_{n}(\alpha) $$ and $$ \beta^{(n-1) / 2}=J_{n}(\beta). $$ Multiply these two equations: $$ (\alpha^{(n-1) / 2})(\beta^{(n-1) / 2})=J_{n}(\alpha)J_{n}(\beta) $$ Since exponent multiplication is commutative, we get: $$ (\alpha \beta)^{(n-1) / 2}=J_{n}(\alpha)J_{n}(\beta) $$ By properties of the Jacobi symbol, \(J_{n}(\alpha\beta)=J_{n}(\alpha)J_{n}(\beta),\) so we have: $$ (\alpha \beta)^{(n-1) / 2}=J_{n}(\alpha\beta) $$ Thus, \(\alpha\beta \in G_n\), and closure is satisfied. 2. Identity: The identity element (1) is in \(G_n\). The Jacobi symbol of 1 is 1, and \(1^{(n-1)/2} = 1\). Thus, $$ 1^{(n-1) / 2}=J_{n}(1) $$ It follows that the identity element 1 is in \(G_n\). 3. Inverses: If \(\alpha \in G_n\), then its inverse \(\alpha^{-1} \in G_n\). Let \(\alpha \in G_n\). Then, $$ \alpha^{(n-1) / 2}=J_{n}(\alpha). $$ Now, \((\alpha^{-1})^{(n-1)/2}\cdot\alpha^{(n-1)/2}=((\alpha\alpha^{-1}))^{(n-1)/2}=1^{(n-1)/2}=1.\) Hence, $$ (\alpha^{-1})^{(n-1)/2}=J_{n}(\alpha)^{-1}. $$ Furthermore, \(J_{n}(\alpha\alpha^{-1})=J_{n}(1)=1.\) Since \(J_{n}(\alpha\alpha^{-1})=J_{n}(\alpha)J_{n}(\alpha^{-1}),\) we have \(1=J_{n}(\alpha)J_{n}(\alpha^{-1})\), or \(J_{n}(\alpha^{-1})=J_{n}(\alpha)^{-1}.\) Thus, $$ (\alpha^{-1})^{(n-1) / 2}=J_{n}(\alpha^{-1}), $$ which means \(\alpha^{-1} \in G_n\), and inverses are satisfied. Since all three group conditions are satisfied, \(G_n\) is a subgroup of \(\mathbb{Z}_{n}^{*}\).

Step 2: Part (b): Proving \(G_n = \mathbb{Z}_{n}^{*}\) when \(n\) is prime

Assume \(n\) is prime. We want to show that \(G_n=\mathbb{Z}_{n}^*\). By Euler's Criterion, for any \(\alpha \in \mathbb{Z}_{n}^*\) with a prime \(n\), $$ \alpha^{(n-1)/2} \equiv J_n(\alpha) \pmod{n}. $$ Thus, for any \(\alpha \in \mathbb{Z}_{n}^*\), we have \(\alpha^{(n-1) / 2}=J_{n}(\alpha)\). So, \(\alpha \in G_n\). Since this holds for all \(\alpha \in \mathbb{Z}_{n}^*\), we conclude that \(G_n = \mathbb{Z}_{n}^{*}\) when \(n\) is prime.

Step 3: Part (c): Proving \(G_n \subseteq \mathbb{Z}_{n}^{*}\) when \(n\) is composite

Assume \(n\) is composite. Then, \(G_n\) is a subgroup of \(\mathbb{Z}_{n}^*\), as shown in part (a). Thus, \(G_n\) is a subset of \(\mathbb{Z}_{n}^*\) when \(n\) is composite.

Step 4: Part (d): Designing a probabilistic primality test

From parts (b) and (c), we have shown that for an odd integer \(n > 1\), if \(n\) is prime, then \(G_n = \mathbb{Z}_{n}^*\). If \(n\) is composite, then \(G_n \subseteq \mathbb{Z}_{n}^*\). We can use this fact to design a probabilistic primality test as follows: 1. Choose a random, non-zero element \(\alpha \in \mathbb{Z}_n\). 2. Calculate the Jacobi symbol \(J_n(\alpha)\). 3. Calculate \(\alpha^{(n-1)/2} \pmod{n}\). 4. If \(\alpha^{(n-1)/2} \equiv J_n(\alpha) \pmod{n}\), then \(n\) has a higher probability of being prime. If not, then \(n\) is composite. 5. Repeat steps 1-4 for multiple random choices of \(\alpha\) to improve the accuracy of the test. Since the probabilistic primality test relies on calculating the Jacobi symbol and exponentiation in modular arithmetic, it is considered efficient. Moreover, by repeating the test for multiple random \(\alpha\)s, we increase the overall probability of determining whether \(n\) is prime or composite correctly.

Key Concepts

Jacobi Symbol

The Jacobi symbol, represented as \(J_n(\alpha)\), is a number-theoretic function of great importance in primality testing. It is an extension of the Legendre symbol and is defined for all integers \(n\) and \(\alpha\), where \(n\) is an odd positive integer. The symbol outputs either \(1\), \(-1\), or \(0\). The value calculated by the Jacobi symbol can be thought of as a generalization of quadratic residues.

• When \(\alpha\) is a quadratic residue modulo \(n\), the Jacobi symbol \(J_n(\alpha)\) equals 1.
• If \(\alpha\) is not a quadratic residue, the Jacobi symbol returns \(-1\).
• For \(\alpha\) divisible by \(n\), the Jacobi symbol is \(0\).

Understanding the Jacobi symbol is essential for calculating whether elements belong to a specific subgroup within number theory, as it relates to the primality test discussed in our exercise. While it resembles the Legendre symbol, which is limited to prime moduli, the Jacobi symbol works for any positive odd number \(n\), thus serving complex applications such as probabilistic algorithms. This feature makes it highly beneficial in assessing potential primes.

Subgroup in Number Theory

In our exercise, we explore a particular subgroup \(G_n\) within the group \(\mathbb{Z}_n^*\), the multiplicative group of integers modulo \(n\). A subgroup in number theory is defined as a smaller group contained within a larger one, where the subgroup's operations align with those of the larger group.
There are three crucial conditions that define a subgroup:

• Closure: If two elements are in the subgroup, their product must also be in the subgroup.
• Identity: The subgroup must include the identity element of the larger group.
• Inverses: Every element of the subgroup must have an inverse within the subgroup that, when multiplied, returns the identity.

For \(G_n\), the exercise has proven that it satisfies these conditions. The focus is on how elements \(\alpha\) of \(\mathbb{Z}_n^*\) are included in \(G_n\) based on the condition \(\alpha^{(n-1)/2} = J_n(\alpha)\). This subgroup plays a pivotal role in understanding how elements relate to primality: when \(n\) is prime, the entire group equals the subgroup (\(G_n = \mathbb{Z}_n^*\)), while for composite \(n\), \(G_n\) is merely a subset.

Probabilistic Algorithms

Probabilistic algorithms are methods that make decisions based on randomization and have a probability of producing the correct solution. In the context of primality testing, these algorithms leverage randomness to assess whether a number is prime. The exercise under consideration uses such a probabilistic test based on the Jacobi symbol and properties of group subgroup membership.
Here's how the algorithm works:

• A random, non-zero element \(\alpha\) is chosen from \(\mathbb{Z}_n\).
• Calculate the Jacobi symbol \(J_n(\alpha)\).
• Compute \(\alpha^{(n-1)/2} \pmod{n}\).
• If these values are congruent, \(n\) is likely prime. If not, \(n\) is composite.
• Repeat the process several times to improve accuracy.

Probabilistic primality tests like these are efficient because they provide a high level of certainty about a number's primality in fewer steps than deterministic methods. Each repetition of choosing a random \(\alpha\) enhances the test's reliability, allowing it to effectively indicate whether a number is prime with elevated confidence, becoming an invaluable tool for quick preliminary checks.