Elliptic curve factorization using a ``partially oblivious function
This work describes, under special conditions, a speedup of Lenstra's Elliptic Curve Method (ECM) for integer factoring. Let \(N\) be an integer such that \(N = PR\), where \(P\) is a prime number not dividing \(R\), whose size is known. A partially oblivious function is a function, \(f: \mathbb{Z}_n\to \mathbb{Z}\), such that \(f(x) = f(x \text{mod }P)\) (\(f\) is oblivious to all other factors of \(N\)), and for uniformly chosen \(x\in\mathbb{Z}_N\), the probability that \(f(x) = 1\) is in the range \([0+\varepsilon,1-\varepsilon]\) for some \(\varepsilon > 0\) independent of \(N\). For certain special classes of numbers there exist polynomial-time computable partially oblivious functions; for instance, for the numbers \(N = PS^2\) we can take the Jacobi function, \(f(x) = \left(\frac xN\right)\). The author presents an algorithm for factoring \(N\) in two phases. The first phase is exactly one step of ECM. It produces a certain iterate \(\tau\) of a random point \((x, y)\) of a random elliptic curve \(y^2 = x^3+ax+b\). If the ECM step fails to produce \(P\) (as the GCD of \(N\) and some of the denominators occurring in the computation of \(\tau\) modulo \(N\)), then the second phase starts. In this phase, a partially oblivious function is used to design a random walk in the subgroup generated by \(\tau\), inspired by Pollard's rho method. If the number of points of the elliptic curve modulo \(P\) is \((U,V)\)-semismooth this phase finds \(P\) in \(O(\sqrt{V})\) elliptic curve operations. For the entire collection see [Zbl 0956.00037].
This page was built for publication: Elliptic curve factorization using a ``partially oblivious function
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2708616)
