Computing the order of points on an elliptic curve modulo \(N\) is as difficult as factoring \(N\) (Q5938924)

Given a square-free integer \(N=p_1\dots p_r, r \geq 2,\) the group of points on an elliptic curve over the ring \(Z_N\) is defined. Assume that one has an oracle that is able to compute the order of any point on an elliptic curve over \(Z_N\). Then a random polynomial algorithm is presented for the factorization of \(N\). Let \(E_N(a,b)\) denote the elliptic curve \(y^2 = x^3 + ax + b\) over \(Z_N\). Let \(\Delta = 4a^3 + 27b^2\) be the discriminant of \(E_N(a,b)\). The algorithm fails to find a divisor of \(N\) iff \(\Delta = 0\) or if \(\gcd(\Delta,N) = 1\), the order of the chosen point \(P\) is odd but the order of the elliptic curves \(E_{p_i}(a,b), 1\leq i \leq r\), are all even. The proof of the main result is based on the fact that the probability of the event mentioned in the last sequence is at most \(184/225\). The main result of the paper means that cryptosystems based on the difficulty of computing the order of points on elliptic curves over the ring \(Z_N\) will be at least as robust as those based on the difficulty of factoring \(N\).