genus 2 Jacobi Pila Schoof 42 Adleman Huang Gaudry Harley l genus 2 Jacobi 17 Jacobi Spallek 52 theta CM Jacobi genus2 Wang 61 Weber 60 Wamelen

Transcription

1 Journal of the Institute of Science and Engineering5 Chuo University Jacobi CM Type Computation of CM Type of Jacobian Varieties Jacobi CM CM Jacobi CM type reflex CM type Frobenius endomorphism Jacobi CM Jacobi CM type reflex CM type Jacobi CM CM Type Reflex CM Type 1 Jacobi Jacobi Jacobi baby-step-giant-step N O N Pohlig-Hellman baby-step-giant-step MOV 32 Frey Rück Jacobi Gaudry genus 4 O N baby-step-giant-step genus Jacobi Schoof SEA reduction CM Toyo Communication Equipment Co.,Ltd.,2-1-1 Koyato, Samukawa-machi Koza-gun, Kanagawa, Japan Department of Electrical and Electronic Engineering, Chuo University. The Institute of Science and Engineering, Chuo University Kasuga, Bunkyo-ku, Tokyo, Japan Department of Information and System Engineering, Chuo University. The Institute of Science and Engineering, Chuo University Kasuga, Bunkyo-ku, Tokyo, Japan Department of Mathematics,Chuo Uni-versity.The Institute of Science and Engineering, Chuo Uni-versity Kasuga, Bunkyoku, Tokyo, Japan. 29

2 genus 2 Jacobi Pila Schoof 42 Adleman Huang Gaudry Harley l genus 2 Jacobi 17 Jacobi Spallek 52 theta CM Jacobi genus2 Wang 61 Weber 60 Wamelen lifting Jacobi CM CM base 8 56 genus 2 Jacobi CM CM CM type reflex CM type CM CM Jacobi CM type reflex CM type Jacobi CM CM type reflex CM type CM CM type reflex CM type 2 Jacobi k F X Y k X Y C F X Y 0 C C P i D S i m i P i m i C C Abel 0 0 h k C D degd S i m i h S i P i Q i P i Q i h l 0 C Jacobi k k 0 / l Jacobi Abel Jacobi Volcheck 55 30

3 Jacobi CM Type C ab Arita 6 superelliptic curve Galbrath 13 Cantor 7 Jacobi D 1 D 2 q D 1 md 2 m 3 Ordinary Jacobi CM C Jacobi CM K K A k g Abel K EndA 2 K A CM A CM i K EndA a K i a EndA EndA k k K 2g A ordinary CM A/ q ordinary Z X 53 p ordinary Abel A/ q q-frobenius endomorphism A CM K p C q i - i 1...g A q-frobenius endomorphism Z X X Z X K Jacobi ordinary CM Algorithm1 Algorithm 1 CM Input C/ q Output C Jacobi CM K Z X ordinary false 1 i 1...g C q i - N i 2 N i M i N i q i 1 3 S a n j M i Newton a j s i SP i a j 4 Z X X 2g s1 X 2g 1 s2 X 2g 2 q g 1 X q g X 5 Z X false 6 Z X Algorithm1 O q g q g 1 O 8g/5 Og q4 1 Elkies 14 Jacobi genus 4 Ordinary Jacobi CM Type Jacobi CM type reflex CM type CM type reflex CM type Jacobi CM type reflex CM type 31

4 Jacobi CM type reflex CM type 51 r K 2g CM K * 1,...,* g r* 1,...,r* g K CM type F * 1,...,* g K F CM type x K type normn F N F x P i x * i L K G Gal L/ * i * i L F G H G K S HF S s 1 s S H g g G gs S H g G Sg S K L H Y S K K K Y CM type K Y K F reflex Algorithm 2 CM type K F reflex CM type K Y Algorithm 2 Reflex CM Type Input CM type K F Output reflex CM type K Y 1 K L 2 G Gal L/ 3 K H G 4 S HF 5 H g G Sg S 6 H K L g K /2 7 S g G g 1 S 8 K g S Y S 9 K Y Y Y K Jacobi CM type A 0 k CM K g Abel A torus g EndA M * 1,...,* 2g K M g * 1,...,* g F * 1,...,* g K F CM type A type K F A k reflex CM K A CM type K F H S H g g G gs S A simple A simple K 0 reflex type y 1,...,y g K 0 K p K 0 32

