Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v11(1-4)/levin-171-184.pdf Дата изменения: Mon Feb 18 14:01:56 2008 Дата индексирования: Mon Oct 1 23:43:07 2012 Кодировка:

. .

, . . . , , . (N. Koblitz) 1985 [1]. . , , .

K , F q , q = pn , p , n N. 1. ( ) char K = 2, 3 x3 + ax + b (a, b K ). K (E (K )) (x, y ) x, y K , y 2 = x3 + ax + b (1) O . : E (K ) = (x, y ) K в K : y 2 = x3 + ax + b, a, b K {O } .


172

. .

A = {a 0 , a2 , . . . , aM -1 }. a m A m. A, m [0, . . . , M - 1] E (K ): A = {a0 , a2 , . . . , a
M -1

} {0, . . . , M - 1}

{P0 (x, y ), . . . , P

M -1

(x, y )} E (K ).

, , , , . (. [1]), . (. [1, 2]). , , . , . . K ( . [1, 2]). P = (x1 , y1 ) E (K ), -P = (x1 , -y1 ). Q = (x2 , y2 ) E (K ) Q = -P , P + Q = (x3 , y3 ), y3 = (x1 - x3 ) - y1 ; y -y 1 2 , P = Q, x2 - x 1 = 3x2 + a 1 , P = Q. 2y1 x3 = 2 - x 1 - x 2 ;




173

1. {E (Fq ), +} . 2 (). #E (K ) (1), K , char K = 2, 3. |#E (K ) - (1 + p)| 2 p. [3]. . 2. : E
ab

: y 2 = x3 + ax + b E

ab

: y 2 = x3 + a x + b ,

K , char K = 2, 3, a, b, a , b K (twists), : a = v 2 a, b = v 3 b, v K p.

#E (K ) E (K ).

3. Eab (Fp ), Ea b (Fp ) Fp , p = 2, 3. #Eab (Fp ) + #E
ab

(Fp ) = 2p + 2.

. Fp : Eab (Fp ) : y 2 = g (x), g (x) = x3 + ax + b, E 1. gv (x) = v 3 g
ab

(Fp ) : y 2 = gv (x), gv (x) = x3 + a x + b . x . v


174 .

. .

gv (x) = x3 + a x + b = x3 + v 2 ax + v 3 b = v

3

x v

3

+a

x x + b = v3g . v v

. (1), . [4, 5] #E (Fp ) = 1 +
x (mo d p)

x3 + Ax + B p

+1 .

, #Eab (Fp ) = 1 +
x (mo d p)

g (x) p gv (x) p

+1 , +1 .

(2) (3)

#E

ab

(Fp ) = 1 +
x (mo d p)

: x F p x gv (x) = 0, g = 0, v x gv (x) = v 3 g . (2), v (3). , g v (x) p. v p, v 3 , : v3 p = v2 p v p = (1)(-1) = -1.
-1

, l , l , ll -1 1 (mo d p), ll-1 p = l p l
-1

. -

p

= (-1)(s) = 1 s = -1.




175

, , , g

x x gv (x) = , g . 3 v v v (3) (2). x , gv (x) , g v , (2) (3). Fp , #Eab + #Ea b = 2p + 2. . 1. 3 F5 :
E E E E E E E E E E E E E E E E E E E E E E E
01 02 03 04 10 11 12 13 14 20 21 22 23 24 30 31 33 34 40 41 42 43 44

1 v3

. -

: : : : : : : : : : : : : : : : : : : : : : :

y y y y y y y y y y y y y y y y y y y y y y y

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

= = = = = = = = = = = = = = = = = = = = = = =

x x x x x x x x x x x x x x x x x x x x x x x

3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

+ + + + + + + + + + + + + + + + + + + + + + +

0x 0x 0x 0x 1x 1x 1x 1x 1x 2x 2x 2x 2x 2x 3x 3x 3x 3x 4x 4x 4x 4x 4x

+ + + + + + + + + + + + + + + + + + + + + + +

1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 3 4 0 1 2 3 4

#E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E

01 02 03 04 10 11 12 13 14 20 21 22 23 24 30 31 33 34 40 41 42 43 44

= = = = = = = = = = = = = = = = = = = = = = =

6 6 6 6 4 9 4 4 9 2 7 7 7 7 10 5 5 5 8 8 3 3 8



E E E E E E E E E E E E E E E E E E E E E E E

03 01 04 02 40 43 41 44 42 30 33 31 34 32 20 23 24 22 10 13 11 14 12

: : : : : : : : : : : : : : : : : : : : : : :

y y y y y y y y y y y y y y y y y y y y y y y

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

= = = = = = = = = = = = = = = = = = = = = = =

x x x x x x x x x x x x x x x x x x x x x x x

3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

+ + + + + + + + + + + + + + + + + + + + + + +

0x 0x 0x 0x 4x 4x 4x 4x 4x 3x 3x 3x 3x 3x 2x 2x 2x 2x 1x 1x 1x 1x 1x

+ + + + + + + + + + + + + + + + + + + + + + +

3 1 4 2 0 3 1 4 2 0 3 1 4 2 0 3 4 2 0 3 1 4 2

#E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E #E

03 01 04 02 40 43 41 44 42 30 33 31 34 32 20 23 24 22 10 13 11 14 12

= = = = = = = = = = = = = = = = = = = = = = =

