Two discrete log algorithms for super-anomalous elliptic curves and their applications

Super-anomalous elliptic curves ol er a ring Z/nZ (n = Pi(i=1)(k) p(i)(epsi lon i)) are defined by extending anomalous elliptic curves over a prime fil ed F-p. They have n points over a ring Z/nZ and p(i) points over F-pt for a ll p(i). We generalize Satoh-Araki-Smart algorithm [10], [11] and Ruck algo rithm [9], which solve a discrete logarithm problem over anomalous elliptic curves. We prove that a "discrete logarithm problem over super-anomalous e lliptic curves" can be solved in deterministic polynomial time without know ing prime factors of n.