Düsseldorf 2007 – wissenschaftliches Programm
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ňák1,2, Wolfgang Merkel2, Wolfgang P. Schleich2, Daniel Haase3, and Helmut Maier3 — 1Department of Physics, FJFI CTU in Prague, Czech Republic — 2Institut für Quantenphysik, Universität Ulm, Germany — 3Institut 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.