Problem 36 - An Introduction to Mathematical Cryptography

Question

Compute the value of $$ 2^{(p-1) / 2}(\bmod p) $$ for every prime \(3 \leq p<20\). Make a conjecture as to the possible values of \(2^{(p-1) / 2}(\bmod p)\) when \(p\) is prime and prove that your conjecture is correct.

Step-by-Step Solution

Answer

Possible values are 1 or -1 for each prime 3 ≤ p < 20.

Step 1: Confirm Fermat's Little Theorem

Fermat's Little Theorem states that if \( p \) is a prime number, then for any integer \( a \) not divisible by \( p \), it holds that \( a^{p-1} \equiv 1 \pmod{p} \). Therefore, if \( p \) is prime, \( 2^{p-1} \equiv 1 \pmod{p} \). This will be foundational for our calculations.

Step 2: Simplify the Expression

For each prime \( p \), we need to compute \( 2^{(p-1)/2}\mod p \). This stems from the fact that \( 2^{p-1} = (2^{(p-1)/2})^2 \equiv 1 \pmod{p} \), which implies that \( 2^{(p-1)/2} \equiv \pm 1 \pmod{p} \).

Step 3: Compute for Each Prime

We calculate \( 2^{(p-1)/2}\mod p \) for each prime number between 3 and 19:- When \( p = 3 \), \((3-1)/2 = 1\); thus, \(2^1 \equiv 2 \pmod{3}\).- When \( p = 5 \), \((5-1)/2 = 2\); so \(2^2 \equiv 4 \equiv -1 \pmod{5}\).- When \( p = 7 \), \((7-1)/2 = 3\), \(2^3 \equiv 8 \equiv 1 \pmod{7}\).- When \( p = 11 \), \((11-1)/2 = 5\); \(2^5 \equiv 32 \equiv -1 \pmod{11}\).- When \( p = 13 \), \((13-1)/2 = 6\); \(2^6 \equiv 64 \equiv 1 \pmod{13}\).- When \( p = 17 \), \((17-1)/2 = 8\); \(2^8 \equiv 256 \equiv 1 \pmod{17}\).- When \( p = 19 \), \((19-1)/2 = 9\); \(2^9 \equiv 512 \equiv -1 \pmod{19}\).Through these calculations, the possible values are \( 1 \) or \(-1 \).

Step 4: Conjecture and Proof

The conjecture is that for any odd prime \( p \), \( 2^{(p-1)/2} \equiv 1 \pmod{p} \) if \( 2 \) is a quadratic residue mod \( p \) (implying \( p \equiv \pm 1 \pmod{8} \)), and \( \equiv -1 \pmod{p} \) if \( 2 \) is a non-quadratic residue mod \( p \) (implying \( p \equiv 3 \) or \( 5 \pmod{8} \)). This is based on the law of quadratic reciprocity in number theory.

Key Concepts

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers wrap around after reaching a certain value, known as the modulus. This is akin to the way clock arithmetic works with hours, wrapping around after 12. In modular arithmetic, two numbers are equivalent if they differ by a multiple of the modulus. This idea can be expressed using the notation, for example, \( a \equiv b \pmod{m} \), which states that \( a \) leaves the same remainder as \( b \) when divided by \( m \).

• Key operation: In \( a + b \equiv c \pmod{m} \) and \( a \times b \equiv c \pmod{m} \), operations are performed as usual, followed by taking the remainder when divided by \( m \).
• Fermat's Little Theorem: If \( p \) is a prime number, then for any integer \( a \) not divisible by \( p \), \( a^{p-1} \equiv 1 \pmod{p} \).

Modular arithmetic is a foundational concept used here to calculate terms like \( 2^{(p-1)/2} \mod p \), vital in predicting patterns of quadratic residues.

Quadratic Residues

Quadratic residues relate to the possibility of a number being expressed as a square modulo another number. If there exists some integer \( x \) such that \( x^2 \equiv a \pmod{p} \), then \( a \) is termed a quadratic residue mod \( p \). If no such \( x \) exists, then \( a \) is a non-quadratic residue.

• For any odd prime \( p \), there are exactly \((p-1)/2\) quadratic residues, and the same number of non-quadratic residues.
• Quadratic residues play a crucial role in understanding computations like \( 2^{(p-1)/2} \mod p \), specifically whether results will be \( 1 \) or \(-1\).

This concept is particularly useful in interpreting the results generated from Fermat's Little Theorem and forms the basis for the law of quadratic reciprocity.

Law of Quadratic Reciprocity

The law of quadratic reciprocity is a central theorem in number theory that provides a criterion to decide whether an integer is a quadratic residue modulo a prime number. It can be cumbersome to decide if a number like 2 is a quadratic residue modulo different primes using simple computation.

• The law states conditions under which one prime is a quadratic residue modulo another. For instance, 2 will be a quadratic residue modulo \( p \) if \( p \equiv \pm 1 \pmod{8} \), and a non-residue if \( p \equiv 3 \) or \( 5 \pmod{8} \).
• This law helps make conjectures, such as determining \( 2^{(p-1)/2} \equiv \pm 1 \pmod{p} \).

The law of quadratic reciprocity is integral in proving and predicting which results appear in modular arithmetic problems involving quadratic residues.