Can we avoid repetition in Shor's algorithm by using the quadratic formula?

Question

Shor's algorithm is a quantum algorithm to find a non-trivial factor of a composite integer $N$. It is assumed that $N$ is odd and not a perfect power.

The first step is to find the multiplicative order $r$ of $x$ modulo $N$, where $x$ is randomly chosen in the range 1 to $N-1$. If $r$ is even and $x^{r/2} \ne -1 \pmod{N}$, then either $\gcd(x^{r/2}-1, N)$ or $\gcd(x^{r/2}+1, N)$ is a non-trivial factor of $N$. Otherwise, we must repeat the algorithm with a different choice of $x$.

But is it really necessary to repeat the algorithm? Let's suppose that $N = pq$ where $p$ and $q$ are distinct odd primes. This is the most important case in practice, since arises in the RSA cryptosystem. We know that $x^r = 1 \pmod{N}$, so $r$ divides $\phi(N) = (p-1)(q-1)$. If $r \ge p+q$ then we can recover the sum of the prime factors, since $p + q = (N \mathop{\mathrm{mod}} r) + 1$. Once we know the sum and product, we can find $p$ and $q$ via the quadratic formula. Specifically,

$$\{p, q\} = \left\lbrace\frac12\left(S - \sqrt{S^2 - 4N\,}\right), \frac12\left(S + \sqrt{S^2 - 4N\,}\right)\right\rbrace$$

where $S = p + q$.

Is this argument correct, and has this variation on Shor's algorithm been investigated before? How likely is it to fail? It certainly fails if $p-1$ divides $q-1$ or vice versa. But this seems very unlikely.

Note that we don't need the exact period. It suffices to find any factor of $\phi(N)$ that is greater than or equal to $p+q$.

Answer 1

I think you're right. Your idea is kind of similar to how the factoring in "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" is done, except in that paper the p+q term comes from a different place instead of directly from the period:

If you email Martin Ekerå he will probably know if there's a previous reference for your exact idea instead of a similar idea.

The advantage of getting the sum from this different place is you can use a smaller superposed exponent compared to directly computing the period:

Here's code verifying your idea works:

import math
import random
from typing import Optional, Tuple


def brute_force_period(base: int, modulus: int) -> int:
    t = 1
    k = 0
    while True:
        k += 1
        t *= base
        t %= modulus
        if t == 1:
            return k


def factor_semiprime(
        N: int,
        *,
        g: Optional[int] = None,
        hint_factor_only_for_computing_period: Optional[int] = None,
) -> Tuple[int, int]:
    if g is None:
        g = random.randint(2, N - 2)
    if hint_factor_only_for_computing_period is not None:
        assert N % hint_factor_only_for_computing_period == 0
        known_p = hint_factor_only_for_computing_period
        known_q = N // hint_factor_only_for_computing_period
        period_1 = brute_force_period(g, known_p)
        period_2 = brute_force_period(g, known_q)
        r = math.lcm(period_1, period_2)
    else:
        r = brute_force_period(g, N)

    assert pow(g, r, N) == 1
    s = (N % r) + 1
    b = math.isqrt(s*s - 4*N)
    p = (s - b) // 2
    q = (s + b) // 2
    assert p * q == N
    return p, q


def main():
    p, q = factor_semiprime(599 * 229)
    assert {p, q} == {229, 599}

    p, q = factor_semiprime(39119 * 81517, hint_factor_only_for_computing_period=81517)
    assert {p, q} == {39119, 81517}

    p, q = factor_semiprime(4538923 * 1493339, hint_factor_only_for_computing_period=1493339)
    assert {p, q} == {4538923, 1493339}

    print("passed")


if __name__ == '__main__':
    main()

Answer 2

Since Craig referenced me in his answer, I will chime in and follow up a bit on what Craig wrote. Since there are several sub-questions to your question, I will answer in parts:

