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

arXiv:0811.2070 · Journal of Physics B Atomic Molecular and Optical Physics

Factorizing numbers with classical interference: several implementations in optics

Andon A. Rangelov

Published Jan 12, 2009• 19 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/0953-4075/42/2/021002

Related papers

Factorization algorithm based on the periodicity measurement of a continuous truncated exponential sum

Vincenzo Tamma, Heyi Zhang, Xuehua He +2 more

We exploit the remarkable phenomena of interference in physics together with aspects of number theory in order to factorize large numbers. In particular, the introduction of continuous truncated exponential sums (CTES) allows us to develop a new algorithm for factoring several large numbers by a single measurement of the periodicity of a CTES interferogram. Such an interferogram can be obtained by measuring the interference pattern produced by polychromatic light interacting with an interferometer with variable optical paths.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Mar 31, 2010•0 citations

Factorization of numbers with Gauss sums: III. Algorithms with Entanglement

W P Schleich

We propose two algorithms to factor numbers using Gauss sums and entanglement: (i) in a Shor-like algorithm we encode the standard Gauss sum in one of two entangled states and (ii) in an interference algorithm we create a superposition of Gauss sums in the probability amplitudes of two entangled states.These schemes are rather efficient provided that there exists a fast algorithm that can detect a period of a function hidden in its zeros.

•Aug 17, 2016•4 citations

Factorization with Gauss sums: scaling properties of ghost factors

M. Štefaňák, W. Merkel, W. P. Schleich +2 more

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.

New Journal of Physics•Oct 12, 2007•26 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•23 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•20 citations

Factorization of numbers with Gauss sums: III. Algorithms with entanglement

S Wölk, W P Schleich

We propose two algorithms to factor numbers using Gauss sums and entanglement: (i) in a Shor-like algorithm we encode the standard Gauss sum in one of two entangled states and (ii) in an interference algorithm we create a superposition of Gauss sums in the probability amplitudes of two entangled states. These schemes are rather efficient provided that there exists a fast algorithm that can detect a period of a function hidden in its zeros.

arXiv:1210.6491•New Journal of Physics•Jan 24, 2012•4 citations
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.
We exploit the remarkable phenomena of interference in physics together with aspects of number theory in order to factorize large numbers. In particular, the introduction of continuous truncated exponential sums (CTES) allows us to develop a new algorithm for factoring several large numbers by a single measurement of the periodicity of a CTES interferogram. Such an interferogram can be obtained by measuring the interference pattern produced by polychromatic light interacting with an interferometer with variable optical paths.
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.
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.