5 Jacobi CM Type p K k p K A Amod N -Frobenius endomorphism Frobenius endomorphism p N Y f f / / k A q N q f / p q p n n f / f / p f / K 0 ordinary f / 1 f / n/f / p f / Algorithm 3 Jacobi CM type K F Algorithm 3 CM Type Input C/ q Output C Jacobi CM type K F reflexcm type K Y ordinary false 1 q p n p n 2 Algorithm 1 CM K Z X Algorithm 1 false false 3 K L 4 G Gal L/ 5 K H G 6 G g T F i 7 F i 7.1 F F i 7.2 K F CM type Algorithm 2 reflexcm type K Y 7.3 K g K 0 Y K 0 K 7.4 K 0 p p P e i i 7.5 i i / p f f n K P

6 7.5.5 N Y n f Z X K p p p K F K Y CM type reflex CM type i F i F 7.1. CM Jacobi CM type reflex CM type A k k A Amod K 0 K A ordinary k reduction Algorithm 3 CM type CM Jacobi CM type reflex CM type Algorithm 4 CM Type Input Jacobi CM C/k Output CM type K F reflex CM type K Y 1 q 2 C q reduction C Algorithm 3 CM type K F reflex CM type K Y Algorithm 3 false 1. 3 K F K Y CM type reflex CM type Algorithm 4 CM 56 Frobenius endomorphism K Algorithm 4 Algorithm 5 CM Type Input Jacobi CM C/k Output CM type K F reflex CM type K Y 1 q 2 Algorithm 1 C q reduction C CM K Algorithm 1 false 1. 3 Algorithm 3 L G H T 4 F i T 4.1 F F i 4.2 K F CM type Algorithm 2 reflex CM type K Y 4.3 K g K 0 Y K 0 K 4.4 Nw p w K 4.5 p k f / p 4.6 p f -Frobenius endomorphism Z X Algorithm p N Y w f 4.8 p Z X 4.9 Z X Z X K F K Y CM type reflex CM type 34

7 Jacobi CM Type 4.10 F i F CM Algorithm 1 Algorithm 1 C/ 5 Y 2 X 7 4X 6 3X 5 3X 4 X 3 X 4 Jacobi Frobenius endomorphism p Z X Z X X 6 8X 4 4X 3 40X CM Type Reflex CM Type Algorithm2 3 CM K p L L a a 12 40a 10 70a 9 473a 8 130a a a a 4 320a a a s i G Gal L/ s i a b i b i L 1 a a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 a 11 b b / b / b / b / b / b / , b / b / b / b / b /

8 r s 4 CM type K F reflex CM type K Y K p p 6 8p 4 4p 3 40p F s 1 s 2 s 3 K x x 6 26x 5 223x 4 654x 3 54x x Y s 1 s 5 s CM Type Reflex CM Type p genus 2 Jacobi CM type reflex CM type Algorithm p p CM type reflex CM type A, L 4 B L 8 1 CM Type, Reflex CM Type KASH/KANT 9 UltraSPARC-IIi301MHz L. M. Adleman, A subexponential algorithm for the discrete logarithm problem with applications, Proc. 20th Ann. IEEE Symp. on Foundations of Computer Science,pp ,1979. L. M. Adleman,M. D. A. Huang Primality Testing and Abelian Varieties Over Finite Fields, Springer-Verlag,1992. L. M. Adleman,M. D. A. Huang Counting rational points on curves and abelian varieties over finite fields, Proc. of ANTS-2,Springer-Verlag,1996. L. M. Adleman,J. D. Marrais,M. D. Huang: A Subexponential Algorithms for Discrete Logarithms over the Rational Subgroup of the Jacobians of Large Genus Hyperelliptic Curves over Finite Fields, Proc. of ANTS95,Springer,1995. S. Arita, Public key cryptosystems with C ab curve 2, IEICE,Proc. of SCIS 98,7. 1-B,

