Factorization of numbers with Gauss sums: I. Mathematical background

Sabine Woelk (1) , Wolfgang Merkel (1) , Wolfgang P. Schleich (1) , Ilya Averbukh (2) , Bertrand Girard (3)

1 Abteilung Quantenphysik
2 Department of Chemical Physics
3 Femto (LCAR)

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.

Domaines: Physique Atomique [physics.atom-ph]; Physique Quantique [quant-ph]

Sabine Woelk, Wolfgang Merkel, Wolfgang P. Schleich, Ilya Averbukh, Bertrand Girard. Factorization of numbers with Gauss sums: I. Mathematical background. New Journal of Physics, 2011, 13, pp.103007. ⟨10.1088/1367-2630/13/10/103007⟩. ⟨hal-00671888⟩