Question

\(^*\) In this exercise, you are to prove Theorem 20.1. So let \(N=p q\) for two distinct primes \(p, q \in \mathbb{N}\). (i) Show how to compute \(p, q\) from the knowledge of \(N\) and \(\varphi(N)\). Hint: Consider the quadratic polynomial \((x-p)(x-q) \in \mathbb{Z}[x]\). (ii) Suppose that you are given a black box which on input \(e \in \mathbb{N}\) decides whether it is coprime to \(\varphi(N)\), and if so, returns \(d \in\\{1, \ldots, \varphi(N)-1\\}\) such that de \(\equiv 1 \bmod \varphi(N)\). Give an algorithm using this black box which computes \(\varphi(N)\) in time \((\log N)^{O(1)}\). Hint: Find a "small" \(e\) coprime to \(\varphi(N)\)

Short answer

Compute \(p+q\) as \(N - \varphi(N) + 1\), solve the quadratic \(x^2 - (p+q)x + N = 0\) to find \(p\) and \(q\).

Step-by-step solution

Understanding \\( ext{\(\varphi(N)\)}\)

Since \( ext{\(N\)}\) is the product of two distinct primes \( ext{\(p\)}\) and \( ext{\(q\)}\), the Euler's totient function \( ext{\(\varphi(N)\)}\) is given by \( ext{\((p-1)(q-1)\)}\). Thus, knowing \( ext{\(N\)}\) and \( ext{\(\varphi(N)\)}\), we can work towards finding \( ext{\(p\)}\) and \( ext{\(q\)}\).

Formulating the Quadratic Polynomial

Given the expression \((p-1)(q-1) = \varphi(N)\), we know that \((x-p)(x-q) = x^2 - (p+q)x + pq\). Hence, the polynomial becomes \(x^2 - (p+q)x + N\). Here, we need to solve for \(p\) and \(q\).

Solving the Quadratic Equation

The sum of \(p\) and \(q\) can be found as \((p+q) = N - \varphi(N) + 1\). To find \(p\) and \(q\), solve the quadratic equation: \((x^2 - (p+q)x + N = 0)\), using \(\Delta = (p+q)^2 - 4N\) to find the roots.

Using the Black Box for \\( ext{\(\varphi(N)\)}\)

The black box can decide if \(e\) is coprime to \(\varphi(N)\) and return \(d\) such that \(de \equiv 1 \bmod \varphi(N)\). Use small \(e\), such as \(e = 2\), which has a high chance of being coprime to \(\varphi(N)\). Repeat with different small values until the black box returns a valid \(d\).

Computational Procedure

To find \(\varphi(N)\), start with an \(e\) and use the black box until it is coprime with \(\varphi(N)\). Use algorithms like Extended Euclidean Algorithm to check coprimality quickly, ensuring runtime of \(\log(N)^{O(1)}\).

Final Calculation of Primes

Once \(\varphi(N)\) is known, and \((p+q) = N - \varphi(N) + 1\) is computed, solve the quadratic \(x^2 - (p+q)x + N = 0\) with the derived roots equating to the sought primes \(p\) and \(q\).

Key concepts

Euler's Totient Function

Euler's Totient Function, denoted as \( \varphi(n) \), is a fundamental concept in Number Theory. It counts the number of positive integers up to a given integer \( n \) that are coprime to \( n \). Two numbers are said to be coprime if their greatest common divisor (GCD) is 1.
For instance, \( \varphi(9) = 6 \) because among the numbers 1 to 9, the numbers 1, 2, 4, 5, 7, and 8 do not share any prime factors with 9.
When it comes to a product of two distinct primes, such as \( N = p \times q \), the Euler's Totient Function simplifies to \( \varphi(N) = (p-1)(q-1) \). This is crucial because if we know \( N \) and \( \varphi(N) \), we can potentially solve quadratic equations to find \( p \) and \( q \). This concept is prominently used in cryptographic algorithms, like RSA, where security relies on the difficulty of factoring such numbers.

Quadratic Equations

Quadratic equations are equations of the form \( ax^2 + bx + c = 0 \). They are solved to find the values of \( x \) that make the equation true, known as the roots.
In our exercise, these equations represent the expression \((x-p)(x-q)\) derived from knowing \( \varphi(N) \) and \( N \). This forms the polynomial \( x^2 - (p+q)x + pq = 0 \).
Here, the coefficients and their relationships allow us to deduce \( (p+q) = N - \varphi(N) + 1 \) and \( pq = N \).

• Use the quadratic formula, \( x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \), to solve for \( x \), which in this context are the primes \( p \) and \( q \).
• Calculate the discriminant \( \Delta = b^2 - 4ac \) to ensure it yields real roots, confirming the primality of \( p \) and \( q \).

Understanding these relationships is vital for solving problems involving Euler’s Totient Function and factorization in cryptography.

Coprime

Two numbers are coprime, or relatively prime, if their greatest common divisor (GCD) is 1. This concept is significant in Number Theory and many algorithms.
In the problem at hand, we aim to identify numbers \( e \) that are coprime to \( \varphi(N) \).

• An efficient way to ensure a number is coprime is to check that it does not share any factors with the number in question, other than 1.
• Algorithms like the Euclidean Algorithm aid in swiftly determining the GCD, thus checking coprimality.

Finding such numbers is crucial in cryptographic operations, especially when determining keys in encryption schemes like RSA.
Once you find a number that is coprime to \( \varphi(N) \), you can proceed with modular arithmetic operations essential for encryption and decryption processes.

Algorithms

Algorithms are step-by-step procedures for solving computational problems. In Number Theory, they play a pivotal role in tasks such as prime factorization, cryptographic key generation, and more.
The problem involves using a conceptual 'black box' algorithm to decide if a number \( e \) is coprime with \( \varphi(N) \), and to compute a multiplicative inverse \( d \) such that \( de \equiv 1 \pmod{\varphi(N)} \).

• The Extended Euclidean Algorithm is typically used here to find the inverse efficiently. It's an extension of the Euclidean Algorithm, which finds the GCD.
• By selecting small values for \( e \), like \( e = 2 \), you increase the chances of \( e \) being coprime with \( \varphi(N) \), simplifying computations.

These algorithmic strategies are essential for ensuring that cryptographic systems can be implemented in a feasible time span, maintaining security and efficiency.