9 Jacobi CM Type 6 S. Arita, A. Yoshikawa, H. Miyauch, A software implementation of discrete-log-based cryptosystems with C ab curve, IEEE Japan Proc. of SCIS 99, T3-1. 3, D. Cantor Computing in the jacobian of hyperelliptic curve, Math. Comp., vol. 48, p , J. Chao, N. Matsuda, S, Tsujii Efficient construction of secure hyperelliptic discrete logarithm problems Springer-Verlag Lecture Notes on Computer Science, Vol. 1334, pp , M. Daberkow, C. Fieker, J. Klners, M. Pohst, K. Roegner, M. Schrnig, K. Wildanger KANT V4, J. Symb. Comp., Vol. 24, No3, pp , H. Cohen A course in computational algebraic number theory Springer, GTM-138, J. DeJong, R. Noot, Jacobians with complex multiplication, Arithmetic Algebraic Geometry, Birkhäuser PM89, pp , I. Duursma, P. Gaudry, F. Morain, Speeding up the discrete log computation on curves with automorphisms, LIX/RR/99/03, Ecole Polytech., S. D. Galbrath, S. Paulus, N. P. Smart Arithmetic on superelliptic curves, preprint. 14 N. D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational Perspective on Number Theory in honor of A. O. L. Atkin, G. Frey, H. G. Rück A remark concerning m-divisibility and the discrete logarihm in the divisor class group of curves, Mathematics of Computation, 62, , P. Gaudry A variant of the Adelman-DeMarrais-Huang algorithm and its application to small genera Preliminary version, June P. Gaudry, R. Harley, Counting Points on Hyperelliptic Curves over Finite Fields, ANTS-IV, Springer, LNCS1838, pp , T. Haga, K. Matsuo, J. Chao, S. Tsujii Construction of CM Hyperelliptic Curve using Ordinary Liftings, IEICE, Japan, Proc. of SCIS2000, C51, M. D. Huang, D. Ierardi Counting Rational Point on Curves over Finite Fields, Proc. 32nd IEEE Symp. on the Foundations of Computers Science, T. Honda Isogeny classes of abelian varieties over finite fields, J. Math. Soc. Japan, vol. 20, No. 1-2, p , J. Igusa Arithmetic variety of moduli for genus two, Ann. of Math., vol. 72, No. 3, p , H. Kawashiro, O. Nakamura, J. Chao, S. Tsujii Construction of CM hyperelliptic curves using RM family, IEICE ISEC97-72, pp , J. Klüners, M. Pohst On Computing Subfields, J. Symbolic Computation, 11, H. Kuboyama, K. Kamio, K. Matsuo, J. Chao, S. Tsujii Construction of Superelliptic Curve Cryptosystem, IEICE, Japan, Proc. of SCIS2000, C52, N. Koblitz Elliptic Curve Cryptosystems, Math. Comp., vol. 48, p , N. Koblitz Hyperelliptic cryptosystems, J. of Cryptology, vol. 1, p, , N. Koblitz, A very easy way to generate curves over prime field for hyperelliptic cryptosystem, CRYPTO 97, Ramp session, S. Lang Abelian Varieties, Interscience, New York S. Lang Complex multiplication Springer-Verlag, H. W. Lenstra Algorithms in Algebraic Number Theory, Bulletin of The Amer. Math. Soc., 2, vol. 26, pp , K. Matsuo, J. Chao, S. Tsujii On lifting of CM hyperelliptic curves, IEICE Proc. SCIS 99, A. Menezes, S. Vanstone, T. Okamoto Reducing Elliptic Curve Logarithms to Logarithms in a Finite Fields, Proc. of STOC, p ,

