Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe

Q: Fachverband Quantenoptik und Photonik

Q 61: Poster Quanteneffekte

Q 61.3: Poster

Donnerstag, 22. März 2007, 16:30–18:30, Poster C

Optimal truncation of Gauss sums for integer factorization — •Martin Štefaňák^1,2, Wolfgang Merkel², Wolfgang P. Schleich², Daniel Haase³, and Helmut Maier³ — ¹Department of Physics, FJFI CTU in Prague, Czech Republic — ²Institut für Quantenphysik, Universität Ulm, Germany — ³Institut für Zahlentheorie und Wahrscheinlichkeitstheorie, Universität Ulm, Germany

We analyze truncated Gauss sums in the context of integer factorization. The absolute value of the Gauss sum is a useful tool to discriminate factors from non-factors. Recently, an experimental realization in physical systems demonstrated the ability to factorize numbers with Gauss sums. Experimental limitations directly translate into a truncation of the summation range. However, this constraint results in less contrast between factors and non-factors. We derive an upper bound on the truncation parameter which allows to suppress all non-factors below a threshold value. Moreover, we show that if we tolerate a limited number of errors we can reduce the truncation even further.