On completely factoring any integer efficiently in a single run of an order-finding algorithm

From the abstract of [E21b]: "We show that given the order of a single element selected uniformly at random from $\mathbb Z_N^*$, we can with very high probability, and for any integer $N$, efficiently find the complete factorization of $N$ in polynomial time. This implies that a single run of the quantum part of Shor's factoring algorithm is usually sufficient. All prime factors of $N$ can then be recovered with negligible computational cost in a classical post-processing step. The classical algorithm required for this step is essentially due to Miller [Miller76]."

This repository contains a Sage script factor.sage that implements the factoring algorithm in [E21b].

For test purposes, it furthermore contains a script factor-test.sage that simulates order finding.

Note that the aforementioned scripts were developed for academic research purposes. They grew out of our research project in an organic manner as research questions were posed and answered. They are distributed "as is" without warranty of any kind, either expressed or implied. For further details, see the license.

It is possible to further optimize portions of the scripts and the procedures therein. However, the current scripts perform sufficiently well for our purposes, in that they clearly show that it is virtually always possible to completely factor any integer $N$ efficiently after a single run of an order-finding algorithm.

Prerequisites

To install Sage under Ubuntu 20.04 LTS, simply execute:

$ sudo apt install sagemath

For other Linux and Unix distributions, or operating systems, you may need to download Sage and install it manually. These scripts were developed for Sage 9.3.

Attaching the scripts

Launch Sage and attach the scripts factor.sage and factor-test.sage, by executing:

$ sage
(..)
sage: %attach factor.sage
sage: %attach factor-test.sage

Factoring

To completely factor $N$, execute:

sage: factor_completely(r, N, c = 1)

Above $r$ is the order of an element $g$ selected uniformly at random from $\mathbb Z_N^*$, $N$ is the integer to be factored, and $c \ge 1$ is a constant that may be freely selected.

As is explained in [E21b], by increasing $c$ the success probability of the algorithm can be increased at the expense of also increasing the runtime. In virtually all cases, it is however more than sufficient to let $c = 1$.

To better understand why, recall from [E21b] that if some moderate product of small prime factors is missing from the order $r$ input compared to $\lambda'(N)$, the complete factorization will be recovered anyhow by iterating. If a single large prime factor is missing, it still does not matter, for the complete factorization will be found anyhow via $N$. It is only if two large prime factors are missing simultaneously, and if these two factors are associated with different prime factors $p_i$ of $N = {\prod}_{i = 1}^n p_i^{e_i}$, that the complete factorization of $N$ will not be recovered. This is very unlikely to occur in practice, even if some $p_i - 1$ are smooth.

Note furthermore that by default the function will continue to iterate until the complete factorization is found, or until Ctrl-C is pressed. The constant $k$ in [E21b], that controls the number of iterations, need therefore not be specified. If you wish, you may explicitly set $k$, or a timeout in seconds, or both, in which case an exception will be raised if either limit specified is exceeded.

Simulating order finding

The factor-test.sage script implements two types of order-finding simulators:

• Given the factorization of $N$, and an element $g \in \mathbb Z_N^*$, the first type of order-finding simulator yields either the order $r$ of $g$, or a heuristic approximation of $r$ that is correct with very high probability.

  To be more specific: If the factorization of $p_i - 1$ is known for all $i \in [1, n]$, where $N = {\prod}_{i = 1}^n p_i^{e_i}$, order finding can be performed exactly. Otherwise, a heuristic approximation can be computed by performing trial division to identify all small factors of $p_i - 1$ for $i \in [1, n]$. For further details, see Appendix A of [E21b].

• Given the factorization of $N$, the second type of order-finding simulator yields the order $r$ of an element $g$ selected uniformly at random from $\mathbb Z_N^*$. This without explicitly computing $g$.

  This approach to simulating order finding is not described in [E21b]. For further details, see instead the documentation of the test_of_random_pi_ei() function in the factor-test.sage script.

Exact order finding by factoring

To test the factoring algorithm by performing exact order finding for a random integer $N$, execute:

sage: test_of_random_N(m = 192, c = 1)

This function will first select $N$ uniformly at random from the set of all $m$ bit composites, where it is required that $m \in [8, 224]$. It will then select $g$ uniformly at random from $\mathbb Z_N^*$, and compute the order $r$ of $g$ exactly classically by factoring $N = p_1^{e_1} \cdot \ldots \cdot p_n^{e_n}$ and then $p_i - 1$ for $i \in [1, n]$ using functions native to Sage.

Finally, it will call factor_completely() with $r$ and $N$ passing along the constant $c$.

Exact or heuristic order finding for a given factorization

To test the factoring algorithm by performing order finding given the factorization of $N$, execute:

sage: test_of_random_pi_ei(l = 1024, n = 2, e_max = 1, c = 1, exact = True)

This function will first select $n \ge 2$ distinct primes $p_i$ uniformly at random from the set of all odd $\ell$ bit primes, and $n$ exponents $e_i$ uniformly at random from $[1, e_{\max}]$. It will then compute $N = {\prod}_{i=1}^n p_i^{e_i}$.

• If exact is set to False, this function will first select $g$ uniformly at random from $\mathbb Z_N^*$. It will then heuristically determine the order $r$ of $g$ using the first type of simulator described above.

• If exact is set to True, as is the default, this function will exactly compute the order $r$ of an element $g$ selected uniformly at random from $\mathbb Z_N^*$, using the second type of simulator described above.

  This without explicitly computing $g$. (Note that $g$ is not used by the factoring algorithm in [E21b].)

Finally, this function will call factor_completely() with $r$ and $N$ passing along the constant $c$.

Test suites

To run the test suite described in Appendix A.3 of [E21b], execute:

sage: test_all_appendix_A(exact = True)

This function in turn calls the test_of_random_pi_ei() function documented above.

• Set the exact flag to False to perform heuristic order finding as described in Appendix A of [E21b].

• Set the exact flag to True, as is the default, to instead perform exact order finding at the expense of foregoing the computation of $g$. This is an improvement of the procedure in Appendix A of [E21b].

For further details on the exact flag, see the documentation for the test_of_random_pi_ei() function.

Notes on optimizations

This implementation supports several optimizations that may be enabled or disabled by passing along flags to the functions described in the above sections. For more information, see the notes on optimizations.

About and acknowledgments

These scripts were developed by Martin Ekerå, in part at KTH, the Royal Institute of Technology, in Stockholm, Sweden. Valuable comments and advice were provided by Johan Håstad throughout the development process.

Funding and support was provided by the Swedish NCSA that is a part of the Swedish Armed Forces.