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)(epsilon i)) are defined by extending anomalous elliptic curves over a prime filed F-p. They have n points over a ring Z/nZ and p(i) points over F-pt for all p(i). We generalize Satoh-Araki-Smart algorithm [10], [11] and Ruck algorithm [9], which solve a discrete logarithm problem over anomalous elliptic curves. We prove that a "discrete logarithm problem over super-anomalous elliptic curves" can be solved in deterministic polynomial time without knowing prime factors of n.
super-anomalous elliptic curves elliptic curve discrete logarithm problem deterministic polynomial time algorithm