Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

New Journal of Physics

Factorization with Gauss sums: scaling properties of ghost factors

M. Štefaňák, W. Merkel, W. P. Schleich, D Haase, Helmut Maier

Published Oct 12, 2007• 25 citations
Publisher

Abstract

Recent experiments have shown that truncated Gauss sums allow us to find the factors of an integer N . This method relies on the fact that for a factor the absolute value of the Gauss sum is unity. However, for every integer N there exist integers which are not factors, but where the Gauss sum reaches a value which is arbitrarily close to unity. In order to distinguish such ghost factors from real factors we need to amplify this difference. We show that a proper choice of the truncation parameter of the Gauss sum suppresses the ghost factors below a threshold value. We derive the scaling law of the truncation parameter on the number to be factored. Moreover, we show that this scaling law is also necessary for the success of our factorization scheme, even if we relax the threshold or allow limited error tolerance.

DOI
10.1088/1367-2630/9/10/370

Related papers

Factorization with exponential sums

M. Štefaňák, D Haase, W. Merkel +2 more

We generalize the concept of factorization using truncated Gauss sums to exponential sums where the phase increases with the jth power of the summation index. For such sums the number of terms needed to suppress ghost factors of N scales as . Unfortunately, this advantageous scaling law is accompanied by a disadvantage: the gap between factors and non-factors decreases rapidly with increasing power j and as a consequence it gets more difficult to identify factors. This feature serves as our motivation to study sums with an exponential phase. Our numerical simulations indicate that in this case the scaling law is logarithmic and that we retain a significant gap between factors and non-factors.

Journal of Physics A Mathematical and Theoretical•Jul 15, 2008•15 citations

NMR implementation of factoring large numbers with Gauß sums: Suppression of ghost factors

Xinhua Peng, Dieter Suter

Finding the factors of an integer can be achieved by various experimental techniques, based on an algorithm developed by Schleich et al . ( Fortschr. Phys. , 54 (2006) 856), which uses specific properties of Gauß sums. Experimental limitations usually require truncation of these series, but if the truncation parameter is too small, it is no longer possible to distinguish between factors and so-called “ghost" factors. Here, we discuss two techniques for distinguishing between true factors and ghost factors while keeping the number of terms in the sum constant or only slowly increasing. We experimentally test these modified algorithms in a nuclear spin system, using NMR.

arXiv:0803.3396•Europhysics Letters (EPL)•Nov 1, 2008•22 citations

Ghost factors in Gauss-sum factorization with transmon qubits

Lin Htoo Zaw, Yuanzheng Paul Tan, Long Hoang Nguyen +8 more

A challenge in the Gauss-sum factorization scheme is the presence of ghost factors, nonfactors that behave similarly to actual factors of an integer, which might lead to the misidentification of nonfactors as factors or vice versa, especially in the presence of noise. We investigate type II ghost factors, which are the class of ghost factors that cannot be suppressed with techniques previously laid out in the literature. The presence of type II ghost factors and the coherence time of the qubit set an upper limit for the total experiment time, and hence the largest factorizable number with this scheme. Discernibility is a figure of merit introduced to characterize this behavior. We introduce preprocessing as a strategy to increase the discernibility of a system, and demonstrate the technique with a transmon qubit. This can bring the total experiment time of the system closer to its decoherence limit, and increase the largest factorizable number.

arXiv:2104.11368•Physical Review A•Dec 7, 2021•3 citations

Factorization of numbers with Gauss sums: I. Mathematical background

Sabine Wölk, W. Merkel, Wolfgang P. Schleich +2 more

We use the periodicity properties of generalized Gauss sums to factor numbers. Moreover, we derive rules for finding the factors and illustrate this factorization scheme for various examples. This algorithm relies solely on interference and scales exponentially.

arXiv:1210.6474•New Journal of Physics•Oct 7, 2011•22 citations

Factorizing numbers with classical interference: several implementations in optics

Andon A. Rangelov

Truncated Fourier, Gauss, Kummer and exponential sums can be used to factorize numbers: for a factor these sums equal unity in absolute value, whereas they nearly vanish for any other number. We show how this factorization algorithm can emerge from superpositions of classical light waves and we present a number of simple implementations in optics.

