Computing the order of points on an elliptic curve module N is as difficult as factoring N

Given a square-free integer N, the group of points on an elliptic curve ove r the ring Z(N) is defined in the natural way. We prove that computing the order of points on elliptic curves over Z(N) is as difficult as factoring N , in the sense of randomly polynomial time reduction. Therefore, cryptosyst ems based on the difficulty of computing the order of points on elliptic cu rves over the ring Z(N) will be at least as robust as those based on the di fficulty of factoring N. (C) 2001 Elsevier Science Ltd. All rights reserved .