index calculus

Size: px

Start display at page:

Download "index calculus"

なごみおうじ
4 years ago
Views:

1 index calculus

2 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

3 Index calculus Plain version Double-large-prime version Relation collection Gaudry Nagao 3

4 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

5 Generalized Weil descent Step1 : Relation collection part Relation Gröbner Step2 : Linear algebra part relation 5

6 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

7 Relation collection Gaudry Semaev summation polynomials Gröbner Nagao Gaudry Gröbner 7

8 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 P m = 0 E(F p 3) 8

9 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

10 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

11 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

12 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

13 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

14 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

15 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

16 (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

17 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

18 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

19 Gaudry Gaudry Nagao ,124,124 35,33,33 21,21,15,15,5,5 Gröbner 19

20 Relation collection Relation collection OS:Linux version CPU:AMD Athlon 64 X2, 2.4GHz 4GB MAGMA V

21 Gaudry, Nagao p bit relation 1000

22 Relation 1 Gaudry log p 3 Gröbner 64 (bit) (sec) (sec) (sec) 96 (bit) (sec) (sec) (sec) 128 (bit) (sec) (sec) (sec) 160 (bit) (sec) (sec) (sec) Nagao log p 3 Gröbner 64 (bit) (sec) (sec) (sec) 96 (bit) (sec) (sec) (sec) 128 (bit) (sec) (sec) (sec) 160 (bit) (sec) (sec) (sec) 21

23 Index calculus(plain version) Relation collection part : p relation Gaudry, Nagao relation p Gaudry p bit relation 100 relation p 22

24 Relation collection Gaudry s algorithm Gaudry s algorithm (with symmetry) Nagao s algorithm Time(sec) log 2 p 3 (bit) 23

25 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

26 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

27 Index calculus (plain version) Index calculus p bit (Relation collection by Nagao ) 53bit 26

28 Index calculus (plain version) Relation collection part Linear algebra part Rho method Time(sec) log 2 p 3 (bit) 27

29 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

30 Double-large-prime version Double-large-prime version p bit (Relation collection by Nagao ) double-large-prime version 29

31 Double-large-prime-version Relation collection part Linear algebra part Rho method Time(sec) log 2 p 3 (bit) 30

32 4 Relation collection Relation 1 64(bit) : (sec) 96(bit) : (sec) Time(sec) ext.deg = 4 ext.deg = 3 Rho method log 2 #E(F p n) (bit) p 3 : p 4 3, p 4 : p 3 2 relation 31

33 Relation collection Gaudry Nagao Index calculus Plain version Double-large-prime version Generalized Weil descent 3 32

:00-16:10

3 3 2007 8 10 13:00-16:10 2 Diffie-Hellman (1976) K K p:, b [1, p 1] Given: p: prime, b [1, p 1], s.t. {b i i [0, p 2]} = {1,..., p 1} a {b i i [0, p 2]} Find: x [0, p 2] s.t. a b x mod p Ind b a := x