| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 401167 | Journal of Symbolic Computation | 2014 | 6 Pages |
Abstract
We present an algorithm that recovers a decomposition of an integer N as sum of two squares from an approximation to one of the summands. It is based on Coppersmith's linearization technique which, applied directly to this problem, requires an approximation error smaller than N1/6N1/6. Our algorithm performs a two-round linearization and allows approximation errors up to N1/4N1/4.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Jaime Gutierrez, Álvar Ibeas, Antoine Joux,