I HÅC QUÈC GIA H NËI
TR×ÍNG I HÅC KHOA HÅC TÜ NHIN
VÃ TÒNG LINH
V DNG CHUN EDWARDS
V MËT VI ÙNG DÖNG
LUN VN THC S TON HÅC
H NËI - 2014
I HÅC QUÈC GIA H NËI
TR×ÍNG I HÅC KHOA HÅC TÜ NHIN
VÃ TÒNG LINH
V DNG CHUN EDWARDS
V MËT VI ÙNG DÖNG
Chuy¶n ng nh: I SÈ V LÞ THUYT SÈ
M¢ sè: 60460104
LUN VN THC S TON HÅC
Ng÷íi h÷îng d¨n khoa håc:
TS. Phâ ùc T i
H NËI - 2014
Möc löc
Líi c£m ìn
Líi mð ¦u
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1 Ki¸n thùc chu©n bà
6
1.1
Lþ thuy¸t chung v· ÷íng cong elliptic
. . . . . . . . . . . . . .
1.2
D¤ng Montgomery cõa ÷íng cong elliptic
. . . . . . . . . . . .
2 D¤ng chu©n Edwards cho ÷íng cong elliptic
2.1
2.2
6
12
15
D¤ng chu©n Edwards . . . . . . . . . . . . . . . . . . . . . . . .
15
2.1.1
D¤ng chu©n Edwards . . . . . . . . . . . . . . . . . . . .
15
2.1.2
Hai cæng thùc cëng iºm tr¶n ÷íng cong Edwards
. . .
20
. . . . . . . . .
27
Nhâm c¡c iºm tr¶n ÷íng cong Edwards cuën
3 Mët sè ùng döng cõa ÷íng cong d¤ng chu©n Edwards
3.1
C¡c iºm câ c§p nhä tr¶n ÷íng cong Edwards cuën
3.2
Nhâm xon cõa ÷íng cong Edwards tr¶n
3.3
41
. . . . . .
41
. . . . . . . . . . .
46
Ùng döng cõa ÷íng cong Edwards trong mªt m¢ . . . . . . . .
58
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
. . . . . . . . . . . . . . . . . . . . . . . . . . .
62
K¸t luªn
T i li»u tham kh£o
1
Q
Líi c£m ìn
B£n luªn v«n n y ÷ñc ho n th nh d÷îi sü h÷îng d¨n v ch¿ b£o tªn t¼nh cõa
Th¦y gi¡o, Ti¸n s¾ Phâ ùc T i, Gi£ng vi¶n Khoa To¡n-Cì-Tin håc, Tr÷íng
¤i håc Khoa håc Tü nhi¶n, ¤i håc Quèc gia H nëi. Th¦y ¢ gi nh nhi·u
thíi gian h÷îng d¨n, trao êi v gi£i ¡p nhúng thc mc cõa tæi trong suèt
qu¡ tr¼nh l m luªn v«n. Qua luªn v«n n y, tæi muèn b y tä láng bi¸t ìn s¥u
sc ¸n Th¦y gi¡o cõa m¼nh.
Tæi xin gûi líi c£m ìn s¥u sc ¸n c¡c L¢nh ¤o Vi»n Khoa håc - Cæng ngh»
Mªt m¢, Ban Cì Y¸u Ch½nh Phõ, L¢nh ¤o Ph¥n vi»n Nghi¶n cùu Khoa håc
Mªt m¢ v t§t c£ c¡c Cæ, Chó v Anh, Chà, Em çng nghi»p trong ìn và ¢
t¤o i·u ki»n tèi a công nh÷ ¢ âng gâp nhúng þ ki¸n quþ b¡u gióp tæi ho n
th nh luªn v«n n y.
Tæi công xin gûi líi c£m ìn s¥u sc tîi PGS.TS. L¶ Minh H v c¡c Th¦y,
Cæ trong Khoa To¡n-Cì-Tin håc, Tr÷íng ¤i håc Khoa håc Tü Nhi¶n, ¤i håc
Quèc Gia H nëi, công nh÷ t§t c£ nhúng Th¦y, Cæ ¢ tham gia gi£ng d¤y khâa
Cao håc 2011-2013. N¸u khæng câ nhúng líi ëng vi¶n, h÷îng d¨n v cæng lao
d¤y dé cõa c¡c Th¦y, Cæ th¼ tæi công khæng ho n th nh ÷ñc luªn v«n n y.
Líi cuèi còng, tæi muèn gûi líi c£m ìn s¥u sc ¸n Bè, Mµ v gia ¼nh tæi,
nhúng ng÷íi ¢ tin t÷ðng s¥u sc, ¢ luæn cê vô ëng vi¶n v chia s´ måi khâ
kh«n gióp tæi ho n th nh luªn v«n n y. Tæi công xin c£m ìn t§t c£ nhúng anh
em b¤n b± luæn b¶n c¤nh tæi trong trong suèt khâa håc n y.
Tæi xin ch¥n th nh c£m ìn t§t c£!
H Nëi, th¡ng 12 n«m 2014
Håc vi¶n
Vã Tòng Linh
2
Líi mð ¦u
Trong nhúng n«m 80 cõa th¸ k¿ tr÷îc, Neal Kobliz v Victor Miller ¢ ëc
lªp · xu§t vi»c sû döng ÷íng cong elliptic cho c¡c h» mªt m¢ khâa cæng
khai. Tø â ¸n nay h» mªt ÷íng cong elliptic ¢ ÷ñc nghi¶n cùu s¥u rëng
v trð n¶n phê bi¸n còng vîi c¡c h» mªt m¢ khâa cæng khai kh¡c, ch¯ng h¤n
nh÷ RSA, Diffie Hellman v ElGamal. Do ÷u th¸ l câ cï cõa c¡c tham bi¸n
nhä hìn so vîi c¡c h» mªt m¢ khâa cæng khai kh¡c khi x²t ð còng mët mùc an
to n n¶n h» mªt ÷íng cong elliptic l r§t h§p d¨n èi vîi c¡c ùng döng m
câ t i nguy¶n h¤n ch¸.
V o n«m 2007, Harold Edwards trong [7] ¢ · xu§t mët d¤ng chu©n tc
mîi cho c¡c ÷íng cong elliptic. B¬ng vi»c têng qu¡t hâa mët v½ dö bt nguçn
tø Euler v Gauss, Edwards ¢ giîi thi»u mët ph²p cëng iºm tr¶n ÷íng cong
x2 + y 2 = c2 (1 + x2 y 2 )
tr¶n mët tr÷íng
k
câ °c sè kh¡c 2. M°c dò b i b¡o
cõa H. Edwards khæng tªp trung v o vi»c ¡p döng d¤ng ÷íng cong n y trong
mªt m¢, nh÷ng d¦n d¦n, vîi nhúng nghi¶n cùu sau â, d¤ng chu©n tc n y
¢ thº hi»n c¡c t½nh ch§t mªt m¢ ¡ng mong muèn v húu ½ch trong né lüc
tr¡nh º lë thæng tin. Ti¸p sau Edwards, Bernstein, Lang, Birker v c¡c cëng
sü trong [1, 2, 4, 5] ¢ têng qu¡t hâa nghi¶n cùu cõa Edwards cho mët lîp
÷íng cong rëng hìn
ax2 + y 2 = 1 + dx2 y 2
vîi
a 6= d, a, d ∈ k \ {0, 1}.
Nhúng
t¡c gi£ n y ¢ k¸t hñp þ t÷ðng x¥y düng ph²p cëng iºm cõa Edwards v ph²p
cëng iºm èi ng¨u do Hisil, Wong, Carter v Dawson · xu§t trong [9] º
÷a ra mët cæng thùc duy nh§t cho c£ vi»c cëng iºm l¨n nh¥n æi iºm. ¥y
l mët ph¡t triºn quan trång bði khæng ch¿ mang l¤i cho nhâm iºm tr¶n c¡c
÷íng cong Edwards cuën nâi chung v c¡c ÷íng cong Edwards nâi ri¶ng mët
3
Líi mð ¦u
4
c§u tróc nhâm, m cæng thùc cëng iºm duy nh§t n y l cì sð n·n t£ng vúng
chc cho vi»c sû döng d¤ng chu©n Edwards trong mªt m¢ nh¬m chèng l¤i c¡c
t§n cæng k¶nh k·. Hìn núa, trong nhi·u tr÷íng hñp, ph²p cëng iºm do c¡c
t¡c gi£ tr¶n ÷a ra câ sè l÷ñng nhúng t½nh to¡n cì b£n (ph²p nh¥n v ph²p
cëng trong tr÷íng cì sð) ½t hìn, d¨n ¸n vi»c t½nh to¡n trong thüc t¸ s³ nhanh
hìn so vîi d¤ng chu©n Weierstrass. çng thíi c¡c t¡c gi£ công x¥y düng t÷íng
minh lîp c¡c ÷íng cong Edwards, v do â l lîp c¡c ÷íng cong elliptic d¤ng
Weierstrass tr¶n tr÷íng
Q
vîi nhâm xon cho tr÷îc.
Trong luªn v«n n y, chóng tæi tr¼nh b y l¤i ành ngh¾a ÷íng cong Edwards
v ÷íng cong Edwards cuën theo nghi¶n cùu cõa Berstein v c¡c cëng sü.
Chóng tæi công i v o chi ti¸t vi»c x¥y düng ph²p cëng iºm tr¶n c¡c d¤ng
÷íng cong n y, v tø §y i t½nh c¡c nhâm xon câ thº câ cõa chóng tr¶n
tr֒ng
Q.
Bè cöc cõa luªn v«n gçm câ ba ch÷ìng:
Ch÷ìng 1: Ki¸n thùc chu©n bà.
Trong ch÷ìng n y, chóng tæi tr¼nh b y mët sè ki¸n thùc chu©n bà v· lþ thuy¸t
÷íng cong elliptic têng qu¡t bao gçm c¡c ành ngh¾a, k¸t qu£ cì b£n, vi»c x¥y
düng ph²p cëng iºm tr¶n ÷íng cong elliptic. çng thíi chóng tæi công tr¼nh
b y v· d¤ng Montgomery cõa ÷íng cong elliptic v vi»c bi¸n êi qua l¤i giúa
d¤ng Montgomery v d¤ng Weierstrass.
Ch÷ìng 2: D¤ng chu©n Edwards cho ÷íng cong elliptic.
Ch÷ìng n y gçm hai ph¦n. Ph¦n mët tr¼nh b y v· d¤ng chu©n Edwards v
d¤ng têng qu¡t hìn l c¡c ÷íng cong Edwards cuën. Chóng tæi công tr¼nh
b y mèi quan h» t÷ìng ÷ìng song húu t¿ giúa mët ÷íng cong Edwards cuën
(tr÷íng hñp ri¶ng l ÷íng cong Edwards) vîi ÷íng cong d¤ng Weierstrass
nâi chung v ÷íng cong d¤ng Montgomery nâi ri¶ng. Trong ph¦n n y chóng
tæi công tr¼nh b y chi ti¸t hai cæng thùc cëng iºm tr¶n ÷íng cong Edwards
v ch¿ ra nh÷ñc iºm cõa hai cæng thùc n y. Ph¦n hai tr¼nh b y v· cæng thùc
cëng iºm ¦y õ v duy nh§t tr¶n ÷íng cong Edwards cuën vîi c¡c iºm
÷ñc biºu di¹n ð d¤ng x¤ £nh trong
P1 × P1 .
T½nh óng n cõa ph²p cëng
iºm n y ÷ñc chùng minh qua c¡c ành lþ 2.15, 2.16, 2.17, 2.19. Tø â rót ra
Líi mð ¦u
5
h» qu£ quan trång l tªp c¡c iºm tr¶n ÷íng cong Edwards cuën (÷íng cong
Edwards) l mët nhâm aben, hìn núa nhâm n y ¯ng c§u vîi nhâm iºm tr¶n
÷íng cong ellptic d¤ng Montgomery t÷ìng ùng.
Ch÷ìng 3: Mët sè ùng döng cõa ÷íng cong d¤ng chu©n Edwards.
Ch÷ìng n y gçm ba ph¦n. Ph¦n mët chóng tæi t½nh c¡c iºm câ c§p nhä, cö
thº l c¡c iºm c§p 2, 3, 4, 8 tr¶n ÷íng cong Edwards cuën. Ph¦n hai chóng
tæi tr¼nh b y i·u ki»n cõa tham sè
d
º ÷íng cong Edwards tr¶n
Q
câ nhâm
xon ¢ cho tr÷îc. Tø â, nh÷ mët h» qu£, chóng tæi x¥y düng mët lîp c¡c
÷íng cong elliptic d¤ng Weierstrass vîi nhâm xon ¢ cho thº hi»n qua H»
qu£ 3.12. Cuèi còng, trong ph¦n ba chóng tæi ÷a ra mët v i nhªn x²t v· kh£
n«ng ùng döng ÷íng cong Edwards trong mªt m¢. T§t c£ t½nh to¡n trong
luªn v«n chóng tæi ÷ñc thüc hi»n vîi ph¦n m·m Sage [16].
H Nëi, th¡ng 12 n«m 2014
Håc vi¶n
Vã Tòng Linh
Ch֓ng 1
Ki¸n thùc chu©n bà
Trong ch÷ìng n y, chóng tæi tr¼nh b y mët sè ki¸n thùc v· lþ thuy¸t ÷íng
cong elliptic têng qu¡t. Ngo i ra, chóng tæi công tr¼nh b y v· d¤ng Montgomery
cõa ÷íng cong elliptic. Nhúng k¸t qu£ ch½nh ÷ñc l§y tø c¡c t i li»u [8, 15,
14, 13]
1.1 Lþ thuy¸t chung v· ÷íng cong elliptic
Cho
K
l mët tr÷íng câ °c sè tòy þ.
ành ngh¾a 1.1.
Mët
[8, ành ngh¾a 3.1]
÷íng cong elliptic E tr¶n tr÷íng K ÷ñc ành ngh¾a bði ph÷ìng tr¼nh
E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,
vîi
a1 , a2 , a3 , a4 , a6 ∈ K
v
∆ 6= 0,
trong â
∆
l
bi»t thùc
(1.1)
cõa
E
÷ñc ành
ngh¾a nh÷ sau:
∆ = −d22 d8 − 8d34 − 27d26 + 9d2 d4 d6
2
d2 = a1 + 4a2
d4 = 2a4 + a1 a3
d6 = a23 + 4a6
d8 = a2 a6 + 4a2 a6 − a1 a3 a4 + a2 a2 − a2 .
3
4
1
N¸u
L
l mët tr÷íng mð rëng cõa
K
th¼ tªp c¡c iºm
L − húu
t¿ tr¶n E l
E(L) = {(x, y) ∈ L × L : y 2 + a1 xy + a3 y − x3 − a2 x2 − a4 x − a6 = 0} ∪ {∞}
6
Ch÷ìng 1. Ki¸n thùc chu©n bà
∞
trong â
l
7
iºm t¤i væ h¤n.
V½ dö 1.2.
H¼nh 1.1: y 2 = x3 − x
Cho
E
H¼nh 1.2: y 2 = x3 + x
l mët ÷íng cong elliptic tr¶n tr÷íng
K
câ ph÷ìng tr¼nh x¡c ành
vi¸t d÷îi d¤ng affine
E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 .
Khi â ph÷ìng tr¼nh x¤ £nh cõa
E
s³ l
Ē : y 2 z + a1 xyz + a3 yz 2 = x3 + a2 x2 z + a4 xz 2 + a6 z 3 ,
v iºm
P
n¸u iºm
tr¶n
P
z 6= 0
z=0
s³ câ tåa ë vi¸t d÷îi d¤ng x¤ £nh l
câ tåa ë vi¸t d÷îi d¤ng affine l
cõa nâ s³ l
vîi
E
(x : y : 1).
P
Ng÷ñc l¤i, n¸u iºm
ch½nh l iºm
∞,
D¹ th§y,
(x, y) th¼ d¤ng x¤ £nh t÷ìng ùng
P
th¼ d¤ng affine t÷ìng ùng cõa nâ s³ l
th¼ iºm
(x : y : z).
câ tåa ë x¤ £nh
(x/z, y/z).
(x : y : z)
Trong tr÷íng hñp
v ta câ d¤ng x¤ £nh cõa iºm væ còng l
P = (0 : y : 0) = (0 : 1 : 0).
Ta câ mët sè chó þ v· ành ngh¾a 1.1.
Chó þ 1.3.
Ph÷ìng tr¼nh Weierstrass têng
qu¡t, hay º ìn gi£n, ta gåi l Ph÷ìng tr¼nh Weierstrass.
1. Ph÷ìng tr¼nh (1.1) ÷ñc gåi l
Ch÷ìng 1. Ki¸n thùc chu©n bà
2. Ta nâi
E
֖c
8
ành ngh¾a tr¶n
ph÷ìng tr¼nh ành ngh¾a cõa
E
K
ành ngh¾a tr¶n
th¼
E
E
K
bði v¼ c¡c h» sè
a1 , a2 , a3 , a4 , a6
l c¡c ph¦n tû thuëc
K.
trong
Rã r ng l n¸u
công ành ngh¾a tr¶n mët tr÷íng mð rëng tòy
K.
þ cõa
3. i·u ki»n
∆ 6= 0
£m b£o ÷íng cong elliptic
ngh¾a l khæng tçn t¤i iºm n o tr¶n
E
E
l trìn, i·u n y câ
m t¤i â ÷íng cong câ nhi·u
hìn mët ÷íng th¯ng ti¸p tuy¸n.
4. iºm
∞ l iºm duy nh§t tr¶n ÷íng th¯ng t¤i væ h¤n m thäa m¢n d¤ng
x¤ £nh cõa ph÷ìng tr¼nh Weierstrass.
5. C¡c iºm
L − húu
t¿ tr¶n
E
l c¡c iºm
÷íng cong v câ c¡c tåa ë
mët iºm
L − húu
ành ngh¾a 1.4.
x, y
thuëc
(x, y) thäa m¢n ph÷ìng tr¼nh cõa
L.
iºm t¤i væ h¤n ÷ñc xem l
t¿ èi vîi måi tr÷íng mð rëng
Hai ֒ng cong elliptic
E1
v
E2
L
cõa
K.
ành ngh¾a tr¶n
K
v ֖c
cho bði c¡c ph÷ìng tr¼nh Weierstrass
E1 : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6
E2 : y 2 + ā1 xy + ā3 y = x3 + ā2 x2 + ā4 x + ā6
÷ñc nâi l
¯ng c§u tr¶n K n¸u tçn t¤i u, r, s, t ∈ K, u 6= 0 sao cho ph²p êi
bi¸n
(x, y) 7→ (u2 x + r, u3 y + u2 sx + t)
bi¸n êi ph÷ìng tr¼nh
E1
th nh ph÷ìng tr¼nh
(1.2)
E2 .
B¥y gií, gi£ sû ta câ ph÷ìng tr¼nh Weierstrass
E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6
x¡c ành tr¶n
K
vîi char(K)
6= 2, 3.
Khi §y ta câ thº thüc hi»n ph²p êi bi¸n
nh÷ sau: Ta vi¸t ph÷ìng tr¼nh (1.1) th nh
2
2
2
a
a
a
a1 x a3
a
1
3
3
+
= x3 + a2 + 1 x2 + a4 +
x+
+ a6 .
y+
2
2
4
2
4
Ch÷ìng 1. Ki¸n thùc chu©n bà
°t
9
y1 = y + a21 x +
a0 = a + a21 ,
2
2
4
a1 a3
0
a4 = a4 + 2 ,
a0 = a23 + a ,
6
6
4
a3
,
2
ta nhªn ÷ñc ph÷ìng tr¼nh mîi câ d¤ng
y12 = x3 + a02 x2 + a04 x + a06 .
Ta vi¸t l¤i ph÷ìng tr¼nh vøa nhªn ÷ñc th nh
3
02
03
0
a
a
a
2
2
2
+ a04 −
x + a06 −
.
y12 = x +
3
3
27
°t
a02
,
x
=
x
+
1
3
02
a = a04 − a3 ,
b = a0 − a032 ,
6
27
ta ÷ñc ph÷ìng tr¼nh
y12 = x31 + ax + b.
Khi â ta t½nh ÷ñc bi»t thùc cõa ÷íng cong
tr¼nh (1.3) ÷ñc gåi l
Weierstrass ngn.
(1.3)
∆ = −16(4a3 + 27b2 ).
Ph֓ng
Ph÷ìng tr¼nh Weierstrass thu gån, hay l Ph÷ìng tr¼nh
º cho tªp c¡c iºm tr¶n
E
vîi tåa ë trong
K,
kþ hi»u
E(K),
câ mët c§u
tróc nhâm, ta i x¥y düng ph²p cëng iºm (cán ÷ñc gåi l Luªt nhâm) tr¶n
÷íng cong elliptic theo ph÷ìng ph¡p ÷ñc gåi l
ti¸p tuy¸n-v -d¥y cung
v
÷ñc minh håa qua c¡c h¼nh v³ d÷îi ¥y (xem [15]):
Gi£ sû
elliptic
E.
P = (x1 , y1 )
Khi â
têng
v³ ÷íng th¯ng qua
thù ba, gåi l iºm
R.
Khi â
R
v
P
R0 .
Q = (x2 , y2 )
cõa
v
Q;
P
v
Q
l hai iºm ph¥n bi»t tr¶n ÷íng cong
÷ñc ành ngh¾a nh÷ sau: Tr÷îc ti¶n, ta
÷íng th¯ng n y giao vîi ÷íng cong
L§y èi xùng iºm
R0
÷ñc gåi l têng cõa hai iºm
º ành ngh¾a
2P = P + P ,
P
qua tröc tåa ë
v
Q,
vi¸t
x,
E
t¤i iºm
ta ÷ñc iºm
R = P + Q.
tr÷îc ti¶n ta v³ ti¸p tuy¸n cõa ÷íng cong
E
Ch÷ìng 1. Ki¸n thùc chu©n bà
10
H¼nh 1.3: Ph²p cëng: P + Q = R
t¤i
P.
iºm
H¼nh 1.4: Nh¥n æi: P + P = R
÷íng th¯ng n y giao vîi
R0
qua tröc tåa ë
x,
E
t¤i iºm thù hai, kþ hi»u
ta ÷ñc iºm
R.
Khi â
R
R0 .
L§y èi xùng
÷ñc ành ngh¾a l
nh¥n æi cõa iºm P , ta vi¸t R = P + P = 2P .
iºm
Ta cæng thùc hâa ph²p cëng iºm vøa ÷ñc mæ t£ ð tr¶n qua ành ngh¾a chi
ti¸t d÷îi ¥y.
ành ngh¾a 1.5. Luªt nhâm
(
tr¼nh x¡c ành
K.
Gi£ sû
ành ngh¾a
1. N¸u
) Cho
E
l mët ÷íng cong elliptic câ ph÷ìng
y 2 +a1 xy+a3 y = x3 +a2 x2 +a4 x+a6 vîi c¡c h» sè a1 , a2 , a3 , a4 , a6 ∈
P1 = (x1 , y1 )
v
P2 = (x2 , y2 )
P1 + P2 = P3 = (x3 , y3 )
x1 6= x2 ,
l c¡c iºm tr¶n
2. N¸u
x1 = x2
y3 = −y1 − a3 − a1 x3 + m(x1 − x3 ),
y2 −y1
.
x2 −x1
v
y2 = −y1 − a1 x1 − a3 ,
tr÷íng hñp n y ÷ñc gåi l
3. N¸u
P1 , P2 6= ∞.
th¼
m=
x1 = x2
vîi
nh÷ sau:
x3 = −x1 − x2 − a2 + m(m + a1 ),
trong â
E
v
P2 6= −P1 ,
th¼
P1 + P2 = ∞
v iºm
iºm èi cõa P1, kþ hi»u −P1.
P2
trong
th¼
x3 = −x1 − x2 − a2 + m(m + a1 ),
y3 = −y1 − a3 − a1 x3 + m(x1 − x3 ),
Ch÷ìng 1. Ki¸n thùc chu©n bà
3x21 +2a2 x1 +a4 −a1 y
.
2y1 +a1 x1 +a3
m=
trong â
11
Hìn núa, ành ngh¾a
P +∞=P
vîi måi iºm
P
tr¶n
E.
Vîi luªt nhâm (ph²p cëng iºm) ÷ñc ành ngh¾a nh÷ tr¶n, ta nhªn ÷ñc
k¸t qu£ sau.
ành lþ 1.6.
Tªp c¡c iºm cõa ÷íng cong elliptic E x¡c ành
tr¶n K d÷îi ph²p cëng iºm ành ngh¾a nh÷ trong ành ngh¾a 1.5 lªp th nh
mët nhâm aben vîi ph¦n tû trung háa l iºm ∞.
[15, ành lþ 2.1]
ành ngh¾a 1.7.
Gi£ sû
t¤i mët sè nguy¶n
n≥1
tr¶n
P
l mët iºm tr¶n ÷íng cong elliptic
sao cho
nP = ∞
th¼ ta nâi
P
l mët iºm
E . Gi¡ trà n ≥ 1 nhä nh§t thäa m¢n nP = ∞ ÷ñc gåi l c§p
N¸u
E
E.
N¸u tçn
n − xon
cõa iºm
l mët ÷íng cong elliptic x¡c ành tr¶n tr÷íng húu h¤n
Fq ,
P.
ta °t
#E(Fq ) = #{P ∈ E(Fq )}.
Khi â ta câ ành lþ sau º ¡nh gi¡ ë lîn cõa
ành lþ 1.8.
#E(Fq )
(xem [15]).
Cho E l mët ÷íng cong elliptic tr¶n tr÷íng húu h¤n
Fq . Khi â c§p cõa nhâm E(Fq ) thäa m¢n
(Hasse)
√
|q + 1 − #E(Fq )| ≤ 2 q.
Trong thüc h nh, º t½nh sè iºm cõa mët ÷íng cong elliptic tr¶n tr÷íng
húu h¤n ng÷íi ta sû döng mët thuªt to¡n r§t hi»u qu£ th÷íng ÷ñc bi¸t ¸n
vîi t¶n gåi Thuªt to¡n Schoof do R. Schoof · xu§t v o n«m 1986. Còng vîi
nhúng c£i ti¸n cho ¸n nay, Thuªt to¡n Schoof câ ë phùc t¤p t½nh to¡n ÷ñc
÷îc l÷ñng v o kho£ng
O(log8 q)
vîi
q
l c§p cõa tr÷íng cì sð. Chi ti¸t xem
trong [15, Möc 4.5].
C¡c cæng thùc trong luªt nhâm ÷ñc x¥y düng ð tr¶n ·u ÷ñc tr¼nh b y
vîi c¡c iºm cõa ÷íng cong ÷ñc thº hi»n theo tåa ë affine. B¬ng vi»c khû
i c¡c m¨u sè trong cæng thùc, ta nhªn ÷ñc c¡c cæng thùc cëng iºm biºu
di¹n theo tåa ë x¤ £nh cõa c¡c iºm tr¶n ÷íng cong elliptic.
Ch÷ìng 1. Ki¸n thùc chu©n bà
12
1.2 D¤ng Montgomery cõa ÷íng cong elliptic
ành ngh¾a 1.9. ÷íng cong elliptic d¤ng Montgomery
K
x¡c ành tr¶n tr÷íng
l mët ÷íng cong elliptic ÷ñc cho bði ph÷ìng tr¼nh
EM,A,B : Bv 2 = u3 + Au2 + u,
trong â
Do
A ∈ K \ {−2, 2}
B ∈ K \ {0}
(1.4)
B ∈ K \ {0}.
v
n¶n ta câ thº chia c£ hai v¸ cõa ph÷ìng tr¼nh (1.4) cho
B3
v nhªn ÷ñc
°t
v
u
A u
1 u
( )2 = ( )3 + ( )2 + 2 .
B
B
B B
B B
X = u/B, Y = v/B , ta nhªn ÷ñc ph÷ìng tr¼nh d¤ng
Y 2 = X3 +
Nh÷ vªy, vîi ph²p êi bi¸n
Weierstrass
A 2
1
X + 2 X.
B
B
(u, v) 7→ (u/B, v/B) ta bi¸n êi mët ÷íng cong câ
ph÷ìng tr¼nh d¤ng Montgomery v· d¤ng Weierstrass. Do â ÷íng cong elliptic
d¤ng Montgomery l mët tr÷íng hñp ri¶ng cõa
Gi£ sû
P1 = (u1 , v1 )
d¤ng Montgomery
•
v
EM,A,B .
Cæng thùc cëng:
P2 = (u2 , v2 )
(1.1):
l hai iºm tr¶n ÷íng cong elliptic
Khi â
N¸u
P1 6= ±P2
th¼
P3 = (u3 , v3 ) = P1 + P2
÷ñc x¡c
ành bði
u3 = Bλ2 − A − u2 − u1
v3 = λ(u1 − u3 ) − v1 ,
trong â
•
λ = (v2 − v1 )/(u2 − u1 ).
Cæng thùc nh¥n æi:
N¸u
P1 = P2
v
P1 6= −P2
÷ñc x¡c ành bði
u3 = Bλ2 − A − 2u1
v3 = λ(u1 − u3 ) − v1 ,
ð ¥y
λ = (3u21 + 2Au1 + 1)/(2Bv1 ).
th¼
P3 = (u3 , v3 ) = 2P1
Ch÷ìng 1. Ki¸n thùc chu©n bà
•
N¸u P
ë l
2
= −P1
13
P 1 + P 2 = ∞,
th¼
−P1
ð ¥y
l iºm èi cõa
P1
v câ tåa
(u1 , −v1 ).
ành lþ d÷îi ¥y ch¿ ra i·u ki»n º bi¸n êi mët ph÷ìng tr¼nh Weierstrass
ngn th nh ph÷ìng tr¼nh d¤ng Montgomery.
ành lþ 1.10. Cho K l mët tr÷íng câ char(K) 6= 2, 3. Mët ÷íng cong elliptic
câ ph÷ìng tr¼nh d¤ng Weierstrass ngn E : y2 = x3 + ax + b câ thº bi¸n êi
v· d¤ng Montgomery n¸u v ch¿ n¸u nâ thäa m¢n c¡c i·u ki»n sau ¥y:
E
1. Ph÷ìng tr¼nh x3 + ax + b = 0 câ ½t nh§t mët nghi»m trong K .
2. Ph¦n tû 3α2 + a l ch½nh ph÷ìng trong K , ð ¥y α l mët nghi»m cõa
ph÷ìng tr¼nh x3 + ax + b = 0 trong K .
Chùng minh. i·u ki»n c¦n: Gi£ sû E thäa m¢n c¡c i·u ki»n trong ành
lþ. Gåi
s
l mët trong c¡c c«n bªc hai cõa
B = s, A = 3αs.
bi¸n êi
E
trð th nh
EM,A,B ,
cong elliptic d¤ng Montgomery ành ngh¾a bði
Montgomery
trong
K,
Khi â, d¹ d ng kiºm tra ÷ñc ph²p êi bi¸n
(u, v) = (s(x − α), sy)
i·u ki»n õ:
(3α2 + a)−1
EM,A,B
(x, y) 7→
l ֒ng
Bv 2 = u3 + Au2 + u.
Ng÷ñc l¤i, gi£ sû ÷íng cong elliptic
EM,A,B : Bv 2 = u3 + Au2 + u.
ð ¥y
v °t
E
÷ñc bi¸n êi v· d¤ng
D¹ th§y iºm
(0, 0) ∈ EM,A,B (k)
v sû döng cæng thùc cëng iºm ð tr¶n, ta câ thº ch¿ ra ÷ñc iºm n y câ c§p
2.
Do â suy ra ÷íng cong
ph÷ìng tr¼nh
ki»n
(1)
x3 + ax + b = 0
E
ph£i câ c§p hai, i·u n y çng ngh¾a vîi vi»c
ph£i câ ½t nh§t mët nghi»m trong
tùc l i·u
÷ñc thäa m¢n.
Ph²p ¯ng c§u bi¸n êi d¤ng Weierstrass ngn cõa
gomery
K,
EM,A,B
K, s, t 6= 0
÷ñc cho d÷îi d¤ng
n¶n ta nhªn ÷ñc
E
th nh d¤ng Mont-
(x, y) 7→ (s(x−α0 ), t(y−β 0 )) vîi s, t, α0 , β 0 ∈
n o â. V¼ tçn t¤i mët iºm
d¤ng Weierstrass ngn
E
(α, 0)
câ c§p
t÷ìng ùng vîi iºm
α0 = α, β 0 = 0.
2
(0, 0)
tr¶n ÷íng cong elliptic
tr¶n d¤ng Montgomery,
Khi â ph²p ¯ng c§u ¡nh x¤
(s(x − α), ty). Do iºm n y n¬m tr¶n EM,A,B
(x, y)
tîi
n¶n thay v o ph÷ìng tr¼nh ÷íng
cong ta nhªn ÷ñc
Bt2 y 2 = s3 (x − α)3 + As2 (x − α)2 + s(x − α).
Ch÷ìng 1. Ki¸n thùc chu©n bà
Do
(x, y) l mët iºm tr¶n E
14
n¶n thay
y 2 = x3 + ax + b v o ph÷ìng tr¼nh tr¶n,
ta ֖c
Bt2 (x3 + ax + b) = s3 (x − α)3 + As(x − α)2 + (x − α).
çng nh§t h» sè hai v¸ ta thu ÷ñc
tr¼nh v chia c£ hai v¸ cho
s
Bt2 = s3 ,
thay ng÷ñc trð l¤i v o ph÷ìng
ta câ
s2 (x3 + ax + b) = s2 (x − α)3 + As(x − α)2 + (x − α).
L§y ¤o h m hai v¸ cõa ph÷ìng tr¼nh tr¶n theo
x
t¤i
x=α
ta ֖c
s2 (3α2 + a) = 1,
tø ¥y suy ra
3α2 + a
l ch½nh ph÷ìng trong
thäa m¢n. ành lþ ÷ñc chùng minh.
K,
vªy i·u ki»n (2) công ÷ñc
Ch֓ng 2
D¤ng chu©n Edwards cho ÷íng
cong elliptic
2.1 D¤ng chu©n Edwards
Trong möc n y chóng tæi tr¼nh b y ành ngh¾a ÷íng cong Edwards, ÷íng
cong Edwards cuën (twisted Edwards curve) công nh÷ ph²p cëng iºm tr¶n
c¡c d¤ng ÷íng cong n y. Nëi dung cõa möc n y ÷ñc tr¼nh b y düa tr¶n c¡c
t i li»u [1, 2, 4, 5, 9].
2.1.1 D¤ng chu©n Edwards
ành ngh¾a 2.1. k
Cho
l mët tr÷íng câ °c sè kh¡c 2, v
d ∈ k \ {0, 1}.
÷íng cong Edwards, kþ hi»u EE,d, l ÷íng cong ÷ñc cho bði ph÷ìng tr¼nh
EE,d : x2 + y 2 = 1 + dx2 y 2 .
÷íng cong Edwards cuën
ax2 + y 2 = 1 + dx2 y 2
ành ngh¾a 2.2.
hai
cõa
E
trong â
Cho
E
EE,a,d :
l ÷íng cong câ ph÷ìng tr¼nh x¡c ành
a, d ∈ k \ {0, 1}, a 6= d.
l mët ÷íng cong ành ngh¾a tr¶n
l ÷íng cong ¯ng c§u vîi
E
k.
Mët
tr¶n mët mð rëng tr÷íng
cuën bªc
K/k
vîi
[K : k] = 2.
D¹ th§y ÷íng cong Edwards cuën
bªc hai cõa ÷íng cong Edwards
EE,a,d : ax2 + y 2 = 1 + dx2 y 2
l mët cuën
EE,d/a : X 2 + Y 2 = 1 + (d/a)X 2 Y 2 .
15
nh x¤
Ch÷ìng 2. D¤ng chu©n Edwards cho ÷íng cong elliptic
16
√
(x, y) 7→ (x a, y) l mët ¯ng c§u tø EE,a,d tîi EE,d/a tr¶n tr÷íng mð rëng
√
k( a). Do â, n¸u a l ch½nh ph÷ìng trong k th¼ EE,a,d ¯ng c§u vîi EE,d/a
tr¶n
k.
V½ dö 2.3.
H¼nh 2.1: x2 + y 2 = 1 − 200x2 y 2
H¼nh 2.2: −4x2 + y 2 = 1 − 100x2 y 2
Bê · 2.4. Méi ÷íng cong Edwards cuën E
÷ìng song húu t¿ vîi ÷íng cong EM,A,B
A = 2(a + d)/(a − d) v B = 4/(a − d).
:
ành ngh¾a nh÷ tr¶n l t÷ìng
Bv 2 = u3 + Au2 + u, trong â
E,a,d
Chùng minh. Rã r ng A, B ÷ñc ành ngh¾a v¼ a 6= d. Hìn núa, B ∈ k \ {0} v
A ∈ k \ {−2, 2}
v¼ n¸u
vîi ành ngh¾a cõa
A = 2,
EE,a,d ;
thu¨n vîi ành ngh¾a cõa
c¡c iºm húu t¿ tr¶n
k
n¸u
suy ra
a−d = a+d
A = −2
th¼
k²o theo
−d − a = a − d
d = 0,
k²o theo
m¥u thu¨n
a = 0,
m¥u
EE,a,d . Kþ hi»u EE,a,d (k) v EM,A,B (k) l¦n l÷ñt l tªp
cõa hai ÷íng cong
EE,a,d
v
EM,A,B . X²t ¡nh x¤ húu t¿
ϕ : EE,a,d (k) → EM,A,B (k)
(x, y)
trong â
7→
(u, v)
(u, v) = (1 + y)/(1 − y), (1 + y)/(1 − y)x .
÷ìng song húu t¿ tø
EE,a,d (k)
tîi
EM,A,B
Ta s³ ch¿ ra
vîi ¡nh x¤ ng÷ñc
ϕ
l t֓ng
(u, v) 7→ (x, y) =
Ch÷ìng 2. D¤ng chu©n Edwards cho ÷íng cong elliptic
(u/v), (u − 1)/(u + 1)
. Thªt vªy, vîi
nh÷ tr¶n v o ph÷ìng tr¼nh
v
B = 4/(a − d),
x2 + y 2 = 1 + dx2 y 2
cong
EM,A,B .
(x, y)
(x, y) ∈ EE,a,d (k),
Bv 2 = u3 + Au2 + u
vîi
(u, v)
x¡c ành
A = 2(a + d)/(a − d)
b¬ng c¡c t½nh to¡n ìn gi£n k¸t hñp sû döng h» thùc
ta nhªn ÷ñc k¸t qu£
(u, v)
thäa m¢n ph÷ìng tr¼nh ÷íng
y=1
x=0
v
tr¶n ÷íng cong
cõa ¡nh x¤
EE,a,d
ϕ
ch¿ xu§t hi»n vîi húu h¤n c¡c
; c¡c tr÷íng hñp c¡ bi»t
cõa ¡nh x¤ ng÷ñc công ch¿ xu§t hi»n vîi húu h¤n iºm
ϕ
thay
Chi·u ng÷ñc l¤i công ÷ñc kiºm tra t÷ìng tü. M°t kh¡c, c¡c
tr÷íng hñp c¡ bi»t
iºm
17
l t÷ìng ÷ìng song húu t¿ tø
֒ng cong Edwards
EE,a,d
EE,a,d (k)
tîi
v=0
v
u = −1
(u, v) tr¶n EM,A,B . Vªy
EM,A,B (k),
i·u n y câ ngh¾a
l t÷ìng ÷ìng song húu t¿ vîi ÷íng cong
EM,A,B .
ành lþ d÷îi ¥y cho ta th§y sü bi¸n êi qua l¤i giúa d¤ng Weierstrass v
d¤ng Edwards cõa mët ÷íng cong elliptic.
ành lþ 2.5.
Cho k l mët tr÷íng câ °c sè kh¡c 2. Gi£ sû
E l mët ÷íng cong elliptic tr¶n k sao cho nhâm E(k) câ mët iºm c§p 4.
Khi â
1. Tçn t¤i d ∈ k \ {0, 1} sao cho ÷íng cong x2 + y2 = 1 + dx2y2 l t÷ìng
÷ìng song húu t¿ tr¶n k vîi mët cuën bªc hai cõa E ;
([4, ành lþ 2.1])
2. N¸u E(k) câ duy nh§t mët ph¦n tû c§p 2 th¼ tçn t¤i ph¦n tû khæng ch½nh
ph÷ìng d ∈ k sao cho ÷íng cong x2 + y2 = 1 + dx2y2 l t÷ìng ÷ìng song
húu t¿ tr¶n k vîi mët cuën bªc hai cõa E ; v
3. N¸u k l húu h¤n v E(k) câ duy nh§t mët ph¦n tû c§p 2 th¼ tçn t¤i mët
ph¦n tû khæng ch½nh ph÷ìng d ∈ k sao cho ÷íng cong x2 + y2 = 1 + dx2y2
l t÷ìng ÷ìng song húu t¿ tr¶n k vîi E .
Chùng minh. Gi£ sû ph÷ìng tr¼nh d¤ng Weierstrass têng qu¡t cõa ÷íng cong
elliptic
E
l
s2 + a1 rs + a3 s = r3 + a2 r2 + a4 r + a6 .
V¼ char(k)
cõa
E
6= 2
n¶n thüc hi»n ph²p êi bi¸n
trð th nh
s̄ = s + (a1 r + a3 )/2,
ph÷ìng tr¼nh
s̄2 = r3 + (a2 − a21 /4)r2 + (a4 − a1 a3 )r + (a6 − a23 /4).
Do â,
Ch÷ìng 2. D¤ng chu©n Edwards cho ÷íng cong elliptic
khæng m§t t½nh têng qu¡t ta câ thº gi£ thi¸t
ph÷ìng tr¼nh
Gåi
ta câ
2P
2P = (r2 , 0).
v· gèc tåa ë
tr¼nh d¤ng
qua
a1 = 0
v
a3 = 0,
tùc l
E
câ
s2 = r3 + a2 r2 + a4 r + a6 .
P = (r1 , s1 )
2P = (0, 0)
18
l iºm c§p 4 tr¶n
E.
Khi â
B¬ng ph²p êi bi¸n ìn gi£n
2P
l mët iºm c§p hai n¶n
r̄ = r − r2 ,
ta tành ti¸n iºm
(0, 0). Do vªy, khæng gi£m têng qu¡t, ta công câ thº gi£ thi¸t
v tø â suy ra
a6 = 0.
s2 = r3 + a2 r2 + a4 r.
E
Lóc n y ÷íng cong elliptic
câ ph÷ìng
Ta s³ t¼m c¡ch biºu di¹n c¡c h» sè
a2
v
a4
r1 , s1 .
Do
P
l iºm c§p 4 n¶n
s1 6= 0
ph÷ìng tr¼nh cõa ÷íng cong
E
th§y ÷íng th¯ng ti¸p tuy¸n vîi
suy ra
E
t¤i
kh¡c ph÷ìng tr¼nh ti¸p tuy¸n t¤i iºm
h» sè ti¸p tuy¸n v
kh¡c, v¼
P
s1 = 0
(v¼ n¸u
r1 6= 0.
P
P
th¼ iºm
Ph÷ìng tr¼nh
i qua gèc tåa ë
câ d¤ng
2P = (0, 0)
(0, 0),
cho
hay nâi c¡ch
λ = (3r12 +2a2 r1 +a4 )/2s1 . Do â 3r13 +2a2 r12 +a4 r1 = 2s21 . M°t
l mët iºm tr¶n ÷íng cong
E
n¶n ta câ
v o ta câ
a2 = s21 /r12 − 2r1 .
°t
2s21 = 2s31 + 2a2 r12 + 2a4 r1 .
r13 = a4 r1 ,
Ngo i ra, tø ph÷ìng tr¼nh ÷íng cong ta nhªn ÷ñc
a4 = r12
câ c§p 2). Tø
s1 −0 = (r1 −0)λ trong â λ l
Trø hai ph÷ìng tr¼nh n y cho nhau, ta nhªn ÷ñc
Thay
P
suy ra
a4 = r12 .
a2 = (s21 − r13 − a4 r1 )/r12 .
d = 1 − 4r13 /s21
ta nhªn ÷ñc
a2 = 2((1 + d)/(1 − d))r1 .
Do
th¼
r1 6= 0
n¶n
d 6= 1.
a2 = 2r1 , a4 = r12 ,
Hìn núa ta công câ
d 6= 0
v¼ n¸u ng÷ñc l¤i
do â v¸ ph£i cõa ph÷ìng tr¼nh ÷íng cong
d =0
E
s³ l
r3 + a2 r2 + a4 r = r3 + 2r1 r2 + r12 r = r(r + r1 )2 , i·u n y m¥u thu¨n vîi gi£ thi¸t
E
d¹ d ng kiºm tra ÷ñc iºm
E
d l mët sè ch½nh ph÷ìng th¼ ta
√
√
r1 ( d + 1)/ d − 1), 0 công thuëc ÷íng cong
l mët ÷íng cong elliptic. Ngo i ra, n¸u
v iºm n y câ c§p 2.
X²t hai cuën bªc hai cõa
E,
k½ hi»u
E0
x¡c ành bði c¡c ph÷ìng tr¼nh t÷ìng ùng
v
E 00
l hai ֒ng cong elliptic
(r1 /(1 − d))s2 = r3 + a2 r2 + a4 r
v
(dr1 /(1 − d))s2 = r3 + a2 r2 + a4 r.
Thüc hi»n ph²p êi bi¸n
u = r/r1 v v = s/r1 , ph÷ìng tr¼nh cõa E 0 trð th nh
(1/(1 − d))v 2 = u3 + a2 /r1 u2 + a4 /r12 u = u3 + 2((1 + d)/(1 − d))u2 + u
a2 = 2((1 + d)/(1 − d))r1
tr¼nh ÷íng cong
E 00
v
a4 = r12
trð th nh
do ta câ
nh÷ ¢ t½nh ð tr¶n; t÷ìng tü th¼ ph÷ìng
d/(1 − d)v 2 = u3 + 2((1 + d)/(1 − d))u2 + u.
- Xem thêm -