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. 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.

Keywords:

• factorization
• optical interference
• Gauss sums
• exponential sums
• continuous generalization
• Michelson interferometer
• liquid crystals

Acknowledgements

A. Rangelov proposed, independently from us, an interesting factorization scheme based on exponential sums, which also overcomes pre-calculation of the ratio N/l present in the past proposals. Rangelov's approach is based on the use of a Mach–Zehnder interferometer 20, with fixed indexes of refraction in each interfering path. This unfortunately means that we need to change the optical setup, depending on the number we want to factorize. Moreover, such a scheme does not include a way to check all the trial factors at the same time and for different values of N. The authors thank M. D'Angelo, J. Franson, T. Pittman, A. Rangelov, M.H. Rubin, G. Scarcelli, S. Wölk, T. Worchesky and, in particular, W. Schleich for useful suggestions and stimulating discussions.

Notes

Notes

1. In particular, in 8, it is shown that at least M ∼ N ^1/2j terms in the sum are necessary in order to suppress all the ghost factors under the threshold value of 1/2^1/2; however, in general, the necessary threshold can be larger than 1/2^1/2.

2. A detailed analysis of the experimental error associated with the reproduction of continuous exponential sums goes beyond the purpose of this paper and it will be described in a further publication.