Question

Let \(n\) be a large, positive integer. We can factor \(n\) using trial division in time \(n^{1 / 2+o(1)} ;\) however, using fast polynomial arithmetic in \(\mathbb{Z}_{n}[X],\) one can get a simple, deterministic, and rigorous algorithm that factors \(n\) in time \(n^{1 / 4+o(1)} .\) Note that all of the factoring algorithms discussed in Chapter \(15,\) while faster, are either probabilistic, or deterministic but heuristic. Assume that we can multiply polynomials in \(\mathbb{Z}_{n}[X]\) of length at most \(\ell\) using \(M(\ell)\) operations in \(\mathbb{Z}_{n},\) where \(M\) is a well-behaved complexity function, and \(M(\ell)=\ell^{1+o(1)}\) (the algorithm from Exercise 17.24 would suffice). (a) Let \(\ell\) be a positive integer, and for \(i=1, \ldots, \ell,\) let $$ a_{i}:=\prod_{j=0}^{\ell-1}(i \ell-j) \bmod n $$ Using fast polynomial arithmetic, show how to compute \(\left(a_{1}, \ldots, a_{\ell}\right)\) in time \(\ell^{1+o(1)} \operatorname{len}(n)^{O(1)}\) (b) Using the result of part (a), show how to factor \(n\) in time \(n^{1 / 4+o(1)}\) using a deterministic algorithm.

Short answer

Answer: 1. Set \(\ell = \left \lceil n^{1 / 4} \right \rceil\). 2. Compute the sequence \((a_1,\dots,a_\ell)\) using fast polynomial arithmetic as described in part (a) of the solution. 3. For each \(a_i\), calculate the greatest common divisor (GCD) of \(n\) and \(a_i\): $$\operatorname{GCD}(n, a_i)$$ 4. If a nontrivial factor is found (neither 1 nor n), we can stop and factor n as product of that factor and its complement. The time complexity of these steps is \(O(n^{1/4 + o(1)})\).

Step-by-step solution

Part (a)

To calculate the sequence \(a_i\), we have the following product: $$ a_i = \prod_{j=0}^{\ell-1}(i \ell-j) \pmod{n} \quad \forall i=1,\dots,\ell. $$ Now, use polynomial representation for each term in the product as: $$ P_i(X) = i\ell - X \quad \forall i=1,\dots,\ell. $$ Then, we can rewrite the expression for \(a_i\) as: $$ a_i = P_i(\ell) \pmod{n} \quad \forall i=1,\dots,\ell. $$ Now, compute the product of these polynomials: $$ P(X) = \prod_{i=1}^{\ell} P_i(X) \pmod{n}. $$ We can compute this product using the divide and conquer technique as in fast polynomial multiplication in \(O(\ell^{1+\epsilon} (\log \ell)^{O(1)})\) time using exercise 17.24 (sufficient for our purpose), and then, calculate the sequence \((a_1, \dots, a_\ell)\) by evaluating this polynomial at \(\ell\), modulo n. In summary, 1. Compute \(P(X) = \prod_{i=1}^{\ell} P_i(X) \pmod{n}\) in \(O(\ell^{1+\epsilon} (\log \ell)^{O(1)})\) time using fast polynomial multiplication. 2. Calculate the values of \(a_i = P_i(\ell) \pmod{n}\) for \(i = 1,\dots,\ell\) as our desired sequence.

Part (b)