6, 6, 6, 6, 8, 3, 8, 8, 3, 10, 5, 5, 5, 5, 2, 7, 7, 7, 4, 4, 9, 9, 4.

4. n [2 p] , E (Fp ) (1) F p , p = 2, 3, #E (Fp ) = p + 1 - n.


176

. .

#Ev (Fp ) = Ev (Fp )

p + 1 + n, p + 1 - n,

v v

; ,

(1), a = v 2 a, b = v 3 b.

. . v . E (F p ) Ev (Fp ) . , , #E (F p ) + #Ev (Fp ) = 2p + 2, , #Ev (Fp ) = 2p + 2 - p - 1 + n = p + 1 + n. v , , , x , g v (x) , g v , . Fp #E (Fp ) = #Ev (Fp ) = p + 1 - n. . 5. n [2 p] . (1) F p , p = 2, 3, p + 1 - n (1) , p + 1 + n . . , E
ab

E

ab

, (1) . . E a1 b1 , Ea2 b2 , a1 , b1 , a2 , b2 Fp ,




177

b1 = b2 , a1 a2 p a = v 2 a, b = v3 b Ea b . , , a 1 v 2 a2 v 2 (mo d p), a1 a2 (mo d p). , a1 a2 p ( ). . . , , , p , p + 2 ; p - 1 , p + 3 , . , .


. 1985 () . . A = {a0 , a2 , . . . , aM -1 }. . A m. m Pm (x, y ) (1). A . , , Pm (x, y ) m . ( ). , -


178

. .

ECC (Elliptic Curve Cryptology)-. , . E (Fq ), Fq . q = pr . , q q > M , . , , () 1 . . , = 20 2 = 50. 1 M m + j , 1 j , F q . , r - p- , Z F p = pZ r - 1 F p , Fq :
r -1

(a

r -1 r -2

a

. . . a 1 a0 )p

ai xi .
i=0

m j = 1, 2 . . . x Fq , m + j . x y 2 = f (x) = x3 + ax + b f (x). y : y 2 = f (x), Pm = (x, y ); y , j 1 x. x , f (x) , j , m m= x ~ x-j ~ ,

, x Z F q , 1 , x 1 - . 2




179

, x, y , r - 1. , , [1, . 5,§2].

Fp
, . A = {a0 , a2 , . . . , aM -1 }, . , , , m [0, . . . , M - 1] . , Fp : p M , E (Fp ). 1 M m + j j [1, . . . , ]. f (m + j ) , 1, p Pm (m + j, y ). y Ї Ї , y 2 f (m + j ) (mo d p). Ї -1, j 1 . 1 - . 2 :
1 2 3 . . . m m + j f (m + j ) . . . M f (m + j ) p j j + 1 = 1 Pm (m + j, y ) Ї


180

. .

m [1, . . . , M ] . . 2. veni vidi vici F 6421 y 2 = x3 + 123x + 3456. ASCI I ( 0 255). , = 25.
veni vidi vici (2951,6054)(2527,4044)(2752,140)(2625,1007)(801,4067)(2951,6054)(2625,1007) (2500,4398)(2625,1007)(801,4067)(2951,6054)(2625,1007)(2476,2074)(2625,1007)

, , , P m (x, y ), m.

( Pm (x, y ) m). x - x (mo d ) j = , m = x- j = .


. [6]. m [0, . . . , M - 1], vK Eab Ea b m [0, . . . , M - 1] [0, . . . , 2M - 2]. M , K, E (K ), Pm (x, y ) E (K ), Ev (K ) .



v K , : K . . :




181

g (x) = x3 + ax + b, gv (x) = x3 + a x + b Eab Ea b . , 0 2M - 2 g (m) . , g (m) , gv (mv ) , , g (m) , gv (mv ) . P m (x, y ) m. , g (m) gv (mv ) / , + , g (m) gv (mv ) , - . Eab : m [0, . . . , 2M - 2] y = x3 + ax + b
2

mv 0 v 2v 3v 4v 5v 6v 7v . . . . (2M-2)v

Ea b : y = x3 + a x + b
2

0 1 2 3 4 5 6 7 . . . . 2M-2

+ + - - + - + - - - - - +

2M - 2, M , , . , A. , ( m ( a m A) Pm , ).

- - + + - + - + + + + + -


182

. .

. , . 3. F751 , M = 7. m [0, . . . , M ] : 0 < m < 2M 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 y 2 = x3 + 748x + 749 - - + + + - + + - - + + + - mv 0 v 2v 3v 4v 5v 6v 7v 8v 9v 10v 11v 12v 13v y 2 = x3 + 724x + 697 + + - - - + - - + + - - - +

: 2 (2, 0), 3 (3, 4), 4 (4, 186), 6 (6, 14), 7 (7, 364), 10 (10, 233), 11 (11, 36),


· , .




183

, . · , , - . · , Fp , Fpn . . . . . .


[1] . . .: , 2001. [2] Blake I. F., Serroussi G., Smart N. P. Elliptic curves in cryptography. 1999. [3] . / . . . . , . . . . .: , 2004. [4] Koblitz Neal, Menezis Alfred, Vanstone Scott. The State of Elliptic Curve Cryptography. 2000. [5] Scho of Rene. Counting p oints on elliptic curves over finite fields. 1995. [6] . . / . 2007.