intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Luận văn Thạc sĩ Khoa học: Về dạng chuẩn edwards và một vài ứng dụng

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:65

Thêm vào BST
Báo xấu
42
lượt xem 8
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn trình bày đị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ự. Tác giả 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Về dạng chuẩn edwards và một vài ứng dụng

  1. „I HÅC QUÈC GIA H€ NËI TR×ÍNG „I HÅC KHOA HÅC TÜ NHI–N H€ NËI  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
  2. „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
  3. Möc löc Líi c£m ìn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Líi mð ¦u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1 Ki¸n thùc chu©n bà 6 1.1 Lþ thuy¸t chung v· ÷íng cong elliptic . . . . . . . . . . . . . . 6 1.2 D¤ng Montgomery cõa ÷íng cong elliptic . . . . . . . . . . . . 12 2 D¤ng chu©n Edwards cho ÷íng cong elliptic 15 2.1 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 2.2 Nhâm c¡c iºm tr¶n ÷íng cong Edwards cuën . . . . . . . . . 27 3 Mët sè ùng döng cõa ÷íng cong d¤ng chu©n Edwards 41 3.1 C¡c iºm câ c§p nhä tr¶n ÷íng cong Edwards cuën . . . . . . 41 3.2 Nhâm xo­n cõa ÷íng cong Edwards tr¶n Q . . . . . . . . . . . 46 3.3 Ùng döng cõa ÷íng cong Edwards trong mªt m¢ . . . . . . . . 58 K¸t luªn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 T i li»u tham kh£o . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 1
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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. [8, ành ngh¾a 3.1] Mët ÷í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 , (1.1) vîi a1 , a2 , a3 , a4 , a6 ∈ K v  ∆ 6= 0, trong â ∆ l  bi»t thùc 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 .  1 3 4 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
  9. Ch÷ìng 1. Ki¸n thùc chu©n bà 7 trong â ∞ l  iºm t¤i væ h¤n. V½ dö 1.2. H¼nh 1.1: y 2 = x3 − x H¼nh 1.2: y 2 = x3 + x Cho E 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  E¯ : y 2 z + a1 xyz + a3 yz 2 = x3 + a2 x2 z + a4 xz 2 + a6 z 3 , v  iºm P tr¶n E s³ câ tåa ë vi¸t d÷îi d¤ng x¤ £nh l  (x : y : z). D¹ th§y, n¸u iºm P câ tåa ë vi¸t d÷îi d¤ng affine l  (x, y) th¼ d¤ng x¤ £nh t÷ìng ùng cõa nâ s³ l  (x : y : 1). Ng÷ñc l¤i, n¸u iºm P câ tåa ë x¤ £nh (x : y : z) vîi z 6= 0 th¼ d¤ng affine t÷ìng ùng cõa nâ s³ l  (x/z, y/z). Trong tr÷íng hñp z=0 th¼ iºm P ch½nh l  iºm ∞, 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 1. Ph÷ìng tr¼nh (1.1) ÷ñc gåi l  qu¡t, hay º ìn gi£n, ta gåi l  Ph÷ìng tr¼nh Weierstrass.
  10. Ch÷ìng 1. Ki¸n thùc chu©n bà 8 2. Ta nâi E ÷ñc ành ngh¾a tr¶n K bði v¼ c¡c h» sè a1 , a2 , a3 , a4 , a6 trong ph÷ìng tr¼nh ành ngh¾a cõa E l  c¡c ph¦n tû thuëc K. Rã r ng l  n¸u E ành ngh¾a tr¶n K th¼ E công ành ngh¾a tr¶n mët tr÷íng mð rëng tòy þ cõa K. 3. i·u ki»n ∆ 6= 0 £m b£o ÷íng cong elliptic E l  trìn, i·u n y câ ngh¾a l  khæng tçn t¤i iºm n o tr¶n E 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 (x, y) thäa m¢n ph÷ìng tr¼nh cõa ÷íng cong v  câ c¡c tåa ë x, y thuëc L. iºm t¤i væ h¤n ÷ñc xem l  mët iºm L − húu t¿ èi vîi måi tr÷íng mð rëng L cõa K. ành ngh¾a 1.4. Hai ÷íng cong elliptic E1 v  E2 à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 + a ¯3 y = x3 + a ¯1 xy + a ¯2 x2 + a ¯4 x + a ¯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) (1.2) bi¸n êi ph÷ìng tr¼nh E1 th nh ph÷ìng tr¼nh 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  a1 x a3 a a1 a3 a y+ + = x3 + a2 + 1 x2 + a4 + x+ 3 + a6 . 2 2 4 2 4
  11. Ch÷ìng 1. Ki¸n thùc chu©n bà 9 °t     y1 = y + a21 x + a3 2 ,  a0 = a + a21 ,   2 2 4 0 a1 a3    a4 = a4 + 2 ,  a0 = a23 + a ,   6 4 6 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  0 3  02   03  a a a y12 = x + 2 + a04 − 2 x + a06 − 2 . 3 3 27 °t  a02    x 1 = x + 3 , 02 a = a04 − a3 ,  b = a0 − a032 ,   6 27 ta ÷ñc ph÷ìng tr¼nh y12 = x31 + ax + b. (1.3) Khi â ta t½nh ÷ñc bi»t thùc cõa ÷íng cong ∆ = −16(4a3 + 27b2 ). Ph÷ìng tr¼nh (1.3) ÷ñc gåi l  Ph÷ìng tr¼nh Weierstrass thu gån, hay l  Ph÷ìng tr¼nh Weierstrass ng­n. º 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û P = (x1 , y1 ) v  Q = (x2 , y2 ) l  hai iºm ph¥n bi»t tr¶n ÷íng cong elliptic E. Khi â têng cõa P v  Q ÷ñc ành ngh¾a nh÷ sau: Tr÷îc ti¶n, ta v³ ÷íng th¯ng qua P v  Q; ÷íng th¯ng n y giao vîi ÷íng cong E t¤i iºm thù ba, gåi l  iºm R0 . L§y èi xùng iºm R0 qua tröc tåa ë x, ta ÷ñc iºm R. Khi â R ÷ñc gåi l  têng cõa hai iºm P v  Q, vi¸t R = P + Q. º ành ngh¾a 2P = P + P , tr÷îc ti¶n ta v³ ti¸p tuy¸n cõa ÷íng cong E
  12. Ch÷ìng 1. Ki¸n thùc chu©n bà 10 H¼nh 1.3: Ph²p cëng: P + Q = R H¼nh 1.4: Nh¥n æi: P + P = R t¤i P. ÷íng th¯ng n y giao vîi E t¤i iºm thù hai, kþ hi»u R0 . L§y èi xùng iºm R0 qua tröc tåa ë x, ta ÷ñc iºm R. Khi â R ÷ñc ành ngh¾a l  iºm nh¥n æi cõa iºm P , ta vi¸t R = P + P = 2P . 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 ( ) Cho E l  mët ÷íng cong elliptic câ ph÷ìng tr¼nh x¡c ành y 2 +a1 xy+a3 y = x3 +a2 x2 +a4 x+a6 vîi c¡c h» sè a1 , a2 , a3 , a4 , a6 ∈ K. Gi£ sû P1 = (x1 , y1 ) v  P2 = (x2 , y2 ) l  c¡c iºm tr¶n E vîi P1 , P2 6= ∞. ành ngh¾a P1 + P2 = P3 = (x3 , y3 ) nh÷ sau: 1. N¸u x1 6= x2 , th¼ x3 = −x1 − x2 − a2 + m(m + a1 ), y3 = −y1 − a3 − a1 x3 + m(x1 − x3 ), y2 −y1 trong â m= x2 −x1 . 2. N¸u x1 = x2 v  y2 = −y1 − a1 x1 − a3 , th¼ P1 + P2 = ∞ v  iºm P2 trong tr÷íng hñp n y ÷ñc gåi l  iºm èi cõa P1, kþ hi»u −P1. 3. N¸u x1 = x2 v  P2 6= −P1 , th¼ x3 = −x1 − x2 − a2 + m(m + a1 ), y3 = −y1 − a3 − a1 x3 + m(x1 − x3 ),
  13. Ch÷ìng 1. Ki¸n thùc chu©n bà 11 3x21 +2a2 x1 +a4 −a1 y trong â m= 2y1 +a1 x1 +a3 . 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 [15, ành lþ 2.1] 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 ∞. ành ngh¾a 1.7. Gi£ sû P l  mët iºm tr¶n ÷íng cong elliptic E. N¸u tçn t¤i mët sè nguy¶n n≥1 sao cho nP = ∞ th¼ ta nâi P l  mët iºm n − xo­n tr¶n E . Gi¡ trà n ≥ 1 nhä nh§t thäa m¢n nP = ∞ ÷ñc gåi l  c§p cõa iºm P. N¸u E l  mët ÷íng cong elliptic x¡c ành tr¶n tr÷íng húu h¤n Fq , ta °t #E(Fq ) = #{P ∈ E(Fq )}. Khi â ta câ ành lþ sau º ¡nh gi¡ ë lîn cõa #E(Fq ) (xem [15]). ành lþ 1.8. Cho E l  mët ÷íng cong elliptic tr¶n tr÷íng húu h¤n (Hasse) Fq . Khi â c§p cõa nhâm E(Fq ) thäa m¢n √ |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.
  14. 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 x¡c ành tr¶n tr÷íng K l  mët ÷íng cong elliptic ÷ñc cho bði ph÷ìng tr¼nh EM,A,B : Bv 2 = u3 + Au2 + u, (1.4) trong â A ∈ K \ {−2, 2} v  B ∈ K \ {0}. Do B ∈ K \ {0} n¶n ta câ thº chia c£ hai v¸ cõa ph÷ìng tr¼nh (1.4) cho B3 v  nhªn ÷ñc v u A u 1 u ( )2 = ( )3 + ( )2 + 2 . B B B B B B °t X = u/B, Y = v/B , ta nhªn ÷ñc ph÷ìng tr¼nh d¤ng Weierstrass A 2 1 Y 2 = X3 + X + 2 X. B B Nh÷ vªy, vîi ph²p êi bi¸n (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 (1.1): Gi£ sû P1 = (u1 , v1 ) v  P2 = (u2 , v2 ) l  hai iºm tr¶n ÷íng cong elliptic d¤ng Montgomery EM,A,B . Khi â • Cæng thùc cëng: 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 th¼ P3 = (u3 , v3 ) = 2P1 ÷ñc x¡c ành bði u3 = Bλ2 − A − 2u1 v3 = λ(u1 − u3 ) − v1 , ð ¥y λ = (3u21 + 2Au1 + 1)/(2Bv1 ).
  15. Ch÷ìng 1. Ki¸n thùc chu©n bà 13 • N¸u P 2 = −P1 th¼ P 1 + P 2 = ∞, ð ¥y −P1 l  iºm èi cõa P1 v  câ tåa ë l  (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 E 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: 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 (3α2 + a)−1 trong K, v  °t B = s, A = 3αs. Khi â, d¹ d ng kiºm tra ÷ñc ph²p êi bi¸n (x, y) 7→ (u, v) = (s(x − α), sy) bi¸n êi E trð th nh EM,A,B , ð ¥y EM,A,B l  ÷íng cong elliptic d¤ng Montgomery ành ngh¾a bði Bv 2 = u3 + Au2 + u. i·u ki»n õ: Ng÷ñc l¤i, gi£ sû ÷íng cong elliptic E ÷ñc bi¸n êi v· d¤ng Montgomery EM,A,B : Bv 2 = u3 + Au2 + u. 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 E ph£i câ c§p hai, i·u n y çng ngh¾a vîi vi»c ph÷ìng tr¼nh x3 + ax + b = 0 ph£i câ ½t nh§t mët nghi»m trong K, tùc l  i·u ki»n (1) ÷ñc thäa m¢n. Ph²p ¯ng c§u bi¸n êi d¤ng Weierstrass ng­n cõa E th nh d¤ng Mont- gomery EM,A,B ÷ñc cho d÷îi d¤ng (x, y) 7→ (s(x−α0 ), t(y−β 0 )) vîi s, t, α0 , β 0 ∈ K, s, t 6= 0 n o â. V¼ tçn t¤i mët iºm (α, 0) câ c§p 2 tr¶n ÷íng cong elliptic d¤ng Weierstrass ng­n E t÷ìng ùng vîi iºm (0, 0) tr¶n d¤ng Montgomery, n¶n ta nhªn ÷ñc α0 = α, β 0 = 0. Khi â ph²p ¯ng c§u ¡nh x¤ (x, y) tîi (s(x − α), ty). Do iºm n y n¬m tr¶n EM,A,B 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 − α).
  16. Ch÷ìng 1. Ki¸n thùc chu©n bà 14 Do (x, y) l  mët iºm tr¶n E 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 Bt2 = s3 , thay ng÷ñc trð l¤i v o ph÷ìng tr¼nh v  chia c£ hai v¸ cho s 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 K, vªy i·u ki»n (2) công ÷ñc thäa m¢n. ành lþ ÷ñc chùng minh. 
  17. 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 l  ÷íng cong câ ph÷ìng tr¼nh x¡c ành EE,a,d : ax2 + y 2 = 1 + dx2 y 2 trong â a, d ∈ k \ {0, 1}, a 6= d. ành ngh¾a 2.2. Cho E l  mët ÷íng cong ành ngh¾a tr¶n k. Mët cuën bªc hai cõa E l  ÷íng cong ¯ng c§u vîi E tr¶n mët mð rëng tr÷íng K/k vîi [K : k] = 2. D¹ th§y ÷íng cong Edwards cuën EE,a,d : ax2 + y 2 = 1 + dx2 y 2 l  mët cuën bªc hai cõa ÷íng cong Edwards EE,d/a : X 2 + Y 2 = 1 + (d/a)X 2 Y 2 . nh x¤ 15
  18. 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 E,a,dành ngh¾a nh÷ tr¶n l  t÷ìng ÷ìng song húu t¿ vîi ÷íng cong EM,A,B : Bv 2 = u3 + Au2 + u, trong â A = 2(a + d)/(a − d) v  B = 4/(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 A = 2, suy ra a−d = a+d k²o theo d = 0, m¥u thu¨n vîi ành ngh¾a cõa EE,a,d ; n¸u A = −2 th¼ −d − a = a − d k²o theo a = 0, m¥u thu¨n vîi ành ngh¾a cõa EE,a,d . Kþ hi»u EE,a,d (k) v  EM,A,B (k) l¦n l÷ñt l  tªp c¡c iºm húu t¿ tr¶n k 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) 7→ (u, v)  trong â (u, v) = (1 + y)/(1 − y), (1 + y)/(1 − y)x . Ta s³ ch¿ ra ϕ l  t÷ìng ÷ìng song húu t¿ tø EE,a,d (k) tîi EM,A,B vîi ¡nh x¤ ng÷ñc (u, v) 7→ (x, y) =
  19. Ch÷ìng 2. D¤ng chu©n Edwards cho ÷íng cong elliptic 17  (u/v), (u − 1)/(u + 1) . Thªt vªy, vîi (x, y) ∈ EE,a,d (k), thay (u, v) x¡c ành nh÷ tr¶n v o ph÷ìng tr¼nh Bv 2 = u3 + Au2 + u vîi A = 2(a + d)/(a − d) v  B = 4/(a − d), b¬ng c¡c t½nh to¡n ìn gi£n k¸t hñp sû döng h» thùc x2 + y 2 = 1 + dx2 y 2 ta nhªn ÷ñc k¸t qu£ (u, v) thäa m¢n ph÷ìng tr¼nh ÷íng cong EM,A,B . 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 y=1 v  x=0 cõa ¡nh x¤ ϕ ch¿ xu§t hi»n vîi húu h¤n c¡c iºm (x, y) tr¶n ÷íng cong EE,a,d ; c¡c tr÷íng hñp c¡ bi»t v=0 v  u = −1 cõa ¡nh x¤ ng÷ñc công ch¿ xu§t hi»n vîi húu h¤n iºm (u, v) tr¶n EM,A,B . Vªy ϕ l  t÷ìng ÷ìng song húu t¿ tø EE,a,d (k) tîi EM,A,B (k), i·u n y câ ngh¾a ÷íng cong Edwards EE,a,d 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û ([4, ành lþ 2.1]) 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 ; 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) 6= 2 n¶n thüc hi»n ph²p êi bi¸n s¯ = s + (a1 r + a3 )/2, ph÷ìng tr¼nh cõa E trð th nh s¯2 = r3 + (a2 − a21 /4)r2 + (a4 − a1 a3 )r + (a6 − a23 /4). Do â,
  20. Ch÷ìng 2. D¤ng chu©n Edwards cho ÷íng cong elliptic 18 khæng m§t t½nh têng qu¡t ta câ thº gi£ thi¸t a1 = 0 v  a3 = 0, tùc l  E câ ph÷ìng tr¼nh s2 = r3 + a2 r2 + a4 r + a6 . Gåi P = (r1 , s1 ) l  iºm c§p 4 tr¶n E. Khi â 2P l  mët iºm c§p hai n¶n ta câ 2P = (r2 , 0). B¬ng ph²p êi bi¸n ìn gi£n r¯ = r − r2 , ta tành ti¸n iºm 2P v· gèc tåa ë (0, 0). Do vªy, khæng gi£m têng qu¡t, ta công câ thº gi£ thi¸t 2P = (0, 0) v  tø â suy ra a6 = 0. Lóc n y ÷íng cong elliptic E câ ph÷ìng tr¼nh d¤ng s2 = r3 + a2 r2 + a4 r. Ta s³ t¼m c¡ch biºu di¹n c¡c h» sè a2 v  a4 qua r1 , s1 . Do P l  iºm c§p 4 n¶n s1 6= 0 (v¼ n¸u s1 = 0 th¼ iºm P câ c§p 2). Tø ph÷ìng tr¼nh cõa ÷íng cong E suy ra r1 6= 0. Ph÷ìng tr¼nh 2P = (0, 0) cho th§y ÷íng th¯ng ti¸p tuy¸n vîi E t¤i P i qua gèc tåa ë (0, 0), hay nâi c¡ch kh¡c ph÷ìng tr¼nh ti¸p tuy¸n t¤i iºm P câ d¤ng s1 −0 = (r1 −0)λ trong â λ l  h» sè ti¸p tuy¸n v  λ = (3r12 +2a2 r1 +a4 )/2s1 . Do â 3r13 +2a2 r12 +a4 r1 = 2s21 . M°t kh¡c, v¼ P l  mët iºm tr¶n ÷íng cong E n¶n ta câ 2s21 = 2s31 + 2a2 r12 + 2a4 r1 . Trø hai ph÷ìng tr¼nh n y cho nhau, ta nhªn ÷ñc r13 = a4 r1 , suy ra a4 = r12 . Ngo i ra, tø ph÷ìng tr¼nh ÷íng cong ta nhªn ÷ñc a2 = (s21 − r13 − a4 r1 )/r12 . Thay a4 = r12 v o ta câ a2 = s21 /r12 − 2r1 . °t d = 1 − 4r13 /s21 ta nhªn ÷ñc a2 = 2((1 + d)/(1 − d))r1 . Do r1 6= 0 n¶n d 6= 1. Hìn núa ta công câ d 6= 0 v¼ n¸u ng÷ñc l¤i d =0 th¼ a2 = 2r1 , a4 = r12 , do â v¸ ph£i cõa ph÷ìng tr¼nh ÷íng cong 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 l  mët ÷íng cong elliptic. Ngo i ra, n¸u d l  mët sè ch½nh ph÷ìng th¼ ta √ √  d¹ d ng kiºm tra ÷ñc iºm r1 ( d + 1)/ d − 1), 0 công thuëc ÷íng cong E v  iºm n y câ c§p 2. X²t hai cuën bªc hai cõa E, k½ hi»u E0 v  E 00 l  hai ÷íng cong elliptic x¡c ành bði c¡c ph÷ìng tr¼nh t÷ìng ùng (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 do ta câ a2 = 2((1 + d)/(1 − d))r1 v  a4 = r12 nh÷ ¢ t½nh ð tr¶n; t÷ìng tü th¼ ph÷ìng tr¼nh ÷íng cong E 00 trð th nh d/(1 − d)v 2 = u3 + 2((1 + d)/(1 − d))u2 + u.
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài Chính Ngân Hàng
172 tài liệu
838 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2