Factorization with Gauss sums: scaling properties of ghost factors

Abstract

Recent experiments have shown that truncated Gauss sums allow us to find the factors of an integer N. This method relies on the fact that for a factor the absolute value of the Gauss sum is unity. However, for every integer N there exist integers which are not factors, but where the Gauss sum reaches a value which is arbitrarily close to unity. In order to distinguish such ghost factors from real factors we need to amplify this difference. We show that a proper choice of the truncation parameter of the Gauss sum suppresses the ghost factors below a threshold value. We derive the scaling law of the truncation parameter on the number to be factored. Moreover, we show that this scaling law is also necessary for the success of our factorization scheme, even if we relax the threshold or allow limited error tolerance.