We introduce a new factorization algorithm based on the optical computation by multi-path interference of the periodicity of a "factoring" function given by exponential sums at continuous arguments. We demonstrate that this algorithm allows, in principle, the prime number decomposition of several large numbers by exploiting a remarking rescaling property of this periodic function. Such a function is recorded by measuring optical interferograms with a multi-path Michelson interferometer, a polychromatic light source and a spectrometer. The information about factors is encoded in the location of the inteferogram maxima.
We introduce a new factorization algorithm based on the optical computation by multi-path interference of the periodicity of a "factoring" function given by exponential sums at continuous arguments. We demonstrate that this algorithm allows, in principle, the prime number decomposition of several large numbers by exploiting a remarking rescaling property of this periodic function. Such a function is recorded by measuring optical interferograms with a multi-path Michelson interferometer, a polychromatic light source and a spectrometer. The information about factors is encoded in the location of the inteferogram maxima.
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.
We introduce a new factorization algorithm based on the measurement of the periodicity of a determined function, similar to Shor's algorithm. In particular, such a function is given by a generalized continuous truncated exponential sum (CTES). The CTES interference pattern satisfies a remarkable scaling property, which allows one to plot the interferogram as a function of a suitable continuous variable depending on the number to factorize. This allows one, in principle, to factorize arbitrary numbers with a single interferogram. In particular, information about the factors is encoded in the location of the interference maxima, which repeat periodically in the interferogram. A possible analogue computer for the implementation of such an algorithm can be realized using multi-path optical interferometers, with polychromatic light sources and a high-resolution spectrometer. The experimental accuracy in the realization of the CTES interferogram and the bandwidth of the polychromatic sources determine the largest number Nmax factorable. Once the CTES interferogram is recorded, all the numbers with value up to Nmax can be factorable, without performing any further measurement.
We will describe a new factorization algorithm based on the reproduction of continuous exponential sums, using the interference pattern produced by polychromatic light interacting with an interferometer with variable optical paths. We will describe two possible interferometers: a generalized symmetric Michelson interferometer and a liquid crystal grating. Such an algorithm allows, 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. It also allows to solve the problem of ghost factors and to factorize different numbers using the same output interference pattern.
The security of codes, for example in credit card and government information, relies on the fact that the factorization of a large integer N is a rather costly process on a classical digital computer. Such a security is endangered by Shor's algorithm which employs entangled quantum systems to find, with a polynomial number of resources, the period of a function which is connected with the factors of N. We can surely expect a possible future realization of such a method for large numbers, but so far the period of Shor's function has been only computed for the number 15. Inspired by Shor's idea, our work aims to methods of factorization based on the periodicity measurement of a given continuous periodic factoring function which is physically implementable using an analogue computer. In particular, we have focused on both the theoretical and the experimental analysis of Gauss sums with continuous arguments leading to a new factorization algorithm. The procedure allows, for the first time, to factor several numbers by measuring the periodicity of Gauss sums performing first-order factoring'' interference processes. We experimentally implemented this idea by exploiting polychromatic optical interference in the visible range with a multi-path interferometer, and achieved the factorization of seven digit numbers. The physical principle behind this factoring interference procedure can be potentially exploited also on entangled systems, as multi-photon entangled states, in order to achieve a polynomial scaling in the number of resources.
We present the experimental proof of principle of a new factorization algorithm based on the implementation of generalized continuous truncated Gauss sums using a generalized Michelson interferometer with variable interfering optical paths. Respect to the past Gauss sums realizations, such algorithm allow us to check all the trial factors l of a number N at the same time in a single run, avoiding the pre-calculation of the ratio N/l and it is generalizable to higher order j. Most important, this procedure allows, for the first time, to factorize different numbers in a single run, despite the previous Gauss sums realization, in which was necessary to run the experiment for each trial factors.
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.