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

Abstract

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. Woelk et al. also published in this issue [Woelk, 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.

8 pages, 5 figures

References in corpus (7)

• NMR experiment factors numbers with Gauss sums
• Factorization of Numbers with the temporal Talbot effect: Optical implementation by a sequence of shaped ultrashort pulses
• Gauss sum factorization with cold atoms
• Factorizing Numbers with the Gauss Sum Technique: NMR Implementations
• NMR implementation of Factoring Large Numbers with GaußSums: Suppression of Ghost Factors
• Factorizing numbers with classical interference: several implementations in optics
• NMR implementations of Gauss sums

Cited by in corpus (11)

• From the Physics to the Computational Complexity of Multiboson Correlation Interference
• Factoring numbers with a single interferogram
• Multi-Boson Correlation Sampling
• Prime Number Decomposition using the Talbot Effect
• Factorization of numbers with Gauss sums: I. Mathematical background
• Multipath Correlation Interference and Controlled-NOT Gate Simulation with a Thermal Source
• Spatial interference between pairs of disjoint optical paths with a single chaotic source
• Factorization of numbers with Gauss sums: II. Suggestions for implementations with chirped laser pulses
• Analogue algorithm for parallel factorization of an exponential number of large integers II. Optical implementation
• Analogue algorithm for parallel factorization of an exponential number of large integers I. Theoretical description
• Factorization of numbers with Gauss sums: III. Algorithms with Entanglement