deterministic polynomial time without knowing prime factors of n." />


Two Discrete Log Algorithms for Super-Anomalous Elliptic Curves and Their Applications

Noboru KUNIHIRO  Kenji KOYAMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.1   pp.10-16
Publication Date: 2000/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
elliptic curve discrete logarithm problem,  super-anomalous elliptic curves,  deterministic polynomial time algorithm,  

Full Text: PDF(361.7KB)>>
Buy this Article




Summary: 
Super-anomalous elliptic curves over a ring Z/nZ ;(ni=1k piei) are defined by extending anomalous elliptic curves over a prime filed Fp. They have n points over a ring Z/nZ and pi points over Fpi for all pi. We generalize Satoh-Araki-Smart algorithm and Ruck algorithm, 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.