1. First, to answer your overarching question, note that we can avoid re-runs in Shor's factoring algorithm with very high probability not only when factoring random RSA integers $N = pq$, but when completely factoring any integer $N$. This by using the efficient classical reduction in [E21b] coupled with [E22p]. An implementation of [E21b] is available in this repository on GitHub.

2. Second, to answer your specific questions regarding factoring RSA integers via the quadratic formula, I see no reason for why your proposed reduction would not work. Did you have a specific concern in mind? The probability that $r \ge p + q$ for $N = pq$ a large random RSA integer is overwhelming.

   (You can use the simulator in this repository to exactly simulate you proposed reduction for large cryptographically relevant $N = pq$, provided that you select $N$ so that you know $p$ and $q$. This works because you need not explicitly know $x$. If you are interested in bounding the probability that $r \ge p + q$, see e.g. Lemma 4 in App. A.2.2 of [E20].)

   I do not know if exactly this reduction has been proposed earlier in the literature — but very close ones have, so I presume I would say that this has been investigated, at least to some extent:

   • For instance, take [EH17] as an example, where the idea is essentially as follows:

     For $N = pq$ a large random RSA integer, select an element $g$ uniformly at random from $\mathbb Z_N^*$ and compute $x = g^{N+1} = g^{p+q}$ classically. With overwhelming probability, it holds that $r > p + q$ for $r$ the order of $g$, in which case $d = \log_g x = p + q$.

     The idea in [EH17] is now to use a quantum algorithm that is more efficient than Shor's order-finding algorithm — and that critically does not depend on $r$ being known — to compute the short discrete logarithm $d$.

     Given $d = p + q$ and $N = pq$, the integer $N$ is finally split into $p$ and $q$ in [EH17] by using the quadratic formula, exactly as you describe in your question.

     The advantage of the approach in [EH17] compared to Shor's original approach is not only that a single run of the quantum part of the algorithm suffices to compute $d$ with very high probability, but also that the quantum part that computes $d$ is less costly compared to the quantum part that computes $r$ in Shor's order-finding algorithm. The drawback is that the approach only works for RSA integers (and some other integers on special form, but RSA integers are of key interest).

     As Craig pointed out earlier in his answer, this is why [EH17] is used in [GE21] to break RSA. Factoring via order finding would be less efficient — even if one were to use the reduction in [E21b] that only requires a single successful run of Shor's order-finding algorithm.

   • Another example is [HSS93] — that predates [Shor94] — but that uses more or less exactly the reduction you are describing to factor (inspiring [EH17]).

   • Yet another example is [GLMS15], where a similar reduction to the one you propose is used to factor safe semi-primes in a single run of Shor's order-finding algorithm.

   There may be other related works in the literature — i.e. both in the literature on Shor's algorithm specifically, and on number theory and mathematics, and cryptography and computer science, more broadly. See the "Earlier works" section of [E21b] for one literature survey as a starting point.

3. Third, on a side note, to give a somewhat related proposal: For $N$ an integer with at least two distinct prime factors and no small prime factors (these are trivial to factor out classically), pick $g$ uniformly at random from $\mathbb Z_N^*$ and compute the order $r$ of $g$.

   Then with fairly high probability $r > N - \phi(N)$ and $\phi(N) = N - (N \text{ mod } r)$, in which case we can use $\phi(N)$ to completely factor $N$ efficiently classically by randomizing [Miller76] as described in [E21b]. (This may be slightly improved in various ways, e.g. by considering multiples of $r$ in the event that the procedure fails.)

   (In [E21b], the idea is to construct a positive multiple of a sufficiently large divisor of $\lambda'(N)$ by multiplying on powers of small prime factors to $r$, and to then use this multiple to completely factor $N$ by randomizing [Miller76]. The probability of this approach being successful is lower bounded in [E21b] and shown to be very high in the worst case. Constructing $\phi(N)$ (which is a multiple of a sufficiently large divisor of $\lambda'(N)$) in the above manner may potentially yield a slight improvement for some $N$.)