In this part, we will use the result of part (a) to factorize n efficiently. Follow these steps: 1. Set \(\ell = \left \lceil n^{1 / 4} \right \rceil\). 2. Compute the sequence \((a_1,\dots,a_\ell)\) as described in part (a). 3. For each \(a_i\), calculate the greatest common divisor (GCD) of \(n\) and \(a_i\) as follows: $$\operatorname{GCD}(n, a_i)$$ If we find a nontrivial factor (which is neither 1 nor n), we can stop and factor n as product of that factor and its complement. The algorithm's complexity is determined by the polynomial multiplication and GCD calculations: 1. Polynomial multiplication has complexity \(O(\ell^{1+\epsilon} (\log \ell)^{O(1)})\). 2. GCD calculations for each \(a_i\) takes \(O(\ell \operatorname{len}(n)^{O(1)})\). The total complexity will be \(O(\ell^{1+\epsilon} (\log \ell)^{O(1)}+\ell \operatorname{len}(n)^{O(1)})\), which is within the required time complexity of \(O(n^{1/4 + o(1)})\) since \(\ell = n^{1/4}\) and \(\operatorname{len}(n) = O(\log n)\).

Key concepts

Fast Polynomial Arithmetic

Fast polynomial arithmetic refers to methods that allow computation with polynomials to be more efficient. Instead of performing operations term by term, algorithms are used to handle polynomials as a whole. This is crucial when dealing with large polynomials, especially over rings like \( \mathbb{Z}_n[X] \), where direct computation can be very slow.

The divide and conquer technique is one common approach used in fast polynomial arithmetic. By breaking down a problem into smaller subproblems and solving each independently, the overall process becomes more manageable and less time-consuming. Fast polynomial multiplication is a key component, utilizing methods such as the Karatsuba algorithm or FFT-based techniques, which reduces the time complexity significantly compared to classical methods.

• Efficiency gains: From exponential to polynomial time improvements.
• Applications: Key in modern algorithms for computer algebra systems.
• Useful for: Problems involving polynomial evaluation, multiplication, and factorization.

Deterministic Algorithm

A deterministic algorithm is one that will always produce the same output given the same initial input. This type of algorithm doesn't rely on random numbers or probabilities, ensuring reliability and predictability in results.

In the context of factoring a polynomial over \( \mathbb{Z}_n[X] \), a deterministic algorithm is preferred over probabilistic ones when guaranteed results are required. Probabilistic algorithms might perform faster on average but lack the assurance of correctness for every instance.

• Predictable: Same inputs lead to the same outputs every time.
• Utility: Ideal for problems requiring guaranteed correctness.
• Trade-offs: Might be slower in some instances, but provides certainty.

Deterministic algorithms are often paired with fast polynomial arithmetic to achieve more efficient solutions without sacrificing accuracy or reliability.

Polynomial Multiplication

Polynomial multiplication is the process of multiplying two polynomials to get a resultant polynomial. For polynomials over a ring like \( \mathbb{Z}_n \), direct term-by-term multiplication can be inefficient. Sophisticated techniques like those used in fast polynomial arithmetic are employed instead.

The complexity of polynomial multiplication can be significantly reduced from the naive \( O(n^2) \) to about \( O(n \log n) \) using more advanced algorithms:

• Karatsuba Algorithm: Breaks down the polynomials into smaller parts, improving the complexity to \( O(n^{\log_2 3}) \).
• FFT-Based Multiplication (Fast Fourier Transform): Converts polynomials into point-value form to allow multiplication to occur more quickly.

Each of these methods capitalizes on manipulating polynomials as structured data rather than as a collection of separate terms, making polynomial computations feasible for large datasets.

Trial Division

Trial division is a straightforward method for finding factors of a number. It involves testing potential divisors sequentially to check if they divide the number without leaving a remainder. For large numbers, this can be incredibly time-consuming, as it might require testing many potential factors.

However, the efficiency of trial division can be expressed as \( n^{1/2+o(1)} \), which isn't practical for very large numbers. Despite its simplicity, trial division is not usually employed alone for large number factorization due to its inefficiency.

• Simple: Easy to understand and implement.
• Drawbacks: Slow for large integers, as it tests many potential factors.
• Modern Use: Often used in combination with more sophisticated methods for smaller factor checks.

For large factorization tasks, combining trial division with methods like fast polynomial arithmetic can reduce computation time, offering a more balanced approach to problem-solving.