arXiv:0811.2070•Journal of Physics B Atomic Molecular and Optical Physics•Jan 12, 2009•20 citations

New factorization algorithm based on a continuous representation of truncated Gauss sums

Vincenzo Tamma, Heyi Zhang, Xuehua He +2 more

In this paper, we will describe a new factorization algorithm based on the continuous representation of Gauss sums, generalizable to orders j > 2. Such an algorithm allows one, for the first time, to find all the factors of a number N in a single run without precalculating the ratio N/l, where l are all the possible trial factors. Continuous truncated exponential sums turn out to be a powerful tool for distinguishing factors from non-factors (we also suggest, with regard to this topic, to read an interesting paper by S. Wölk et al. also published in this issue [Wölk, Feiler, Schleich, J. Mod. Opt. in press]) and factorizing different numbers at the same time. We will also describe two possible M-path optical interferometers, which can be used to experimentally realize this algorithm: a liquid crystal grating and a generalized symmetric Michelson interferometer.

arXiv:0811.1595•Journal of Modern Optics•Sep 23, 2009•18 citations
Recent experiments have shown that truncated Gauss sums allow us to find the factors of an integer N . This method relies on the fact that for a factor the absolute value of the Gauss sum is unity. However, for every integer N there exist integers which are not factors, but where the Gauss sum reaches a value which is arbitrarily close to unity. In order to distinguish such ghost factors from real factors we need to amplify this difference. We show that a proper choice of the truncation parameter of the Gauss sum suppresses the ghost factors below a threshold value. We derive the scaling law of the truncation parameter on the number to be factored. Moreover, we show that this scaling law is also necessary for the success of our factorization scheme, even if we relax the threshold or allow limited error tolerance.
We generalize the concept of factorization using truncated Gauss sums to exponential sums where the phase increases with the jth power of the summation index. For such sums the number of terms needed to suppress ghost factors of N scales as . Unfortunately, this advantageous scaling law is accompanied by a disadvantage: the gap between factors and non-factors decreases rapidly with increasing power j and as a consequence it gets more difficult to identify factors. This feature serves as our motivation to study sums with an exponential phase. Our numerical simulations indicate that in this case the scaling law is logarithmic and that we retain a significant gap between factors and non-factors.
Finding the factors of an integer can be achieved by various experimental techniques, based on an algorithm developed by Schleich et al . ( Fortschr. Phys. , 54 (2006) 856), which uses specific properties of Gauß sums. Experimental limitations usually require truncation of these series, but if the truncation parameter is too small, it is no longer possible to distinguish between factors and so-called “ghost" factors. Here, we discuss two techniques for distinguishing between true factors and ghost factors while keeping the number of terms in the sum constant or only slowly increasing. We experimentally test these modified algorithms in a nuclear spin system, using NMR.
A challenge in the Gauss-sum factorization scheme is the presence of ghost factors, nonfactors that behave similarly to actual factors of an integer, which might lead to the misidentification of nonfactors as factors or vice versa, especially in the presence of noise. We investigate type II ghost factors, which are the class of ghost factors that cannot be suppressed with techniques previously laid out in the literature. The presence of type II ghost factors and the coherence time of the qubit set an upper limit for the total experiment time, and hence the largest factorizable number with this scheme. Discernibility is a figure of merit introduced to characterize this behavior. We introduce preprocessing as a strategy to increase the discernibility of a system, and demonstrate the technique with a transmon qubit. This can bring the total experiment time of the system closer to its decoherence limit, and increase the largest factorizable number.
In this paper, we will describe a new factorization algorithm based on the continuous representation of Gauss sums, generalizable to orders j > 2. Such an algorithm allows one, for the first time, to find all the factors of a number N in a single run without precalculating the ratio N/l, where l are all the possible trial factors. Continuous truncated exponential sums turn out to be a powerful tool for distinguishing factors from non-factors (we also suggest, with regard to this topic, to read an interesting paper by S. Wölk et al. also published in this issue [Wölk, Feiler, Schleich, J. Mod. Opt. in press]) and factorizing different numbers at the same time. We will also describe two possible M-path optical interferometers, which can be used to experimentally realize this algorithm: a liquid crystal grating and a generalized symmetric Michelson interferometer.