10 33 A. Menezes Elliptic Curve Public Key Cryptosystems, Kluwer Academic, V. S. Miller Use of Elliptic Curves in Cryptography, Advances in Cryptology Proceedings of Crypto 85, Lecture Notes in. Computer Science, 218, Springer-Verlag, p , D. Mumford Abelian varieties, Tata Studies in Mathematics, Oxford, Bobay, D. Mumford Tata Lectures on Theta, Birkhäuser, Boston, D. Mumford Tata Lectures on Theta, Birkhäuser, Boston, V. Müller, A. Stein, C. Thiel Computing discrete logarithms in real quadratic congruence function fields of large genus Preprint, Nov. 13, K. Nagao, Construction of the Jacobians of Curves Y 2 X 5 k/ p with Prime Order, Manuscript, F. Oort, T, Sekiguchi The canonical lifting of an ordinary jacobian variety need not be a jacobian variety, J. Math. Soc. Japan, Vol. 38, no. 3, S. Paulus Ein Algorithmus zur Berechunung der Klassengruppe quadratischer Ordnungen, über Hauptidealringen, GH Essen, Dr. Thesis, J. Pila Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp., vol. 55, p , B. Poonen Computational aspects of curves of genus at least 2, H. Cohen Ed Algorithmic number theory Lecture Notes in Computer Science, 1122, Second International Symposium, ANTS-, Proceedings, pp M. Pohst, H. Zassenhaus Algorithmic Algebraic Number Theory, Cambridge, M. Pohst Computational Algebraic Number Theory, DMV21, Birkhäuser, H. G. Rück on the discrete logarithm problem in the divisor class group of curves Preprint, R. Schoof Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp., vol. 44, p , J. P. Serre, J. Tate Good reduction of abelian varieties, Ann. of Math. 2, , page G. Shimura Introduction to arithmetic theory of automorphic function, Iwanami-Shoten and Princeton, G. Shimura, Y. Taniyama Complex multiplication of abelian varieties and its application to number theory, Pub. Math. Soc. Jap. no. 6, G. Shimura Abelian Varieties with Complex Multiplication and Modular Functions, Princeton Univ. Press, A-M. Spallek Kurven vom Geschlecht 2 und ihre An-wendung in Public-Key-Kryptosystemen, Dissertation, preprint, No. 18, J. Tate Endomorphisms of Abelian varieties over finite fields, Invent. Math. 2, p , S. Uchiyama, T. Saitoh A Note on The Discrete Logarithm Problem on Elliptic Curves of Trace Two, IEICE Japan Tech. Rep. ISEC98-27, pp , E. J. Volcheck Computing in the Jacobian of a plane algebraic curve, Proc. of ANT-1, p , LNCS-877, T. Wakabayashi, T. Nakamizo, K. Matsuo, J. Chao, S. Tsujii Computation of Weil Number of CM Varieties and Design of Jacobian Cryptosystems, IEICE, Japan, Proc. of SCIS2000, C50, P. V. Wamelen Examples of genus two CM curves defined over the rationals, Math. Comp., , pp , P. V. Wamelen PROVING THAT A GENUS 2 CURVE HAS COMPLEX MULTIPLICATION, Math. Comp., vol. 68, 1999 pp,

11 Jacobi CM Type 59 W. C. Waterhouse Abelian varieties over finite fields Ann. scient. EC. Norm. Sup. 4 t. 2, 1969, p H. J. Weber Hyperelliptic Simple Factor of J 0 N with Dimension at Least 3, Experimental Math., vol6, X. Wang 2-dimensional simple factors of J 0 N, manuscripta math., 87, pp ,