The distribution of solutions to \(XN=N \pmod a\) with an application to factoring integers (Q2855585)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The distribution of solutions to \(XN=N \pmod a\) with an application to factoring integers |
scientific article; zbMATH DE number 6220299
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The distribution of solutions to \(XN=N \pmod a\) with an application to factoring integers |
scientific article; zbMATH DE number 6220299 |
Statements
25 October 2013
0 references
factorization
0 references
Kloosterman sum
0 references
factoring algorithm
0 references
uniform distribution of solution
0 references
The distribution of solutions to \(XN=N \pmod a\) with an application to factoring integers (English)
0 references
The authors consider the uniform distribution of solutions \((x,y)\) to \(xy=N\mod a\) and obtain a bound on the second moment of the number of solutions in squares of length approximately \(a^{1/2}\). In this paper, the author investigate an application of this fact to the problem of factoring integers. The author gives new factoring algorithm for the integer \(N\) which beats trial division, prove that it runs in time \(O(N^{1/3+\varepsilon})\) and discuss the potential for improving the runtime to sub-exponential.
0 references
