Tài liệu Về dạng chuẩn edwards và một vài ứng dụng

„I HÅC QUÈC GIA H€ NËI TR×ÍNG „I HÅC KHOA HÅC TÜ NHI–N  Và TÒNG LINH V— D„NG CHU‰N EDWARDS V€ MËT V€I ÙNG DÖNG LUŠN V‹N TH„C Sž TON HÅC H€ NËI - 2014 „I HÅC QUÈC GIA H€ NËI TR×ÍNG „I HÅC KHOA HÅC TÜ NHI–N  Và TÒNG LINH V— D„NG CHU‰N EDWARDS V€ MËT V€I ÙNG DÖNG Chuy¶n ng nh: „I SÈ V€ LÞ THUY˜T SÈ M¢ sè: 60460104 LUŠN V‹N TH„C Sž TON 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 xo­n 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 th­c m­c 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 s­c ¸n Th¦y gi¡o cõa m¼nh. Tæi xin gûi líi c£m ìn s¥u s­c ¸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 s­c 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 s­c ¸n Bè, Mµ v  gia ¼nh tæi, nhúng ng÷íi ¢ tin t÷ðng s¥u s­c, ¢ 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 t­c mîi cho c¡c ÷íng cong elliptic. B¬ng vi»c têng qu¡t hâa mët v½ dö b­t 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 t­c 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 ch­c 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 xo­n 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 xo­n 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 xo­n ¢ 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 xo­n ¢ 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 ng­n. (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 − xo­n 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 ng­n 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 ng­n 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 ng­n 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 ng­n 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.