Lately, a Chinese research team write an article about quantum factoring algorithm [https://arxiv.org/abs/2212.12372] . They showed quite a amazing results about factorization and claimed that RSA-2048 could be broke if we have a quantum computer with 500-numbers of qubits.
Previously, Peter Shor theoretically showed that the quantum computer can solve the factorization problem exponentially faster than classical computer. And this is one of the most important events in quantum history. However, even in this amazing result, it needs more than 10000+ numbers of qubits.
Therefore, the result of the Chinese research team is amazing one because it shrinks the neccesarry numbers of qubits into 500. Because IBMQ have alreadly launched 432-qubits quantum device (even though it have a lot of error), it litterally showed that the RSA-cryptosystem is about to broken down.
However, a lot of professionals have doubts about the results. They say that the result is exaggerated.
Therefore, in this post, we’re going to understant the exact algorithms and procedure used at the results. Because it use a lot of mathematical fields, we have to know a lot of contents. So, let see it one by one.
Schnorr’s Sieve Method
The most fundamental algorithms used by them is Schnorr’s algorithm.
Schnorr’s Sieve Method is a method converting factorting problem into problem finding gcd of numbers corresponding sr-pairs.
Assume there is an integer \(N\) which is target of factoring problem.
An integer is called $p_n$- smooth if its largest prime factor is not bigger than n th largest prime number \(p_n\) (c.f. \(p_0 = -1, p_1 = 2, p_2=3,p_3=5,p_4=7,p_5=11,p_6=13,p_7=17 ....\) \(p_0=-1\) is defined for technical problems.)
If elements of an integer pair \((u,v)\) are both \(p_n\)-smooth, then the pair is called as \(p_n\)-smooth pair.
Moreover, if $p_n$ -smooth pair \((u,v)\) satisfies \((u-vN)/u \equiv 1 \mod N\), the pair is called as \(p_n\) - smooth relation pair aka sr-pair. (Remark that \(a\equiv b \mod N\) means that $a-b = Nk$ for some \(k \in \mathbb{Z}\))
Now, let assume we have \(n+1\) numbers of sr-pair \((u_j,v_j)\) as follow. \(u_j = \prod_{i=1}^n p_i^{e_{i,j}},u_j-v_jN = \prod_{i=0}^n p_i^{e_{i,j}'}\) If we define \(X = \prod_{i=0}^n p_i^{\frac{1}{2} \sum_{j=1}^{n+1} t_j (e_{i,j}' - e_{i,j})}\) for any \(t_j\), then \(X^2 \equiv 1 \mod N\).
Let’s see them.
First of all, notive that \((u_i-v_iN)/u_i = \prod_{i=0}^{n} p_i^{e_{i,j}'-e_{i,j}}=: \alpha_j \equiv 1 \mod N\).
Then we can use modulo computation formula that for \(a_1 \equiv b_1 \mod N\) and \(a_2 \equiv b_2 \mod N\), the equation 1. \(a^k\equiv b^k \mod N\) and 2. \(a_1a_2 \equiv b_1b_2 \mod N\).
We could know that \(\alpha_j^{t_j} \equiv 1^{t_j} = 1 \mod N\) using the equation 1 and \(\prod_{j=1}^{n+1}\alpha_j^{t_j} \equiv 1 \mod N\).
Then we can expand the term as follow.
\[\prod_{j=1}^{n+1} \alpha_j ^{t_j} = \prod_{j=1}^{n+1} \prod_{i=0}^n p_i^{t_j(e_{i,j}'-e_{i,j})} = \prod_{i=0}^n p_i ^{\sum_{j=1}^{n+1} t_j(e_{i,j}'-e_{i,j})} = X^{2}\]Therefore, \(X^2 \equiv 1 \mod N\)
If $X^2 \equiv 1 \mod N$, then $X^2-1 \equiv 0 \mod N$.
And therefore, \(X^2-1 =(X+1)(X-1) \equiv 0 \mod N\)
If \(X \not \equiv \pm 1 \mod N\), then \(gcd(X\pm 1, N)\) is factor of \(N\).
There is additional steps to complete the procedures.
To follow the procedure, \(X = \prod_{i=0}^n p_i^{\frac{1}{2} \sum_{j=1}^{n+1} t_j (e_{i,j}' - e_{i,j})}\) have to be integer too.
Therefore, we have to find $t_j$ to make \(\sum_{j=1}^{n+1} t_j (e_{i,j}' - e_{i,j}) \equiv 0 \mod 2\).
The set of coefficients \(t_j\) can be found through simple linear equation system.
To summarized the procedure, it can be written as follow.
- Find \((n+1)\) sr-pairs of $N$.
- Find coefficients set \(t_j\) satisfying the condition mentioned above.
- Calculate the \(X = \prod_{i=0}^n p_i^{\frac{1}{2} \sum_{j=1}^{n+1} t_j (e_{i,j}' - e_{i,j})}\) and find gcd between \(X\pm 1\) and \(N\).
The step 2 can be done through ordinary linear equation system.
The step 3 can be done through conventional algorithm such as Euclidean Algorithm and Multiplication Algorithm. Its complexity is \(O(n^2)\) for \(n\)-bit numbers
The difficult part is step 1. In the Schnorr’s algorithm, finding sr-pairs problems is transformed into Closest Vector Problem (CVP) of Lattice Algebra.
SR - pairs problem and Closest Vector Problems.
(On writting)
References : Factoring integers with sublinear resources on a superconducting quantum processor [https://arxiv.org/abs/2212.12372]