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

Factorizing numbers with the Gauss sum technique

Dieter Suter, T. S. Mahesh, Nageswaran Rajendran, Xinhua Peng

Published Jun 4, 2007• 25 citations
Publisher

Abstract

Several physics-based algorithms for factorizing large numbers were recently presented. A notable recent algorthm by Schleich et al. uses Gauss sums for distinguishing between factors and nonfactors. We demonstrate two NMR techniques that evaluate Gauss sums and thus implement their algorithm. The first one is based on differential excitation of a single spin magnetization by a cascade of rf pulses. The second method is based on spatial averaging and selective refocusing of magnetization for Gauss sums corresponding to factors. All factors of 16 637 and 52 882 363 are successfully obtained.

DOI
10.17877/de290r-3047

Related papers

Factorizing numbers with the Gauss sum technique: NMR implementations

T. S. Mahesh, Nageswaran Rajendran, Xinhua Peng +1 more

Several physics-based algorithms for factorizing large numbers were recently presented. A notable recent algorthm by Schleich et al. uses Gauss sums for distinguishing between factors and nonfactors. We demonstrate two NMR techniques that evaluate Gauss sums and thus implement their algorithm. The first one is based on differential excitation of a single spin magnetization by a cascade of rf pulses. The second method is based on spatial averaging and selective refocusing of magnetization for Gauss sums corresponding to factors. All factors of 16 637 and 52 882 363 are successfully obtained.

arXiv:quant-ph/0701205•Physical Review A•Jun 4, 2007•42 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•24 citations

Comment on "NMR Experiment Factors Numbers with Gauss Sums"

Julia A. Wei Xiaohua Jones

Mehring et al. have recently described an elegant nuclear magnetic resonance (NMR) experiment implementing an algorithm to factor numbers based on the properties of Gauss sums. Similar experiments have also been described by Mahesh et al. In fact these algorithms do not factor numbers directly, but rather check whether a trial integer $\ell$ is a factor of a given integer $N$. Here I show that these NMR schemes cannot be used for factor checking without first implicitly determining whether or not $\ell$ is a factor of $N$.

arXiv:0704.2065•Apr 16, 2007•2 citations

Factorization of Numbers and Gauss Sums

Wolfgang P. Schleich

Gauss sums play an important role in number theory as well as quantum physics. We analyze quantum systems which implement Gauss sums and allow us to factor large integers. We review recent experiments. Article not available.

The Rochester Conferences on Coherence and Quantum Optics and the Quantum Information and Measurement meeting•Jan 1, 2007•1 citation

NMR Experiment Factors Numbers with Gauss Sums

Michael Mehring, Klaus Müller, Ilya Sh. Averbukh +2 more

We factor the number 157573 using an NMR implementation of Gauss sums. Although the current implementation is classical and scales exponentially, we believe that an extension to the quantum regime using entangled states is possible.

arXiv:quant-ph/0609174•Physical Review Letters•Mar 22, 2007•85 citations

Factorization of numbers with Gauss sums: II. Suggestions for implementation with chirped laser pulses

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

We propose three implementations of the Gauss sum factorization schemes discussed in part I of this series (Wölk et al 2011 New J. Phys. 13 103007): (i) a two-photon transition in a multi-level ladder system induced by a chirped laser pulse, (ii) a chirped one-photon transition in a two-level atom with a periodically modulated excited state and (iii) a linearly chirped one-photon transition driven by a sequence of ultrashort pulses. For each of these quantum systems, we show that the excitation probability amplitude is given by an appropriate Gauss sum. We provide rules on how to encode the number N to be factored in our system and how to identify the factors of N in the fluorescence signal of the excited state.

arXiv:1210.6487•New Journal of Physics•Oct 7, 2011•12 citations
Several physics-based algorithms for factorizing large numbers were recently presented. A notable recent algorthm by Schleich et al. uses Gauss sums for distinguishing between factors and nonfactors. We demonstrate two NMR techniques that evaluate Gauss sums and thus implement their algorithm. The first one is based on differential excitation of a single spin magnetization by a cascade of rf pulses. The second method is based on spatial averaging and selective refocusing of magnetization for Gauss sums corresponding to factors. All factors of 16 637 and 52 882 363 are successfully obtained.
Several physics-based algorithms for factorizing large numbers were recently presented. A notable recent algorthm by Schleich et al. uses Gauss sums for distinguishing between factors and nonfactors. We demonstrate two NMR techniques that evaluate Gauss sums and thus implement their algorithm. The first one is based on differential excitation of a single spin magnetization by a cascade of rf pulses. The second method is based on spatial averaging and selective refocusing of magnetization for Gauss sums corresponding to factors. All factors of 16 637 and 52 882 363 are successfully obtained.
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.
Mehring et al. have recently described an elegant nuclear magnetic resonance (NMR) experiment implementing an algorithm to factor numbers based on the properties of Gauss sums. Similar experiments have also been described by Mahesh et al. In fact these algorithms do not factor numbers directly, but rather check whether a trial integer ℓ\ellℓ is a factor of a given integer NNN. Here I show that these NMR schemes cannot be used for factor checking without first implicitly determining whether or not ℓ\ellℓ is a factor of NNN.
We propose three implementations of the Gauss sum factorization schemes discussed in part I of this series (Wölk et al 2011 New J. Phys. 13 103007): (i) a two-photon transition in a multi-level ladder system induced by a chirped laser pulse, (ii) a chirped one-photon transition in a two-level atom with a periodically modulated excited state and (iii) a linearly chirped one-photon transition driven by a sequence of ultrashort pulses. For each of these quantum systems, we show that the excitation probability amplitude is given by an appropriate Gauss sum. We provide rules on how to encode the number N to be factored in our system and how to identify the factors of N in the fluorescence signal of the excited state.