index calculus 2008 3 8 1
generalized Weil descent p :, E/F p 3 : Y 2 = f(x), where f(x) = X 3 + AX + B, A F p, B F p 3 E(F p 3) 3 : Generalized Weil descent E(F p 4) 2
Index calculus Plain version Double-large-prime version Relation collection Gaudry Nagao 3
E(F p n) index calculus Index calculus(1991:adleman-demarrais-huang, 1997:Gaudry) Weil descent(1998:frey) E(F p n) F p index calculus Generalized Weil descent(2004:gaudry, 2007:Nagao) E(F p n) index calculus 4
Generalized Weil descent Step1 : Relation collection part Relation Gröbner Step2 : Linear algebra part relation 5
Relation collection part B 0 := {P i = (x i, y i ) E(F p 3) x i F p }, #B 0 = O(p) For Q E(F p 3) Relation : Q + P 1 + P 2 + P 3 = 0, P i B 0 Step1 : Step2 : Gröbner Gröbner 6
Relation collection Gaudry Semaev summation polynomials Gröbner Nagao Gaudry Gröbner 7
Gaudry 1 Semaev summation polynomials For P i = (x i, y i ) E(F p 3) f m (x 1, x 2, x 3,..., x m ) = 0, x 1, x 2, x 3,..., x m F p 3 P 1 + P 2 + P 3 + + P m = 0 E(F p 3) 8
For Q = (x, y) E(F p 3) Gaudry 2 Relation : Q + P 1 + P 2 + P 3 = 0, P i B 0 Relation 1 6 For P i = (X i, Y i ) E(F p 3), : X i, Y i Step1 : f 3 (X 1, X 2, X), f 3 (X 3, x, X) Step2 : f 4 (X 1, X 2, X 3, x) =Resultant(f 3, f 3, X) Step3 : X 1, X 2, X 3 9
Gaudry 3 For Q E(F p 3), P 1, P 2, P 3 E(F p 3), f(x) = X 3 + AX + B Step1: Summation polynomial f 3 (X 1, X 2, X) = (X 1 X 2 ) 2 X 2 2((X 1 + X 2 )(X 1 X 2 + A) + 2B) +((X 1 X 2 A) 2 4B(X 1 + X 2 )) f 3 (X 3, x, X) = (X 3 x) 2 X 2 2((X 3 + x)(x 3 x + A) + 2B) +((X 3 x A) 2 4B(X 3 + x)) 10
Gaudry 4 Step2: f 4 (X 1, X 2, X 3, x) = Resultant(f 3, f 3, X) Step3: F p 3/F p 1, t, t 2 f 4 = ϕ 0 (X 1, X 2, X 3 ) + ϕ 1 (X 1, X 2, X 3 )t + ϕ 2 (X 1, X 2, X 3 )t 2 where ϕ i (X 1, X 2, X 3 ) F p [X 1, X 2, X 3 ] f 4 (X 1, X 2, X 3, x) = 0 Q + P 1 + P 2 + P 3 = 0 ϕ 0 = 0, ϕ 1 = 0, ϕ 2 = 0 ϕ 0 = 0, ϕ 1 = 0, ϕ 2 = 0 X 1, X 2, X 3 11
Gaudry Relation Step1 : ϕ 0 = 0, ϕ 1 = 0, ϕ 2 = 0 Step2 : Gröbner Step3 : X 1, X 2, X 3 F p P i = (X i, Y i ) B 0 12
Gaudry :, :, Step1 : ϕ 0 = 0, ϕ 1 = 0, ϕ 2 = 0 T 1 = X 1 + X 2 + X 3 T 2 = X 1 X 2 + X 2 X 3 + X 1 X 3 T 3 = X 1 X 2 X 3 Step2 : ϕ 0 (T 1, T 2, T 3 ) = 0, ϕ 1 (T 1, T 2, T 3 ) = 0, ϕ 2 (T 1, T 2, T 3 ) = 0 Gröbner Step3 : X 3 + T 1 X 2 + T 2 X + T 3, : X X 1, X 2, X 3 13
Nagao 1 For Q = (x, y) E(F p 3) Relation : Q + P 1 + P 2 + P 3 = 0, P i B 0 Q, P 1, P 2, P 3 E h(x, Y ) = 0 h(x, Y ) = (X x)(x + u) + (Y y)v, : u, v 14
Nagao 2 h(x, Y ) = 0 Y 2 = f(x) Y S(X) := v 2 f(x) + ((X x)(u + X) yv) 2 = X 4 + ( v 2 + 2u 2x)X 3 +( 2yv + u 2 4xu + x 2 )X 2 +( Av 2 2yuv + 2xyv 2xu 2 + 2x 2 u)x Bv 2 + y 2 v 2 + 2xyuv + x 2 u 2 = 0 15
(X x) S(X) g(x) := S(X) X x Nagao 3 g(x) := X 3 + C 2 X 2 + C 1 X + C 0 = 0, where C i F p 3[u, v] g(x) = 0 P 1, P 2, P 3 X F p 3/F p 1, t, t 2 u = u 0 + u 1 t + u 2 t 2 v = v 0 + v 1 t + v 2 t 2 : u i, v i 16
Nagao 4 g(x) := X 3 + C 2 X 2 + C 1 X + C 0 C i,j F p [u 0,..., v 2 ], i.e. C 0 = C 0,0 + C 0,1 t + C 0,2 t 2 C 1 = C 1,0 + C 1,1 t + C 1,2 t 2 C 2 = C 2,0 + C 2,1 t + C 2,2 t 2 P 1, P 2, P 3 B 0 g(x) F p [X] g(x) = X 3 + C 2,0 X 2 + C 1,0 X + C 0,0 C 0,1 = 0,..., C 2,2 = 0 17
Nagao Relation Step1 : C 0,1 = 0, C 0,2 = 0, C 1,1 = 0, C 1,2 = 0, C 2,1 = 0, C 2,2 = 0 Step2 : Gröbner u 0,..., v 2 F p C 0,0, C 1,0, C 2,0 F p Step3 : g(x) = X 3 + C 2,0 X 2 + C 1,0 X + C 0,0 g(x) = (X x 1 )(X x 2 )(X x 3 ) = 0 s.t. x i F p P i = (x i, y i ) B 0 18
Gaudry Gaudry Nagao 3 3 6 3 3 6 12 4 2 125,124,124 35,33,33 21,21,15,15,5,5 Gröbner 19
Relation collection Relation collection OS:Linux version 2.6.13 CPU:AMD Athlon 64 X2, 2.4GHz 4GB MAGMA V2.14-5 20
Gaudry, Nagao p 3 42-160bit relation 1000
Relation 1 Gaudry log p 3 Gröbner 64 (bit) 0.751 (sec) 0.101 (sec) 0.856 (sec) 96 (bit) 1.339 (sec) 0.355 (sec) 1.714 (sec) 128 (bit) 1.299 (sec) 0.365 (sec) 1.690 (sec) 160 (bit) 1.279 (sec) 0.407 (sec) 1.703 (sec) Nagao log p 3 Gröbner 64 (bit) 0.011 (sec) 0.188 (sec) 0.201 (sec) 96 (bit) 0.015 (sec) 0.972 (sec) 0.994 (sec) 128 (bit) 0.014 (sec) 1.036 (sec) 1.058 (sec) 160 (bit) 0.013 (sec) 1.106 (sec) 1.128 (sec) 21
Index calculus(plain version) Relation collection part : p relation Gaudry, Nagao relation p Gaudry p 3 20-50bit relation 100 relation p 22
Relation collection 2 100 2 90 Gaudry s algorithm Gaudry s algorithm (with symmetry) Nagao s algorithm 2 80 2 70 2 60 Time(sec) 2 50 2 40 2 30 2 20 2 10 2 0 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 log 2 p 3 (bit) 23
Index calculus Gaudry (Gaudry) : Plain version O(p 2 ) Plain version Gaudry-Harley (Gaudry-Harley) O(p 3 2) Single-large-prime version (Thériault) Double-large-prime version (Nagao,Gaudry-Thomé-Thériault-Diem) O(p 4 3) < Rho O(p 3 2) 24
Index calculus (plain version) B 0 s.t. #B 0 p Relation collection part O(p) Linear algebra part O(p 2 ) O(p 2 ) : Rho 25
Index calculus (plain version) Index calculus p 3 20-53bit (Relation collection by Nagao ) 53bit 26
Index calculus (plain version) 2 260 2 240 2 220 Relation collection part Linear algebra part Rho method 2 200 2 180 2 160 Time(sec) 2 140 2 120 2 100 2 80 2 60 2 40 2 20 2 0 20 40 60 80 100 120 140 160 180 200 220 240 260 280 300 log 2 p 3 (bit) 27
Index calculus (double-large-prime version) : B B 0 s.t. #B p 2 3 Relation collection part O(p 4 3) Linear algebra part O(p 4 3) O(p 4 3) < Rho O(p 3 2) 28
Double-large-prime version Double-large-prime version p 3 20-35bit (Relation collection by Nagao ) double-large-prime version 29
Double-large-prime-version 2 140 2 120 Relation collection part Linear algebra part Rho method 2 100 2 80 Time(sec) 2 60 2 40 2 20 2 0 20 40 60 80 100 120 140 160 180 200 220 240 260 log 2 p 3 (bit) 30
4 Relation collection Relation 1 64(bit) : 59808 (sec) 96(bit) : 194352 (sec) Time(sec) 2 220 2 210 2 200 2 190 2 180 2 170 2 160 2 150 2 140 2 130 2 120 2 110 2 100 2 90 2 80 2 70 2 60 2 50 2 40 2 30 2 20 2 10 2 0 ext.deg = 4 ext.deg = 3 Rho method 60 80 100 120 140 160 180 200 220 240 260 280 300 320 340 360 380 400 log 2 #E(F p n) (bit) p 3 : p 4 3, p 4 : p 3 2 relation 31
Relation collection Gaudry Nagao Index calculus Plain version Double-large-prime version Generalized Weil descent 3 32