Tạp Chí Epsilon Số 9 - 123doc

, n − 1 phép cộng điểm P , cho đến khi tổng bằng Q , tuy nhiên có một số thuật toán tối ưu hơn để tìm n nhưng vẫn không thể giải được bài toán này trong thời gian đa thức vì thế dựa vào [r]

VÀ PHÉP BIẾN ĐỔI MELLIN

Ngô Bảo Châu

GIẢI NOBEL CỦA EINSTEIN HAY LÀ

SÓNG ĐIỆN THOẠI CÓ GÂY UNG THƯ HAY KHÔNG

Đàm Thanh Sơn

VÀ CÁC CHUYÊN MỤC KHÁC

DIOPHANTUS

Không có gì gần với thực tiễn hơn là một lí thuyết đẹp”

ISAAC NEWTON

Trần Nam Dũng

BIÊN TẬP VIÊN:

Võ Quốc Bá CẩnTrần Quang HùngNguyễn Văn HuyệnNguyễn Tiến Lâm

Lê Phúc LữNgô Quang DươngNguyễn Tất ThuĐặng Nguyễn Đức Tiến

tháng 6 - 2016

NO

09

LỜI NGỎ CHO EPSILON SỐ 9

Ban Biên tập Epsilon

Epsilon số 9, ra mắt vào tháng 6, 2016 kỷ niệm chặng đường một năm rưỡi đầy nỗ lực của BanBiên tập, các tác giả và cộng tác viên cũng như đầy ân tình từ phía độc giả đã ủng hộ chúng tôisuốt từ buổi ban đầu

Số tháng 9 đến được với các bạn cũng là thời điểm mùa hè bắt đầu rộn rã Những kỳ nghỉ vẫygọi và hoa phượng giăng đầy sân trường, lớp học, sắc đỏ lan khắp nắng, khắp những con đườngkhiến bất kì ai vô tình lướt ngang qua đều man mác biết bao hoài niệm Không khí tháng sáu

đã làm sống lại trong chúng tôi, những người thực hiện Epsilon, rất nhiều ký ức đẹp đẽ Vì vậychúng tôi muốn dành lần ra mắt này để giới thiệu về chủ đề Trung học Cơ sở

Bên cạnh những chuyên mục định kỳ, các đề tài và kiến thức toán trung học cơ sở sẽ lần lượtđược trình bày trong số tạp chí mùa hè này

Ban biên tập và các cộng tác viên hy vọng rằng, Epsilon số 9 sẽ góp thêm niềm vui học tập vàomùa hè tràn ngập niềm vui của các em học sinh, cũng như làm sống lại ký ức một thuở bảng đen,mực tím với những độc giả đã qua tuổi hoa niên

Trân trọng

Ban Biên tập Epsilon

Ban Biên tập Epsilon

Lời ngỏ cho Epsilon số 9 3

Hà Huy Khoái

Ích gì, toán học? 5

Phùng Hồ Hải

Hàm Moebius và định lý phần dư Trung Hoa 13

Ngô Bảo Châu

Dẫn nhập về hàm zeta Riemann và phép biến đổi Mellin 15

Đinh Trung Hòa

About means of non-negative numbers and positive definite matrices 67

Trịnh Huy Vũ

Điểm Kosnita và một số đường thẳng đi qua nó 73

Tạp chí Epsilon, Số 09, 06/2016

Trần Quang Hùng, Dương Ánh Ngọc

Định lý Sawayama và Thébault trong các bài toán hình học thi Olympic 91

Lê Phúc Lữ

Về bài toán tam giác 80-80-20 115

Nguyễn Tài Chung

Sử dụng tổng tích phân để tính giới hạn dãy số 121

tổ chức đó là cần thiết, rằng nó có ích Vậy nên câu hỏi “Ích gì, Chương trình quốc gia phát triển

Toán học?”, “Ích gì, VIASM?”, nếu không được phát biểu một cách công khai, thì chắc chắncũng lởn vởn trong đầu không ít người, như nó đã từng được đặt lên bàn của những nhà hoạchđịnh chính sách, của Bộ Tài chính, Bộ Giáo dục và Đào tạo

Vậy nên, khi được đề nghị làm một “bài giảng đại chúng”, tôi đã chọn đề tài “Ích gì, Toán học?”

Mà người “mách nước” cho tôi chọn đề tài đó lại không là một nhà toán học, mà là Chế LanViên! Hình như ông cũng đã từng trăn trở với câu hỏi “Ích gì Thơ ca? Ích gì, Nghệ thuật?”

Ích gì?

Chế Lan Viên – Di cảo

Khéo rồi mất giống bò sữa, hoạ mi, ngựa đua, gà chọi

Khó gì? Ta không giữ, không nuôi thì nó mất

Giống các nhà thơ cũng vậy

Tuyết trên non cao không ai thấy,

Giống nàng tiên, ông Bụt hiện trong mơ

Mà chả cần ai giết

Chỉ thôi yêu là nó chết

Chỉ cần bâng quơ, vu vơ đặt ra câu hỏi

Trịnh trọng cái bâng quơ, vu vơ ấy

Hỏi rằng: Ích gì họa mi?

gì họa mi và giấc mơ? Với tôi, bài thơ trên còn thiếu một câu: Ích gì, Toán học?

2 Đối tượng của toán học: Tìm về cội nguồn

Lo lắng như Chế Lan Viên cũng phải, nhưng làm sao có thể lảng tránh câu hỏi “Ích gì”? Nhất làđối với Toán học, khi nhìn sang “bên cạnh”, hình như chưa có ai đặt ra câu hỏi: “Ích gì, Vật lý?Ích gì, Sinh học?”

Ích gì, Vật lý?Dễ trả lời thôi, vì vật lý học nghiên cứu vật chất và chuyển động của chúng trongkhông gian và thời gian Có ai lại không cần những kiến thức đó?

Ích gì, Sinh học?Dễ trả lời thôi, vì sinh học nghiên cứu các cơ thể sống và tương tác của chúngvới môi trường Có ai lại không cần những kiến thức đó?

Nhưng “Ích gì, Toán học? Toán học nghiên cứu cái gì?” thì lại là câu hỏi không dễ trả lời Để

hiểu đối tượng của Toán học, phải tìm về cội nguồn của nó Tức là phải tìm đến “Cơ sở” củaEuclid Trước khi cuốn “Cơ sở” ra đời (khoảng 300 năm trước Công nguyên), Toán học chưaphải là một khoa học độc lập Nó “lẫn” vào Triết học và Thiên văn học

Bắt đầu với những “định nghĩa cơ bản” về những đối tượng của Toán học, trong Cơ sở - cuốn I,Euclid đưa ra 23 định nghĩa cơ bản Xin nhắc lại ba trong số đó, định nghĩa thứ 1, 2 và 15 :α΄v Σημεῖόν ἐστιν, οὗ μέρος οὐθέν

β΄v Γραμμὴ δὲ μῆκος ἀπλατές

ιε΄v Κύκλος ἐστὶ σχῆμα ἐπίπεδον ὑπὸ μιᾶς γραμμῆς περιεχόμενον [ἣ καλεῖται περιφέρεια],πρὸς ἣν ἀφ΄ ἑνὸς σημείου τῶν ἐντὸς τοῦ σχήματος κειμένων πᾶσαι αἱ προσπίπτουσαιεὐθεῖαι [πρὸς τὴν τοῦ κύκλου περιφέρειαν] ἴσαι ἀλλήλαις εἰσίν

Dịch nghĩa

1 Điểm là một cái không có kích thước.

2 Đường là cái chỉ có chiều dài, không có chiều rộng.

15 Đường tròn là một hình phẳng chỉ gồm một đường duy nhất (gọi là chu vi), (sao cho) mọi

đường thẳng xuất phát (đến chu vi) từ một điểm nằm bên trong hình đều bằng nhau.

Như vậy, Toán học nghiên cứu những sự vật không hề tồn tại trong thực tế! Không thể tìm ramột “vật thể” không có kích thước, cũng như không thể tìm ra một cái gì đó không có chiều rộng

Và hiển nhiên, cái đường tròn “lý tưởng” của Toán học không thể tồn tại, người ta chỉ nhìn thấy

“vành nón tròn, mặt trời tròn”, hay “khuôn trăng đầy đặn” của Thuý Vân tròn như Mặt trăng!Vậy thì, ích gì, cái khoa học nghiên cứu những sự vật không hề tồn tại? Tìm về cội nguồn lạikhông cho ta câu trả lời, mà ngược lại, hình như còn làm ta bối rối thêm Nhưng, phải chăngnhững gì không tồn tại trong thực tế đều vô ích, đều cần phải biến mất sau câu hỏi “Ích gì?” Tathử tìm về Pablo Picasso, hoạ sĩ vĩ đại của thế kỷ XX Người ta nhìn thấy Picaso không chỉ trongnhững bức tranh ông để lại, mà cả trong những vật dụng hàng ngày Ông làm thay đổi quan niệmcủa chúng ta về cái đẹp Và điều kỳ diệu đó Picasso làm được, khi đưa ta về tận cùng của bảnchất sự vật

Một trong những đề tài thường gặp trong tranh Picasso là bò tót Con bò tót, đấu bò gần như làbiểu tượng của Tây Ban Nha Nhưng trong tranh Picasso, bò tót tượng trưng cho sức mạnh u tốicủa chủ nghĩa phát xít Franco những năm 30 của thế kỷ trước Ta hãy xem cách Picasso vẽ bò tót:

Như vậy, Picaso đã đi từ “con bò tót” đến “khái niệm bò”! Con bò “khái niệm” của Picasso với

bộ sừng đáng sợ, với bộ óc nhỏ như một “điểm” của Euclid, đã thể hiện đầy đủ cái sức mạnh ngumuội của chủ nghĩa phát xít những năm 30 Hơn hai ngàn năm trước, Euclid cũng bằng cách đó

đi từ “mặt trời tròn, vành trăng tròn” đến cái “đường tròn” của toán học

Cái không có trong thế giới thực tại lại mô tả chân thực nhất thế giới thực tại, vì nó đưa ta về vớibản chất Phải chăng đó là lý do giải thích việc các lý thuyết toán học cho ta công cụ mô tả chínhxác thế giới tự nhiên Nói như Galilei, Thượng đế viết nên tự nhiên bằng ngôn ngữ của toán học

3 Nghề làm Toán

Nhiều người hỏi bác Tôm (René Thom, nhà toán học Pháp, giải thưởng Fields) về nghề làm Toán.Thấy khó nói quá, bác bèn kể chuyện săn rồng Chuyện rằng, xưa bên Trung Quốc, có anh chànghọc nghề đi săn Anh chẳng chịu học săn hổ, săn lợn, mà lại học nghề săn Rồng! Nghề này khólắm, phải thực tập nhiều Bởi thế nên khi anh ta thạo nghề thì trên thế gian chẳng còn lấy mộtcon Rồng nào! Có người hỏi: Bây giờ sống bằng nghề gì? Đáp: Đi dạy nghề săn Rồng! Bác Tômnói: Làm Toán tức là đi dạy nghề săn Rồng vậy! (thảo nào chẳng có chú Rồng nào dám bén mảngđến nhà bác Tôm!)

Thế thì, làng nước đâu có cần cái anh săn Rồng ấy Có còn Rồng nữa đâu mà học nghề săn rồng?

Ấy chết, đừng vội nói thế Rồng thì chẳng còn, nhưng có khi vẫn phải học nghề săn Rồng đấy.Nếu anh đi học nghề săn lợn thì chắc gì đã bắn được hổ? Mà học nghề săn hổ thì chắc gì bắnđược voi? Nhưng nếu đã thạo nghề săn Rồng thì hổ, báo, sư tử, voi, chắc chắn đều săn đượctuốt! Này nhé, Rồng có thân như cá sấu, móng vuốt như hổ, đầu sư tử, ẩn hiện như trăn, vậy màcòn không thoát được tay anh săn Rồng, thì chẳng nói gì đến hổ, báo, voi, trăn, mà sau này có

“nhân bản” ra con nào nữa, anh ta cũng chẳng sợ! Thành ra, đã định học nghề đi săn thì hãy cứhọc nghề săn Rồng!

Từ cá sấu, hổ, sư tử, trăn, người xưa “trừu tượng hóa” thành con Rồng Cũng như thế, từ thựctiễn, người ta trừu tượng hóa thành Toán học Câu chuyện đơn giản của bác Tôm mà thâu tómđược cả cái mạnh, và cái yếu, của Toán học là vậy

Khi đã trừu tượng hoá để tìm đến bản chất, Toán học không phải bao giờ cũng dễ dàng trở về vớithực tại, vốn là nơi xuất phát của nó Thậm chí, người ta còn nghi ngờ cái khả năng nó có thểquay về với thực tại

Bởi thế nên mới có người hỏi khích bác Tôm: “Mấy cái anh làm Toán gàn dở bịa ra những phươngtrình, vi phân, tích phân, gì gì nữa nhỉ, thực tế làm gì có? Bọn họ chỉ ngồi chơi cái trò chơi trítuệ đấy thôi”! Bác Tôm hỏi lại: “Này nhé, nếu anh đánh rơi cái nhẫn trong góc nhà kho bừa bộn,tối om, mà lại không có đèn, thì anh tìm nó ở đâu”? Anh chàng nọ ngạc nhiên: “Hỏi lạ nhỉ, thìchui vào đó mà tìm chứ ở đâu nữa”! Bác Tôm cười: “Thế thì có khi mấy tháng trời vẫn chưa tìm

ra Cứ như tôi thì tôi sẽ chạy ra dưới ngọn đèn sáng mà tìm vậy”! Anh chàng được mẻ cười vỡbụng: “Mấy anh làm Toán gàn quá đi mất, biết tỏng tòng tong là nhẫn rơi trong góc nhà kho, màlại ra dưới đèn tìm thì có mà suốt đời tìm cũng không thấy” Ấy vậy mà cái anh đồ (Toán) gàn dởchẳng dại lắm đâu Này nhé, anh ta cầm lấy chiếc nhẫn, đứng dưới ngọn đèn mà thả cho nó rơi.Tất nhiên là tìm lại được ngay (ở đó sáng lắm) Cứ như thế mười lần, hai mươi lần, một trăm lần, anh ta phát hiện ra quy luật: Khi rơi thì cái nhẫn nói chung chạy theo hướng nào Bởi thế lúcvào góc nhà kho tối om, anh ta tìm ra ngay chiếc nhẫn Mà không chỉ chiếc nhẫn ấy, nhà kho ấy,

mà dù chiếc nhẫn khác, rơi ở nhà kho khác cũng tối om như vậy, thì đối với anh làm Toán, tìm nócũng chẳng khó khăn gì!

Tạp chí Epsilon, Số 09, 06/2016

Các phương trình, các lý thuyết Toán học cũng như ngọn đèn của bác Tôm vậy Có nó, người tamới “làm Toán” được, tức là mới tìm ra quy luật của sự vật Muốn trở về được với thực tiễn thìtrước tiên phải biết rời xa thực tiễn, để không còn bị che lấp bởi cái rườm rà, không bản chất củađời thường

Ba trăm năm trước bác Tôm, Newton đã từng nói: “Không có gì gần với thực tiễn hơn là một líthuyết đẹp!”

4 Ứng dụng Toán học

Nhưng cái câu hỏi “Ích gì, Toán học?” vẫn cứ lởn vởn đâu đây, nhất là khi nhìn những nhà toánhọc hàng đầu nghiên cứu những thứ hoàn toàn “xa rời thực tế” , mà ngay cả bản thân họ cũngchưa biết mình sẽ đi đến đâu

Người ta thường hỏi nhà Toán học: Lí thuyết của anh ứng dụng vào đâu? Không phải lúc nàocũng có câu trả lời Vào thế kỉ thứ III trước Công nguyên, nếu ai đó hỏi Apolonius rằng nghiêncứu các đường cônic (nhận được bằng cách cắt mặt nón bởi mặt phẳng) để làm gì, thì chắcApolonius không trả lời được Ông ta chỉ nghiên cứu các đường cônic vì thấy là chúng “đẹp”.Không chỉ Apolonius không thể trả lời, mà hơn chục thế kỉ sau cũng không ai trả lời được Phảichờ đến Kepler và Newton, tức là 20 thế kỉ sau, người ta mới biết ông già Apolonius đã từng làmtrò chơi với các quỹ đạo chuyển động của các hành tinh! Chính vì bị ám ảnh bởi các đường cônicngay từ thuở ấu thơ mà Kepler đã nghi ngờ kết luận của những người đi trước về quỹ đạo tròn,

và đưa ra giả thuyết quỹ đạo đó là đường ellip, với hai tiêu cự rất gần nhau Giả thuyết đã đượcNewton chứng minh, với định luật vạn vật hấp dẫn “Cái đẹp”, từ chỗ không biết để làm gì, đãtìm thấy một ứng dụng vào loại vĩ đại nhất trong lịch sử, sau hơn hai ngàn năm

Bác Tôm có lần nói: Đối với những người mở đường, đừng hỏi họ đi đâu, khi người ta biết mình

đi đâu, người ta không đi được xa “quand on sait òu va, on va pas loin” Thật thế, nếu anh định

đi đến Thành phố Hồ Chí Minh thì chắc là anh cũng chỉ đi đến Cà Mau là cùng Ngay như cáianh Armstrong, biết mình đi đến Mặt trăng thì cũng chỉ đến đó thôi, rồi về Còn bác Tôm chẳngbiết mình đi đâu, nên bác có thể đi xa hơn, đến tận sao Hỏa, hay những miền đất mới của khoahọc Và chúng ta, dù không đi xa được như bác Tôm, nhưng muốn ngày mai có bát cơm ngon, thìđừng quá sốt ruột nếu hôm nay chưa “ra ngô, ra khoai” gì! Còn nếu muốn “ra ngô, ra khoai”ngay thì có khi cả đời chỉ biết ăn ngô, ăn khoai!

Vậy nhưng, nếu các lý thuyết Toán học đều phải cần đến 2000 năm sau mới có ứng dụng, thì câuhỏi “Ích gì, Toán học?” sẽ dễ nhận được câu trả lời là “Vô ích”! Dù “nhìn xa” đến mấy, người tacũng khó nhìn đến tận 2000 năm sau!

Nhưng Toán học đi vào thực tiễn với những con đường khác nhau Có khi 2000 năm, có khi chỉhai năm, thậm chí chỉ cần hai tháng! Ví dụ nổi tiếng là những hệ mật mã khoá công khai, như hệ

mã RSA hay hệ mã dùng đường cong elliptic Từ trang giấy của nhà nghiên cứu toán học đếnứng dụng vào cái điện thoại thông minh hay cái thẻ tín dụng gần như là tức thời

Không chỉ là những ứng dụng dễ nhìn thấy, Toán học giúp cho con người luôn hướng đến sự đơngiản trong tư duy Tư duy Toán học chính là lối tư duy loại bỏ tất cả những gì không cần thiết,những gì rườm rà Sự tối giản chính là một tiêu chuẩn của sự tối ưu, và nhiều khi, còn là tiêuchuẩn của cái đẹp Một lần nữa, Toán học lại rất gần với Nghệ thuật Nhà điêu khắc vĩ đại ngườiPháp Auguste Rodin (1840 − 1917) đã sáng tạo nên pho tượng bất hủ Le Penseur (Người suytư), khắc họa hình ảnh một con người mà sự suy nghĩ căng thẳng hiện ra trên từng thớ thịt Có

người hỏi Rodin: “Làm thế nào mà ông có thể tạc nên pho tượng tuyệt vời đến vậy?” Rodin trảlời: “Đơn giản thôi, tôi lấy một khối đá, và thấy cái gì thừa thì đẽo nó đi!”.

Nhưng, tại sao sau tất cả những điều đã nói, vẫn tồn tại dai dẳng câu hỏi: ”Ích gì, Toán học”?Người ta hàng ngày dùng điện thoại di động để nói đủ thứ chuyện, đôi khi là để nói về cái sự

vô ích của Toán học Người ta hàng ngày dùng thẻ tín dụng để chuyển tiền, rút tiền Nhưng sẽkhông có điện thoại thông minh, không có thẻ tín dụng nếu không có mật mã khoá công khai,không có Toán học Vậy nhưng người ta có thể vẫn rất ngại dùng tiền đó đầu tư cho Toán học, vì

“Ích gì, Toán học?” Khi dùng điện thoại, khi rút tiền, không ai thấy “tích phân, vi phân, tổ hợphay số học” trong đó Nói khác đi, Toán học đã đến mức “trong suốt” đối với người sử dụng nó(tất nhiên chỉ khi đó nó mới được dùng cho tất cả mọi người)

Xem ra, sự “trong suốt” đôi khi lại che khuất tầm nhìn hơn ngọn núi!

Năm 1674 Mayow tìm thấy trong khí quyển một chất giúp cho sự sống Năm 1773 Karl Scheelelần đầu tiên cô lập được chất khí đó Antoine Lavoisier lặp lại thí nghiệm đó của Scheele và gọi

đó là “oxygen” Như vậy, oxy được “tìm ra” khá muộn Tại sao? Vì nó trong suốt Người ta hầunhư không nhận thấy mình đang cần đến oxy Và không chịu bỏ tiền ra “cho nó” Phải đến khicon người nhìn thấy những hình ảnh sau đây:

Đó là không khí ở Bắc Kinh Nó không còn trong suốt nữa Và người ta buộc phải nhìn thấy nó,buộc phải họp nhau ở Rio de Janeiro, ở Kyoto, ở Paris để bàn nhau tìm cách bỏ tiền ra làm cho

nó trong suốt trở lại Giá như người ta nhìn thấy sự cần thiết từ khi nó còn trong suốt!

5 “Tính” và “Toán”

Một người bạn của bác Tôm, ông F.Hirzebruch, khi trả lời phỏng vấn của các nhà báo, trên cương

vị là Chủ tịch đầu tiên của Hội Toán học Châu Âu, đã nói: “Người ta thường hay nhấn mạnh vai

Tạp chí Epsilon, Số 09, 06/2016

trò của Toán học trong phát triển công nghệ, nhưng tôi nghĩ rằng, sẽ đến lúc công nghệ phát triển

để giải phóng con người, cho họ thời gian quay về với thơ ca, âm nhạc và Toán học” Phải chăng,Hirzebruch muốn ám chỉ rằng, trong Toán học có hai phần: “Tính” và “toán”

Nếu như tính rất cần thiết cho công nghệ, thì Toán, ngoài chức năng phát triển phần tính ra, còngóp phần làm nên Con Người, cũng giống như âm nhạc, nghệ thuật và thơ ca

Nhưng có thể 5 năm nữa, trong dịp kỷ niệm 10 năm của VIASM, chúng ta lại sẽ phải bàn về câuhỏi: “Ích gì, Toán học?”

Phải chăng đó là câu hỏi vĩnh cửu, song hành với Toán học từ khi nó ra đời? Cũng như câu hỏitương tự cũng song hành cùng Nghệ thuật và Thơ ca

HÀM MOEBIUS VÀ ĐỊNH LÝ PHẦN DƯ

TRUNG HOA

Phùng Hồ Hải(Viện Toán học Việt Nam)

Câu lạc bộ (CLB) Toán học Viện toán học được thành lập cách đây 5 năm Đầu tiên CLBsinh hoạt sáng chủ nhật mỗi tuần với các bài giảng toán của các GS, TS, các thầy giáo chuyêntoán dành cho học sinh THPT Sau đó để tạo điều kiện cho các học sinh tỉnh xa, CLB đã tổchức những đợt giảng dài ngày dưới hình thức trường đông, trường hè, trường xuân Gần đâyCLB toán học Viện toán học đã tổ chức thêm các lớp học dành cho học sinh THCS với mụctiêu định hướng và tạo nguồn Epsilon xin giới thiệu với bạn đọc bài viết của GS Phùng HồHải kể lại buổi dạy ngẫu hứng của mình vào chiều thứ ba 7/6/2016 vừa qua

Bài viết được lấy từ trang facebook cá nhân của giáo sư Phùng Hồ Hải

Để hiểu nội dung bài viết, ta cần đến định nghĩa của hàm Moebius Hàm Moebius µ(n) được xácđịnh trên tập hợp các số nguyên dương và nhận giá trị trong tập hợp {−1, 0, 1} Ta có µ(1) = 1.Khi n > 1, µ(n) sẽ bằng 0 nếu n có ít nhất một ước chính phương lớn hơn 1 Trong trường hợp

n không có ước chính phương (lớn hơn 1) thì với n = p1p2· · · prlà tích của các số nguyên tốphân biệt ta sẽ có µ(n) = (−1)r Ví dụ ta có bảng giá trị của hàm Moebius với n 6 15

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

µ(n) 1 −1 −1 0 −1 1 −1 0 0 1 −1 0 −1 1 1

Lâu rồi không report về Math Circle Hôm nay tôi đã có một buổi dạy khá ngẫu hứng HàmMoebius đã được nhắc tới vài lần Hôm nay tôi muốn thuyết phục các bạn trong lớp rằng hàmnày bằng 0 tại “phần lớn” các số tự nhiên Nói phải có sách, mách phải có chứng Ta sẽ thử liệt

kê xem hàm sẽ triệt tiêu tại những giá trị nào

Ta biết rằng hàm sẽ triệt tiêu tại n nếu n chia hết cho bình phương một số nguyên tố Như vậytrong 10 số tự nhiên đầu tiên, hàm sẽ triệt tiêu tại 4, 8, 9 - ba số

Trong 10 số tự nhiên tiếp theo hàm sẽ triệt tiêu tại 12, 16, 18, 20 - bốn số Tình hình sau đó kém

đi một chút: 32, 36, 40 Rồi lại khá lến: 44, 45, 48, 49, 50

Dù sao thì các bạn trong lớp cũng thấy rằng tình hình có chiều hướng tốt lên, nghĩa là càng ngàythì tỷ lệ các số mà tại đó hàm triệt tiêu càng tăng Đặc biệt ta thấy xuất hiện ba số liên tiếp mà tại

Câu hỏi có vẻ hơi khó

- Hay là thế này: Chứng minh rằng tồn tại vô hạn cặp hai số tự nhiên liên tiếp mà tại đó hàmMoebius triệt tiêu

Ngay lập tức có lời giải: xét hai số a2− 1 và a2, hàm hiển nhiên triệt tiêu tại a2, chỉ cần chọn a

Thầy giải thích cho các bạn rằng a3 − 1 chia hết cho 4 khi và chỉ khi a − 1 chia hết cho 4 còn

a3+ 1 chia hết cho 9 khi và chỉ khi a + 1 chia hết cho 3 Vậy bài toán là những số a nào thỏamãn các điều kiện này?

Đây là một bài toán dễ đối với các bạn, câu trả lời có ngay: a chia 12 dư 5, hay a = 12k + 5

- Bài toán tìm a để a đồng dư với 3 mod 4 và đồng dư với 2 mod 3 chính là bài toán “giải hệphương trình đồng dư bậc nhất”, thầy giải thích cho các bạn Mọi người rất phấn khích

- Bây giờ ta hãy xem nguyên tắc giải hệ như thế nào: Trước hết ta tìm một “nghiệm riêng”, chính

là số 5, từ đó ta chỉ cần cộng thêm “nghiệm tổng quát”, là số 12 - bội chung nhỏ nhất của 3 và 4.Quá dễ hiểu đối với các bạn học sinh

- Bây giờ ta hãy xét một hệ 3 phương trình xem sao Chẳng hạn: a đồng dư với 1 mod 3, đồng dưvới 2 mod 4 và đồng dư với 4 mod 5

a = 34 + 60k, chỉ trong vài phút các bạn đã có câu trả lời

- Chúng ta có thể giải hệ trên “dần dần”, xét hai phương trình đầu tiên ta sẽ có nghiệm: a đồng

dư với 10 mod 12, sau đó ta lại xét phương trình này cùng với phương trình thứ ba, a đồng dư với

4 mod 5, để suy ra nghiệm bằng phương pháp tương tự

- Bằng cách này ta chứng minh được Định lý phần dư Trung Hoa: Mọi hệ phương trình đồng dưbậc nhất với các modun đôi một nguyên tố cùng nhau đều có nghiệm Chỉ cần xét dần dần, mỗilần hai phương trình

- Bạn nào biết tại sao hệ hai phương trình đồng dư bậc nhất với modun nguyên tố cùng nhau luôn

có nghiệm?

- Sử dụng hệ thức Bezout, một bạn trả lời ngay lập tức

Thế là định lý phần dư Trung Hoa được chứng minh, ít nhất là “về nguyên tắc” Trở lại bài toánban đầu, phương pháp sử dụng a3 rồi thêm bớt 1 không thể cho ta lời giải cho câu hỏi: Tìm 10 số

tự nhiên liên tiếp mà tại đó hàm Moebius triệt tiêu Đó là vì phương pháp xây dựng của ta khôngphù hợp Chúng ta có thể sử dụng Định lý phần dư Trung Hoa để có một cách xây dựng đơn giảnhơn nhiều Chỉ cần có 5 phút để một bạn có lời giải hoàn chỉnh cho bài toán này

DẪN NHẬP VỀ HÀM ZETA RIEMANN VÀ

PHÉP BIẾN ĐỔI MELLIN

Ngô Bảo Châu(Đại học Chicago)

Đọc lịch sử toán học ta thấy rằng trước đây thư tín là một phương tiện trao đổi thông tin toánhọc rất quan trọng Rất nhiều những ý tưởng, giả thuyết, dự đoán và cả những chứng minhhay phản ví dụ đã được trình bày lần đầu tiên ở trong những bức thư chứ không phải là ởtrong các tạp chí và cuốn sách Newton, Leibniz, Fermat, Euler, Gauss, Jacobi, Bernoulli,Mersenne, đều có những “công bố” ở dạng thư tín

Ngày nay, với những phương tiện giao tiếp hiện đại như blog, trang wordpress, archiv ta

có nhiều cách để “công bố” các ý tưởng hay tiền ấn phẩm của mình Tuy nhiên, trao đổi họcthuật bằng thư tín, email vẫn là một hình thức thông dụng và hiệu quả

Thông tin qua email có thể sẽ không hình thức và chặt chẽ như những bài báo, những cuốnsách, có nhiều ý tưởng còn thô ráp, nôm na, nhưng chính điều đó làm độc giả dễ đọc hơn,gần gũi hơn, dễ hiểu hơn

Chúng tôi xin giới thiệu với bạn đọc lá thư của GS Ngô Bảo Châu gửi cho GS Phùng HồHải nhân việc GS Hải muốn tổ chức một khóa học về hàm zeta và phép biến đổi Mellin đểchuẩn bị cho chuỗi bài giảng về lý thuyết biểu diễn của GS Ngô Bảo Châu và GS Phạm HữuTiệp vào tháng 8/2016

Dịch bởi Nguyễn Vũ Duy Linh và Trần Nam Dũng hiệu đính

From:

Đại Học CHICAGO

Khoa Toán

5734 University Avenue, Chicago IL 60637

Ngô Bảo Châu

To:

GS Phùng Hồ Hải

Viện Toán học Việt Nam

18 Hoàng Quốc Việt, Hà Nội

Ngày 5 tháng 5 năm 2016.Hải thân mến,

Tổ chức một seminar học tập về hàm zeta có vẻ là một ý tưởng tốt

Tôi thiết nghĩ nên mở đầu bằng một vài vấn đề rất căn bản của lý thuyết số giải tích Chúng tahãy xem xét một hàm số học tức là đơn thuần một dãy số a1, a2, được định nghĩa theo kiểu

số học nào đó Đây là một khái niệm trừu tượng và người ta không thể làm được gì ở mức độtrừu tượng như vậy Trên một phương diện khác, ta có rất nhiều ví dụ cụ thể:

1 an = 1,

2 an = µ(n) là hàm Moebius,

3 an = d(n) là số những ước số của n,

4 an = r(n) là số cách biểu diễn n như là tổng của hai bình phương,

5 an = 1 nếu n nguyên tố và bằng 0 nếu ngược lại,

6 an = log(p) nếu n là lũy thừa của p và 0 nếu ngược lại,

Mặc dầu những dãy số này rất bất thường, ngoại trừ dãy đầu tiên, tổng Cesaro a1+ a2+ · · · + an

có tính tiệm cận nào đó Chẳng hạn chúng ta xác định tính tiệm cận của dãy thứ 5, chúng ta thửtính số lượng số nguyên tố nhỏ hơn một số nào đó

Ước lượng tổng Cesaro của d(n) và r(n) là những vấn đề sơ cấp cổ điển trong lý thuyết số Đốivới r(n), đó là những bài toán về hình tròn Gauss: Có bao nhiêu điểm nguyên nằm trong hìnhtròn khi bán kính tiến về ∞ Bằng những lý luận sơ cấp như Gauss đã làm, chúng ta có

X

n<X

r(n) = πX + O(X1/2) (0.1)

Seminar có thể bắt đầu với bài toán này và người ta không cần có kiến thức để hiểu cách giải Nó

đã được giải thích rất kỹ lưỡng trong chương 6 của quyển “Nhập môn lý thuyết số giải tích” của

Chandrasekharan Tại chỗ này, ta cần đề cập rằng sai số O(X1/2) có thể cải thiện đáng kể nhờmột công cụ giải tích tốt hơn Chẳng hạn, nhờ công thức lấy tổng Poisson, người ta có thể đạtđược O(X1/3)

Cách truyền thống để hiểu tính tiệm cận của tổng Cesaro là tạo ra chuỗi Dirichlet

nn−shội tụ trên miền <(s) > 1

Có một vài thao tác mà chúng ta nên làm quen khi làm việc với chuỗi Dirichlet Chẳng hạn,trong bốn ví dụ đầu tiên, ancó tính chất nhân tính: amn = amanvới (m; n) = 1 Chuỗi Dirichlettương ứng có thể phân tích thành nhân tử thành tích Euler tức là tích của các thừa số đánh sốbằng số nguyên tố Chẳng hạn như:

Tạp chí Epsilon, Số 09, 06/2016

Những hằng đẳng thức này là hiển nhiên khi xem xét như là chuỗi Dirichlet hình thức Như làcác hàm phức, chúng có thể được chứng minh dễ dàng trên miền mà chuỗi Dirichlet hội tụ tuyệt

đối Tất cả những điều này được giải thích hoàn hảo trong chương 2 của quyển “Nhập môn lý

thuyết số giải tích” của Apostol

Một trong những hướng chính của lý thuyết số giải tích cổ điển là dẫn ra một ước lượng tiệm cậncủa tổng Cesaro từ những cực của chuỗi Dirichlet Đó chính là nội dung của định lý Tauberian.Một vấn đề khó chịu là có nhiều phiên bản của định lý Tauberian Phiên bản đơn giản nhất có thể

là định lý Wiener-Ikehara’s được giải thích trong chương 11 của Chandrasekharan chẳng hạn.Trong bất cứ trường hợp nào, định lý Tauberian cho ta biết một điều đại loại như sau: Giả sử rằngD(s, a) = P

nann−s có thể thác triển phân hình vượt qua đường thẳng <(s) = 1 − ε Giả sửrằng nó chỉ có một cực cấp 2 tại 2 và một cực cấp 1 tại 1 Khi đó biểu thức tiệm cận sẽ có dạng:

X

n<X

an = c2,2X2log(X) + c2,1X2 + c1,1X + · · · (0.5)

trong đó c2,2, c2,1là hệ số Laurent của khai triển D(a, s) thành chuỗi Laurent tại s = 2 Ở đây

số mũ 2 trong X2tương ứng với vị trí của cực tại 2, số hạng log(X) xuất hiện là vì cực tại 2 cócấp 2

Mất nhiều thời gian cho các định lý Tauberian cũng không hay lắm vì trên một phương diện nóchỉ là vấn đề kỹ thuật, và trên một phương diện khác phần giải tích ít ỏi cần dùng để chứng minhcác định lý Tauberian có vẻ là không thích đáng xét trên quan điểm lý thuyết số

Nếu như tôi không lầm thì có một cách tiếp cận tốt hơn sử dụng cái gọi là “tổng trơn” Người ta

có thể đọc bài post của Emmanuel Kowalski trên blog của ông ta để được giới thiệu về tổng trơn:

https://blogs.ethz.ch/kowalski/smoothing-sums-wiki-page/

Cách tốt nhất để khởi đầu với tổng trơn là quay về với bài toán hình tròn Gauss Chúng ta phátbiểu lại bài toán hình tròn Gauss tổng quát như sau: Cho hàm φ : R2 → C, chẳng hạn như hàmđặc trưng của đĩa đơn vị, chúng ta muốn biết tiệm cận của

Điểm chính yếu của chiến lược “tổng trơn” là nhận ra rằng thay vì làm việc với một hàm thử

“thô”, như là hàm đặc trưng của đĩa đơn vị có những bước nhảy thô trên chu vi của đường tròn,

tốt hơn chúng ta làm việc với những hàm thử trơn với giả thiết compact Đối với những hàm trơn,tiệm cận củaP

n∈Z 2φ(tn) là hệ quả trực tiếp của công thức lấy tổng Poisson:

trong đó ˆφ là biến đổi Fourier của φ Biến đổi Fourier ˆφ không còn hỗ trợ compact nữa, nhưngvẫn một hàm giảm nhanh trong không gian Schwartz Ở vế phải, khi t−1 → ∞, mọi số hạng,ngoại trừ n = 0, giảm rất nhanh Do vậy ta có

X

n∈Z 2

φ(tn) = t−1φ(0) + O(tˆ r), với mọi r (0.8)

Số hạng ˆφ tương ứng với diện tích của đĩa, nơi xuất hiện của số π trong bài toán hình tròn Gauss.Mặc dù vậy, nếu chúng ta áp dụng trực tiếp công thức lấy tổng Poisson cho hàm đặc trưng củađĩa đơn vị, chúng ta sẽ gặp rắc rối to vì những điểm kỳ dị lớn của φ sẽ dẫn tới sự tăng nhanh củabiến đổi Fourier ˆφ Tốt hơn chúng ta xấp xỉ hàm đặc trưng của đĩa bằng một hàm trơn nào đó và

cố gắng khống chế sai số Làm như vậy theo một đường lối thông minh, chúng ta nhận được sai

số O(t−1/3) Tôi nhớ đã thấy lối giải thích rất đẹp này ở đâu đó nhưng tôi không tìm thấy nó nữa.Nhưng nó sẽ là một bài tập thật tốt cho những ai tham dự seminar của anh

Một bài học rút ra từ phép giải bài toán hình tròn Gauss là chúng ta có thể quên đi hàm thử thô

và thay vào đó chỉ làm việc một hàm trơn Phần lý thuyết sẽ hoàn toàn nói về hàm thử trơn.Đối với mỗi bài toán cụ thể, người ta phải cất công xấp xỉ một hàm thử thô bằng những hàm trơn.Điều này cũng cho ta một hình dung tốt hơn về các hàm số học và các chuỗi Dirichlet theo nghĩacác phân bố Mỗi dãy antăng vừa phải có thể xem như phân bố

Người ta có thể định nghĩa biến đổi Mellin của một phân bố loại a như sau Đối với một hàmSchwartz φ, tích chập a ∗ φ lại là một hàm Schwartz Cả hai biến đổi Mellin của φ và a ∗ φ vẫncòn là hàm trơn với tiệm cận vừa phải Khi đó chúng ta có thể định nghĩa biến đổi Mellin M (φ)

và M (a ∗ φ) rồi cho M (a) = M (a ∗ φ)/M (φ)

Ý tưởng này có vẻ được nhiều người biết, mặc dầu tôi không nhớ rõ nó được giải thích trongtài liệu nào Ít nhất nó được giải thích trong các bức thư ngắn tôi gởi cho anh trước đây vềhàm ς Nếu không thì anh có thể đọc về phép biến đổi Mellin trong bài giảng của Igusatrong TIFR:http://www.math.tifr.res.in/publ/ln/tifr59.pdf.Zagiercóviết bài giới thiệu sơ cấp hơn:http://people.mpim-bonn.mpg.de/zagier/files/tex/MellinTransform/fulltext.pdf

Bây giờ người ta có thể tiếp cận hàm Riemann zeta theo lối phân bố Công thức lấy tổng Poisson

có thể được phát biểu như sau: phân bố lược Dirac φ 7→ σZ(φ) = P

n∈Z

φ(n), là phép biến đổiFourier của chính nó Bây giờ tính biến đổi Mellin và biến đổi Fourier của σZ ta có phương trìnhhàm của hàm Riemann zeta Trong quá trình tính toán, người ta phải chứng minh rằng ς có tháctriển phân hình dựa trên sự tác động lẫn nhau của phép biến đổi Mellin, tiệm cận của tổng Cesaro

và công thức lấy tổng Poisson

Một bài tập rất tốt là thử tổng quát hóa lý thuyết của các hàm zeta Riemann như đã giải thích

ở trên đối với mở rộng bậc hai F của Q Chẳng hạn trong trường hợp tách được F = Q × Q,chúng ta cần phải quay trở lại dãy an= d(n) Nếu như F = Q[i] là trường hữu tỉ Gauss, chúng

ta cần phải quay trở lại bài toán hình tròn Gauss

Tại điểm này người ta có thể hỏi, phải chăng phép lấy tổng Poisson là tất cả những gì chúng tacần để ước lượng các tổng Cesaro? Xét cho cùng, chúng ta cần chuỗi Dirichlet để làm gì? Câu

Tạp chí Epsilon, Số 09, 06/2016

trả lời là phép lấy tổng Poisson làm việc với tổng có chỉ số nguyên và không thể làm gì với tổng

có chỉ số là số nguyên tố Chẳng hạn phép lấy tổng Poisson một mình nó không thể làm việc vớicác dãy (0.5) và (0.6) Nói cách khác phép lấy tổng Poisson một mình nó không thể chứng minhđược định lý số nguyên tố

Đối với định lý số nguyên tố, nói chung chúng ta cần phải xử lý như sau: Chúng ta bắt đầu vớidãy (0.1), chúng ta tạo chuỗi Dirichlet chính là hàm zeta Riemann Chúng ta dùng công thức lấytổng Poisson để chứng minh rằng ς có thác triển phân hình và phương trình hàm Chúng ta suy rarằng d log ς cũng có thác triển phân hình và phương trình hàm Giờ đây d log ς là chuỗi Dirichletcủa dãy (0.6) Chúng ta hoàn tất công việc nếu chúng ta biết các cực của d log ς Nhưng các cựccủa d log ς căn bản là các không điểm của ς, đó chính là lý do chúng ta muốn định vị các khôngđiểm của ς

Chẳng hạn, định lý số nguyên tố dựa trên sự kiện là ς không có không điểm trên một miền mởnào đó chứa <(s) > 1, điều này được chứng minh bởi Hadamard cả trăm năm về trước

Nếu anh có đủ thời gian và can đảm, anh hãy nghiên cứu lại tất cả những thứ đó cũng như định lýDirichlet về số nguyên tố trong cấp số cộng Đó là chỗ mà chúng ta cần một luật thuận nghịchnào đó Nhưng anh không cần bắt đầu với luật thuận nghịch vì thật sự ra nó không phải là hướngchính trong sự phát triển ban đầu của hàm zeta, ít ra theo ý kiến của tôi Tất nhiên về sau luậtthuận nghịch sẽ trộn lẫn rất nhiều vào lý thuyết của hàm zeta cũng như trong chương trình củaLanglands, nhưng mỗi lúc học một thứ thì vẫn dễ dàng hơn

Chúc anh mọi điều tốt lành

Châu

GIẢI NOBEL CỦA EINSTEIN HAY LÀ SÓNG ĐIỆN THOẠI CÓ GÂY UNG THƯ HAY KHÔNG

(Đàm Thanh Sơn - ĐH Chicago)

Bài viết được tham khảo từblogcủa giáo sư Đàm Thanh Sơn

Albert Einstein có lẽ là nhà vật lý nổi tiếng nhất từ trước đến nay Công chúng thường biết đếnông ta như người khám phá ra thuyết tương đối, làm thay đổi quan niệm của chúng ta về khônggian và thời gian Thuyết tương đối bao gồm thuyết tương đối hẹp, được Einstein tìm ra năm

1905 và thuyết tương đối rộng được ông ta tìm ra 10 năm sau Tuy nhiên có thể không phải aicũng biết là giải thưởng Nobel về vật lý năm 1921 được trao cho Einstein vì một khám phá kháccủa ông: Hiệu ứng quang điện Đây là công trình Einstein viết cũng vào năm 1905, cùng nămvới công trình về thuyết tương đối hẹp và một công trình nữa về chuyển động Brown Hiệu ứngquang điện là đóng góp lớn nhất của Einstein vào thuyết lượng tử, lý thuyết mà sau này đượcBohr, Heisenberg, Schr¨odinger và nhiều người khác phát triển lên nhưng lại bị Einstein nghi ngờđến cuối đời

Hiệu ứng quang điện là hiện tượng khi ta chiếu ánh sáng vào một tấm kim loại thì thỉnh thoảngđiện tử bị bứt ra khỏi kim loại Ta có thể đoán là ánh sáng càng mạnh thì càng nhiều điện tử

bị bứt ra Phán đoán này hoá ra là không hoàn toàn đúng: Có những nguồn ánh sáng rất mạnhkhông gây ra hiệu ứng quang điện, nhưng có những nguồn yếu hơn lại gây ra hiệu ứng này Thựcnghiệm cho thấy rằng hiệu ứng quang điện phụ thuộc vào tần số của ánh sáng Ví dụ, với cùngmột mẫu kim loại, ánh sáng đỏ hoặc tia hồng ngoại không gây ra hiệu ứng nhưng ánh sáng tímhoặc cực tím lại có tác dụng

Einstein giải thích điều này bằng cách áp dụng và mở rộng giả thuyết lượng tử của Planck.Einstein giả thuyết rằng ánh sáng bao gồm các hạt photon, mỗi hạt mang một năng lượng tỉ lệthuận với tần số của ánh sáng.

E = hv

Ở đây E là năng lượng của hạt photon, v là tần số của ánh sáng, và h là hằng số Planck Côngthức trên có tên là công thức Planck, công thức mà theo tôi đáng lẽ ra phải nổi tiếng hơn côngthức E = mc2

Hiệu ứng quang điện là quá trình một hạt photon truyền năng lượng cho một hạt điện tử Để bứtmột điện tử ra khỏi mảnh kim loại ta cần một năng lượng tối thiểu nhất định, ta gọi là ∆ Nhưvậy chỉ khi v > ∆h ánh sáng mới có thể bứt được điện tử ra khỏi khối kim loại Nếu v < ∆h thìnguồn sáng có mạnh thế nào cũng không có photon đủ năng lượng để gây ra hiệu ứng quangđiện Bạn có thể hỏi liệu có khi nào hai hạt photon, hoặc nhiều hơn, cùng hợp sức để bứt ra mộtđiện tử hay không Điều này về nguyên tắc có thể xảy ra, nhưng xác suất rất thấp, có thể bỏ qua.Hiệu ứng quang điện có liên quan trực tiếp đến một câu hỏi hay được đặt ra hiện nay: Điện thoại

di động có gây tác hại cho sức khoẻ hay không? Một trong những điều làm nhiều người lo lắng

là khả năng gây ung thư của sóng điện thoại (ví dụ xembài này) Nhiều người còn nói là sóngđiện từ trong lò vi sóng cũng có thể gây ra ung thư

Nếu ta nhớ lại công thức E = hv của Einstein thì ta sẽ thấy những lo lắng này không có cơ sở

Đó là do tần số sóng của các thiết bị điện tử quá thấp để có thể gây ra những biến đổi của phân

tử ADN Tần số sóng trong lò vi sóng là 2500 MHz, tần số của điện thoại di động là 800 MHzhay 1900 MHz Hằng số Planck là 4 × 10−9 eV/MHz, như vậy 2500 MHz tương đương với nănglượng 10 phần triệu eV, trong khi các quá trình hoá học hay sinh hoá cần năng lượng cỡ ít nhất0.1 eV, nếu không phải là 1 eV Sự chênh lệch đến 10 − 100 nghìn lần giữa hai cỡ năng lượnglàm cho lò vi sóng hay điện thoại di động không thể làm biến đổi gien của miếng thịt để trong lòhay cơ thể chúng ta (Tia cực tím thì lại khác, vì tần số của tia cực tím cao hơn tần số của điệnthoại di động đến cả triệu lần, nên nó có đủ năng lượng để gây tác hại cho tế bào)

Tất nhiên là điện thoại di động hay các thiết bị điện tử có thể có những tác hại khác, ví dụ chotâm lý hay là giấc ngủ của người dùng, nhưng chúng ở ngoài khuôn khổ của bài viết này

HỆ MẬT MÃ KHÓA CÔNG KHAI DỰA TRÊN ĐƯỜNG CONG ELLIPTIC - TỔNG QUAN VỀ

HỆ MẬT MÃ KHÓA CÔNG KHAI

Đặng Minh Tuấn(Vietkey)

Trong số này, Epsilon trân trọng gửi đến độc giả phần đầu tiên của chuyên đề

về hệ mật mã khóa công khai dựa trên đường cong Elliptic của tác giả Đặng MinhTuấn Phần sau của chuyên đề sẽ được chuyển tải ở tạp chí số 10

Sau đây là toàn văn của lời mở đầu và chương 1 của loạt chuyên đề

LỜI MỞ ĐẦU

Tháng 3 năm 2016, Bộ Ngoại Giao Hoa Kỳ, đứng đầu là bộ trưởng John Kerry,

đã dẫn một đoàn đại biểu tới các nước ASEAN trong đó có Việt Nam để thảo luận vềphát triển Fintech và đặc biệt là về công nghệ Blockchain1.Tháng 9 năm 2015, Ủyban giao dịch hàng hoá tương lai Mỹ công bố, Bitcoin đã chính thức được đưa vàodanh sách hàng hóa được phép giao dịch tại Mỹ2.Công nghệ Blockchain và Bitcoin

là công nghệ tiền số ra đời năm 2009 và ngày càng có nhiều quốc gia và các tổ chức,doanh nghiệp cho phép lưu hành và thanh toán bằng loại tiền số này trong khônggian mạng Internet toàn cầu Tháng 4-2016, giá trị thương mại của Bitcoin đã lênđến 6.5 tỷ USD3 Nền tảng cơ sở của Bitcoin chính là lý thuyết về mật mã mà cụ thể

ở đây là hàm băm và lý thuyết về chữ ký số dựa trên Hệ mật đường cong Elliptic(ECC)

Bên cạnh việc sử dụng trong tiền số Bitcoin4, ECC còn được ứng dụng rấtnhiều trong thực tiễn ngành Công nghệ thông tin [1] Các trang Web bảo mật https(http-secure) thường được dùng trong thanh toán điện tử hay ứng dụng riêng tư nhưgmail đều sử dụng các giao thức TLS (Transport Layer Security) mà trước đó là

1 B Cohen (April 12, 2016) U.S State Department Recommends Development of Blockchain and tributed Ledgers to International Partners [Online] Available: http://www.nasdaq.com/article/us-state-department- recommendsdevelopment-of-blockchain-and-distributed-ledgers-to-international-partnerscm605334.

Dis-2 (21/09/2015) Bitcoin chính thức được Mỹ công nhận là hàng hoá [Online] Available: tuc-kinh-doanh/-/view-content/content/1654484/bitcoin-chinh-thuc-duoc-My-cong-nhan-la-hang-hoa.

http://vnreview.vn/tin-3 (15/4/2016) https://markets.blockchain.info/

4 Địa chỉ ví Bitcoin được tính dựa trên khóa công khai của ECC với hàm băm bảo mật có độ dài 256-bit SHA256 và thuật toán Base58Encode dùng để chuyển số thành dạng 56 ký tự, RIPEMD (RACE Integrity Primitives Evaluation Message Digest) là một họ hàm băm bảo mật khác:

Version = 1(byte) KeyHash = Version + RIPEMD(SHA256(PublicKeyEC)) CheckSum = SHA256(SHA256(KeyHash))

BitcoinAddress = Base58Encode(KeyHash + CheckSum)

SSL (Secure Socket Layer) Trong các giao thức này ECC được sử dụng để trao đổikhóa phiên Các giao dịch remote access được sử dụng rất nhiều trong thế giới Unix,Linux là SSH (Secure SHell) cũng sử dụng ECC để trao đổi khóa Ưu điểm của hệmật sử dụng đường cong Elliptic (ECC) là có độ dài khóa nhỏ (160 bit tương đươngvới khóa độ dài 1024 Bit trong hệ mật RSA), do sử dụng độ dài khóa nhỏ nên tàinguyên phục vụ cho ECC thường nhỏ hơn rất nhiều, bên cạnh đó hiệu năng tính toáncũng được nâng cao rõ rệt Hiện nay ECC đang là xu thế để thay thế RSA.

Cơ sở toán học của hệ mật ECC là nhóm giao hoán Abel các điểm nằm trênđường cong Elliptic Ngoài việc đường cong Elliptic là cơ sở cho hệ mật ECC, hệmật ID-Based, đường cong Elliptic (EC) còn là công cụ hữu hiệu để phân tích sốnguyên ra thừa cố nguyên tố [2,3,4], hoặc dùng để kiểm tra tính nguyên tố của

số nguyên [3] EC cũng là cơ sở để chứng minh định lý Fermat nổi tiếng đã tồn tạinhiều trăm năm qua

Đường cong Elliptic là một trường hợp đặc biệt của phương trình Diophant Lýthuyết về đường cong Elliptic (EC) rất phong phú và đồ sộ Trong [5] tác giả Serge

Lang đã phát biểu về phương diện học thuật: “Có thể viết vô tận về đường cong

Elliptic” Các lý thuyết và khái niệm liên quan tới EC có thể liệt kê một số như dướiđây:

• Lý thuyết nhóm, vành, trường trong đại số trừu tượng [3,6];

• Đa tạp Affine, đa tạp Jacobian và đa tạp xạ ảnh trong hình học đại số [7,8];

• Điểm Torsion, Divisor, cặp song tuyến tính Weil, Tate-Lichtenbaum [3];

• Lý thuyết trường Galois, tự đồng cấu-ánh xạ Frobenius [3,9];

• Lý thuyết Baker-Feldman, Baker-Tijdeman và lý thuyết Kummer [5];

• Số p-adic, Isogenies, hàm Sigma và hàm Zeta [5,7,10,3,4];

• Nhóm đối đồng điều, đối đồng điều Galois và đối đồng điều phi giao hoán(Topo đại số) [8,4];

• Nhóm Mordell–Weil, Selmer và nhóm Shafarevich–Tate [8,11];

• Phương pháp hình học và Tựa tuyến tính (Quasilinear) [12]

Với ý nghĩa to lớn cả về thực tiễn và học thuật, EC là nền tảng toán học quantrọng trong đại số hiện đại cũng như lý thuyết mật mã hiện đại EC cũng là nền tảngquan trọng trong chính phủ điện tử và thương mại điện tử Chính vì những điều này

mà Chuyên đề “Hệ mật mã khóa công khai dựa trên đường cong Elliptic” được lựa

chọn để trình bày báo cáo

Với khối lượng kiến thức và khái niệm đồ sộ như đã liệt kê ở trên việc nghiêncứu và đào sâu về đường cong Elliptic gặp không ít khó khăn cho những người làmCông nghệ thông tin (CNTT) mà toán học không phải là chuyên môn chính Mụctiêu của chuyên đề này là tổng hợp những khái niệm và kiến thức cơ bản nhất của

EC liên quan đến cơ sở toán học của Hệ mật dựa trên đường cong Elliptic Đồngthời người viết cũng chứng minh lại một số định lý và bổ đề theo cách dễ hiểu hơn,tránh dùng đến các khái niệm quá phức tạp và xa lạ với chuyên ngành CNTT Cácphép toán của đường cong Elliptic được trình bày trong báo cáo phần lớn được càiđặt bằng phần cứng sử dụng công nghệ FPGA (Field-Programmable Gate Array)của Xilinx trong khuôn khổ Đề tài cấp Nhà nước KC01-18 (đã được nghiệm thutrong năm 2014) do người viết báo cáo làm chủ nghiệm đề tài, kết quả được công bốtại [13]

Tạp chí Epsilon, Số 09, 06/2016

Phạm vi của chuyên đề cũng được giới hạn với những khái niệm và lý thuyết đủcho các ứng dụng cơ bản của EC, các phát triển của EC thành hệ mật ID-Based,hoặc các ứng dụng về chữ ký số tập thể, chữ ký số nhóm, chữ ký ngưỡng, chứ ký ủynhiệm, chứ ký số mù sẽ không được đề cập đến trong khuôn khổ của báo cáo này

Báo cáo chuyên đề được kết cấu thành 02 chương, chương 1 trình bày các kháiniệm, định nghĩa cơ bản về đường cong Elliptic (Phương trình của EC, nhóm cộngAbel các điểm trên đường cong, chứng minh định lý về nhóm ) Chương 2 trìnhbày về Hệ mật dựa trên đường cong Elliptic và một số ứng dụng trong mã hóa, xácthực chữ ký số, trao đổi khóa dự trên bài toán khó Logarithm rời rạc

EC Đường cong Elliptic (Elliptic Curve)

ECC Hệ mật dựa trên đường cong Elliptic (Elliptic Curve Cryptography)

ECDLP Elliptic Curve Logarithm Problem

ECDH Thuật toán Elliptic Curve Diffie–Hellman

ECDSA The Elliptic Curve Digital Signature Algorithm

ECIES The Elliptic Curve Integrated Encryption System

ECMQV Elliptic Curve Menezes–Qu–Vanstone protocol

1 Tổng quan về đường cong Elliptic

Năm 250 sau Công nguyên, Diophant khi giải bài toán tìm số tầng của tháp các quả cầu mà khitrải ra mặt đất có thể xếp thành một hình vuông đã dẫn đến giải phương trình (y là số quả cầutrên 1 cạnh hình vuông; x là số tầng của tháp):

y2 = 12+ 22+ 32+ · · · + x2 = x(x + 1)(2x + 1)

6Phương trình y2 = x(x + 1)(2x + 1)/6 là một dạng của đường cong Elliptic

Năm 1637, nhà toán học và vật lý học người Pháp Pierre de Fermat công bố định lý Fermat cuốicùng khi viết trên lề bản copy công trình của Diophant: Phương trình sau đây là vô nghiệm:

xn+ yn= zn, n > 2

Hơn ba thế kỷ, đã có rất nhiều nhà toán học cố gắng chứng minh định lý này xong đều thất bại,mãi cho đến năm 1994, Andrew Wiles, giáo sư trường Princeton đã gây một tiếng vang lớntrong cộng đồng toán học thế giới vào thời điểm đó khi sử dụng đường cong Elliptic có dạng

y2 = x(x − an)(x + bn) cùng với lý thuyết về Modul để chứng minh định lý Fermat cuối cùng.Năm 1987, Trong [14], Lenstra đề xuất thuật toán phân tích số nguyên ra thừa số nguyên tố sửdụng đường cong Elliptic, đó là thuật toán tương đối nhanh, chạy với thời gian dưới hàm mũ và

là thuật toán nhanh thứ 3 trong việc phân tích ra thừa số nguyên tố, sau phương pháp sàng đathức toàn phương và phương pháp sàng trường số tổng quát

Trong lĩnh vực mật mã, vào năm 1985, Victor S Miller công bố bài báo đầu tiên về ứng dụng

đường cong EC trong mật mã “Use of Elliptic Curves in Cryptography” [15] và sau đó là Neal

Koblitz với “Elliptic curve cryptosystem” [16] vào năm 1987 Từ đó cho đến nay đã có rất nhiềucông bố nghiên cứu về EC về lý thuyết và trong thực tiễn càng ngày ứng dụng ECC càng được sửdụng rộng rãi, và đã được đưa thành các tiêu chuẩn

Một số tiêu chuẩn liên quan đến đường cong Elliptic:

IEEE 1363: Tiêu chuẩn này bao gồm gần như tất cả các thuật toán

về các hệ khóa công khai trong đó có ECDH, ECDSA,ECMQV và ECIES Trong phần phụ lục có cả cácthuật toán cơ bản về lý thuyết số liên quan đến hệ mậtkhóa công khai

ANSI X9.62 và X9.63: Các chuẩn này tập trung vào đường cong Elliptic và

cụ thể về ECDSA trong X9.62 và ECDH, ECMQV

và ECIES trong X9.63 Các chuẩn này cũng xác địnhkhuôn dạng các dữ liệu và danh mục các đường congkhuyến cáo sử dụng

FIPS 186.2: Tiêu chuẩn của NIST cho chữ ký số, mô tả chi tiết về

thuật toán DSA algorithm

SECG: Là tiêu chuẩn được biên soạn bởi nhóm các doanh

nghiệp dẫn dắt bởi công ty Certicom, gần như là ánh

xạ của các chuẩn ANSI nhưng được tiếp cận trên môitrường Web từ Website http://www.secg.org/

ISO 15946-2: Tiêu chuẩn mô tả về ECDSA và ECIES (còn được gọi

là ECIES-KEM)

RFC 3278: “Use of Elliptic Curve Cryptography (ECC)

Algo-rithms in Cryptographic Message Syntax (CMS)” làkhuyến nghị sử dụng thuật toán ECC trong mã hóathông điệp văn bản

2 Phương trình Weierstraß của đường cong Elliptic

Trong tài liệu này, đa phần số các đường cong Elliptic sẽ được nghiên cứu dưới dạng sau:

y2 = x3+ Ax + B, (2.1)Trong đó A và B là các hằng số Các giá trị của x, y, A, B thường là các giá trị trên một trườngnào đó, ví dụ như R (số thực), Q (số hữu tỷ), C (số phức), hoặc trường hữu hạn Fq, với q = pn

trong đó p là số nguyên tố với n = 1 Nếu K là một trường có a, b ∈ K, khi đó ta nói đường congElliptic được định nghĩa trên trường K Điểm (x, y) trên đường cong Elliptic với (x, y) ∈ K

Tạp chí Epsilon, Số 09, 06/2016

được gọi là điểm K–Hữu tỷ Dạng tổng quát phương trình Weierstrass của đường cong Elliptic

sẽ được biểu diễn dưới dạng:

Có thể viết lại như sau:

y12 = x3+ a02x2+ a04x + a06,Với y1 = y + a1x/2 + a3/2 và với các hằng số a02, a04, a06 Khi K có chap(K) khác 3 có thể dùngphép thế x1 = x + a02/3 và ta có:

y12 = x31+ Ax + B,Trong đó A, B là các hằng số nào đó Đường cong (2.1) có định thức ∆ = −16(4A3+ 27B).Đường cong này sẽ suy biến và không có đủ 3 nghiệm phân biệt khi ∆ = 0, trong tài liệu nàychúng ta chỉ xét các đường cong có ∆ 6= 0

3 Cộng các điểm trên đường cong Elliptic

Xét hai điểm P1 = (x1, y1) và P2 = (x2, y2) trên đường cong Elliptic E : y2+ a1xy + a3y =

x3+ a2x2+ a4x + a6 Phép cộng giữa hai điểm trên đường cong E được định nghĩa như sau:

P3(x3, y3) = P1(x1, y1) + P2(x2, y2) (3.1)

Trong đó P3(x3, y3) = −P30(x3, y30), điểm P30(x3, y03) là giao điểm của đường cong E và đườngthẳng đi qua P1 và P2 Vì 2 điểm P3(x3, y3) và −P30(x3, y30) đều nằm trên đường cong E nên(x3, y3) và (x3, y30) phải thỏa mãn phương trình (2.2) Công thức để tính các giá trị (x3, y3) sẽđược chứng minh ở dưới đây

Trong các các tài liệu cơ bản và nâng cao được tham chiếu nhiều về đường cong Elliptic như[3,7,8] người viết vẫn chưa thỏa mãn với các dẫn dắt và chứng minh công thức tổng quát chocác giá trị (x3, y3), do đó các công thức này sẽ được chứng minh chi tiết trong tài liệu này Đườngthẳng đi qua 2 điểm P1 và P2 có phương trình là:

y = λx + µ (3.2)Trong đó λ là hệ số góc của đường thẳng đi qua P1, P2 Ta có:

y1 = λx1+ µ (3.3)

y2 = λx2+ µ (3.4)

y30 = λx3+ µ (3.5)

Hình 6.1: Phép cộng trên đường cong Elliptic

3.1 Trường hợp 2 điểm không trùng nhau P1 6= P2

Từ (3.3) và (3.4) suy ra: y1− y2 = λ(x1− x2), khi P1 6= P2, nghĩa là x1 6= x2 ta có công thức:

(λx + µ)2+ (a1x + a3)(λx + µ) = x3+ a2x2+ a4x + a6 (3.8)

Từ đó dẫn đến phương trình r(x) = 0 với:

r(x) = x3+ (a2 − λ2− a1λ)x2+ (a4− 2λµ − a3λ − a1µ)x + a6− µ2− a3µ (3.9)

y2+ (a1x3+ a3)y − (x33 + a2x23 + a4x3 + a6) = 0 (3.12)Phương trình bậc 2 này có 2 nghiệm là:

y3, y03 = −(a1x3+ a3) ±√

∆

2 × 1 (3.13)Cộng 2 nghiệm này ta sẽ có: y30 + y3 = −a1x3− a3, mặt khác do y30 nằm trên đường thẳng P1, P2

nên y30 = λx3+ µ Từ đây có thể tính được y3 theo công thức5:

y3 = −λx3− µ − a1x3− a3 (3.14)Thay µ từ (3.7) ta có thể tính y3dưới dạng sau:

y3 = λ(x1− x3) − y1− a1x3− a3 (3.15)

3.2 Trường hợp 2 điểm trùng nhau P1 = P2

Khi này x1 = x2và y1 = y2 do đó công thức tính λ ở (3.7) không sử dụng được vì xuất hiện phépchia số 0 Trong trường hợp này λ chính là hệ số góc của đường thẳng tiếp tuyến đường cong Etại P1hay P2 Hệ số góc của tiếp tuyến của E chính là đạo hàm dydx, sử dụng các quy tắc lấy đạohàm của tích, đạo hàm của hàm số hợp và lấy đạo hàm 2 vế của phương trình (2.2) theo dx ta có:

d(y2+ a1xy + a3y)

dx =

d(x3+ a2x2+ a4x + a6)

dxd(y2)

dx = 3x

2+ 2a2x + a4− a1ydy

dx =

3x2+ 2a2x + a4− a1y2y + a1x + a3

5Ghi chú: Các tác giả H Cohen và G Frey trong cuốn “Handbook of Elliptic and Hyperelliptic Curve raphy” [7] trình bày diễn giải về cách tính y3 dựa trên sự đối xứng qua trục x là không chính xác và thiếu rõ ràng đối với đường cong Elliptic dạng tổng quát, cách giải thích của người viết bằng cách giải phương trình bậc 2 ở đây

Cryptog-có thể coi là đúng đắn và rõ ràng hơn.

Như vậy với điểm P1(x1, y1) ta có:

λ = 3x

2

1+ 2a2x1+ a4− a1y12y1+ a1x1+ a3 (3.16)Trong tất cả các trường hợp điểm P3 là tổng của 2 điểm P1, P2 sẽ là điểm có tọa độ là:

P3(x3, y3) = (λ2+ a1λ − a2− x1− x2, λ(x1− x3) − y1− a1x3− a3) (3.17)Với đường cong E dạng (2.1), khi đó a1 = a3 = a2 = 0 và P3 sẽ được tính theo công thức:

P3(x3, y3) = (λ2− x1− x2, λ(x1− x3) − y1) (3.18)Trong trường hợp P1 = P2, (3.16) sẽ được biến đổi thành:

λ = 3x

2

1+ a4

4 Nhân vô hướng các điểm trên đường cong Elliptic

Với n ∈ N \ {0} định nghĩa phép nhân vô hướng của điểm P nằm trên đường cong E là phépcộng n lần chính bản thân điểm P :

P 7→ nP = P + P + · · · + P

| {z }

n lần

= Q

Để tối ưu phép nhân vô hướng, có thể sử dụng phương pháp Nhân đôi-và-cộng, đầu tiên biểu

diễn số n dưới dạng: n = n0 + 2n1 + 22n2 + · · · + 2mnm với [n0 nm] ∈ {0, 1}, sau đó ápdụng thuật toán:

Algorithm 1 Phương pháp Nhân đôi-và-cộng

Ngoài phương pháp Nhân đôi-và-cộng, có thể sử dụng phương pháp Trượt-cửa-sổ Các phương

pháp này cho phép nhân vô hướng một cách tối ưu

Lưu ý của người viết:

• Không tồn tại phép nhân 2 điểm trên đường cong E, có nghĩa là không tồn tại P × Q với

P, Q ∈ E

• Không tồn tại thuật toán chia vô hướng Q : n Biết rằng Q = nP , bài toán tìm số n là bàitoán Logarithm rời rạc sẽ được đề cập tới ở chương sau Đây là bài toán khó, thông thườngphải thử lần lượt n = 1, 2, , n − 1 phép cộng điểm P , cho đến khi tổng bằng Q, tuynhiên có một số thuật toán tối ưu hơn để tìm n nhưng vẫn không thể giải được bài toán nàytrong thời gian đa thức vì thế dựa vào độ khó này có thể xây dựng ra hệ mật đường congElliptic với các giao thức cho mã hóa, xác thực và trao đổi khóa

Tạp chí Epsilon, Số 09, 06/2016

Hình 6.2: Ví dụ về tính chất kết hợp trên đường cong Elliptic

5 Nhóm (+) của các điểm trên đường cong Elliptic

Xét đường cong Elliptic E được định nghĩa bởi phương trình y2 = x3+ Ax + B Xét 3 điểmnằm trên đường cong E là P1, P2, P3 lần lượt có các tọa độ là (x1, y1), (x2, y2), (x3, y3)

Để các điểm trên đường cong Elliptic tạo thành nhóm (+), “điểm vô cùng” (∞) sẽ được thêmvào đường cong, kí hiệu là O, điểm này sẽ nằm ở trên cùng và dưới cùng của trục y Một trongnhững thuộc tính quan trọng nhất của đường cong Elliptic là tồn tại nhóm các điểm với phépcộng nằm trên đường cong.

Định lý 5.1 Phép cộng với các điểm P, P1, P2, P3 trên đường cong E thỏa mãn các tính chất của nhóm:

(2 Điểm đơn vị) không cần phải chứng minh vì nó xuất phát từ định nghĩa Có thể lý giải rõ hơn

về điểm (∞) và cách định nghĩa phép cộng trên E (theo quan điểm của người viết) như sau: Khiđường cong E không suy biến, nó sẽ cắt một đường thẳng được định nghĩa bởi phương trình(3.2) ở 3 điểm, thực vậy theo các phép biến đổi ở mục 3.1 (trang 28) phương trình (3.9) r(x) sẽ

có 3 nghiệm phân biệt Mặt khác E đối xứng qua trục x do phương trình (2.1) có thành phần y2

nên luôn tồn tại hai giá trị y, −y thỏa mãn (2.1), cũng do tính đối xứng này nên đường cong E sẽcắt các đường thẳng song song với với trục y ở 2 điểm, vì nếu cắt thêm 1 điểm nữa thì sẽ phảicắt thành 4 điểm do tính đối xứng, điều này là mẫu thuẫn vì phương trình bậc 3 chỉ có tối đa 3nghiệm Ở trường hợp này nếu cộng 2 điểm nằm trên đường song song trục y sẽ không tìm đượcđiểm thứ 3 do vậy P1+ P2sẽ không tồn tại Chính vì để nhóm các điểm trên E có tính đóng bắtbuộc chúng ta phải định nghĩa thêm điểm ∞ coi như là điểm thứ 3 nằm trên đường cong E, và

nó sẽ nằm ở vô cực ở 2 đầu trục y

Tiếp theo, có thể lý giải (của người viết6) về phép định nghĩa phép cộng 2 điểm trên E như sau

Để thỏa mãn tính chất tồn tại điểm đơn vị theo định nghĩa về nhóm G với mọi giá trị a ∈ G tồntại e ∈ G sao cho

a • e = e • a = a (5.1)Xét điểm P trên đường cong E, khi đó cần tính P + ∞, dễ thấy điểm này chắc chắn phải nằmtrên cùng đường thẳng song song trục y vì nếu không sẽ cắt E ở 2 điểm nữa cùng với ∞ tạothành 4 điểm và điều này là phi lý Nếu đã nằm trên đường song song y thì nó sẽ cắt E ở điểmđối xứng qua trục x, nếu coi điểm cắt này là tổng P + ∞ thì như vậy sẽ tồn tại P + ∞ = P0 vàđiều kiện (5.1) sẽ không được thỏa mãn Vì vậy sẽ phải định nghĩa điểm tổng không phải là giao

6

Khi bắt đầu nghiên cứu về đường cong Elliptic, luôn có 2 câu hỏi mà người viết không thể tìm thấy trong nhiều tài liệu kể cả những cuốn kinh điển về Elliptic:

1 Tại sao phải chọn ∞ làm điểm trung hòa.

2 Tại sao P 1 + P2= P3mà P 3 không nằm trên đường thẳng đi qua P 1 , P2mà phải là điểm đối xứng của giao điểm qua trục x.

Trong chuyên đề này cả 2 câu hỏi đều đã được người viết lý giải một cách rõ ràng và đầy đủ.

λ32= (y2− y3)(x2− x3) (5.3)

được biểu diễn dưới các dạng công thức từ (5.10) đến (5.13).

(x2− x3)3 − (2x3+ x2)(y2− y3)

x2− x3 + y3Cần phải chứng minh rằng P123 = P321điều này có nghĩa cần phải chứng minh:

dx = x123− x321 = 0 (5.14)

dy = y123− y321 = 0 (5.15)Triển khai vế trái của (5.14), sẽ được một phân số mà tử số và mẫu số bao gồm tổng cộng 1446thành phần, tương tự vế trái của (5.15) có tất cả 10081 thành phần có dạng nkxi1

Trường F2 mthường được biểu diễn dưới dạng tổ hợp tuyến tính của các vector gồm m phần tử{α0, α1, , αm−1}, mọi phần tử α ∈ F2 m đều có thể được biển diễn dưới dạng:

• Phép nhân:

(rm−1 r1r0) = (am−1 a1a0).(bm−1 b1b0)

Trong đó (rm−1xm−1+ + r1x + r0) = (am−1xm−1+ + a1x + a0) × (bm−1xm−1+ + b1x + b0) mod f (x)

Đa thức rút gọn f (x) thường có dạng sau:

i=0 aiβ2i, ai ∈ {0, 1} và cũng được biểu diễn dưới dạng chuỗi bit (a0a1 am−1)

có độ dài là m Với cơ sở này phép bình phương sẽ thực hiện rất đơn giản chỉ bằng cách quay bit.Các phép toán trong trường F2 m:

Pm/2 k=1(ak+l−1bm/2+k+l−1+ am/2+k+l−1bk+l−1)+Pp=2

k=1aF (k+1)+laF (k+1)+l, nếu T lẻ

6.2 Tổng số điểm của đường cong Elliptic trên trường hữu hạn Fq

E là đường cong Elliptic trên trường Fq, bởi vì cặp (x, y) với x, y ∈ Fqlà hữu hạn do đó nhómE(Fq) cũng sẽ là nhóm hữu hạn Các giá trị x, y là các số nguyên, dễ dàng nhận thấy khôngphải với mọi giá trị x đều tìm được giá trị nguyên y bởi vì không phải bao giờ√

y cũng là một

số nguyên dương Câu hỏi đặt ra là số điểm của của đường cong Elliptic trên trường Fqlà baonhiêu? Xác định số điểm trên đường cong E nhằm xác định không gian khóa của hệ mật.Sau đây là phần trình bày về việc tính tổng số điểm của đường cong Elliptic trên trường hữu hạn

Fq

Tạp chí Epsilon, Số 09, 06/2016

Bổ đề 1 M và N là hai ma trận 2 × 2 M =m11 m12

m21 m22

, N = n11 n12

n21 n22



, với các số nguyên

a, b ta có:

det(aM + bN ) = a2det(M ) + b2det(N ) + ab(det(M + N ) − det(M ) − det(N )) (6.1)

Chứng minh. Theo định nghĩa về định thức ta có:

det(M + N ) = det(M ) + det(N ) + (m11n22+ n11m22− m21n12− n21m12) (6.3)Nhân cả 2 vế (6.3) với ab sau đó trừ vào (6.2) sẽ được kết quả (6.1) là điều cần phải chứngminh

Định nghĩa 6.1 Điểm n-xoắn (Torsion): Cho đường cong Elliptic E được định nghĩa trên trường

K, cho n là số nguyên dương, tập các điểm Torsion E[n] là tập các điểm trên đường cong có

tính chất như sau:

E[n] =P ∈ E(K) | nP = ∞

(6.4)

K là đóng đại số của K

Định nghĩa 6.2 Divisor: Cho đường cong Elliptic E được định nghĩa trên trường K, với mỗi

điểm P ∈ E(K) định nghĩa một ký hiệu hình thức (formal symbol) [P ], khi đó divisor D sẽ là:

Bổ đề 2 Với mọi tự đồng cấu bất khả tách α trên E, và với mọi S, S1, S2, T, T1, T2 ∈ E[n] ta

Giả thiết {T1, T2} là cơ sở của E[n], mỗi phần tử trong E[n] đều có thể biểu diễn dưới dạng tổhợp tuyến tính m1T1+ m2T2 α là một tự đồng cấu trong E[n], n là một số nguyên không chiahết bởi char(K) Tồn tại các số a, b, c, d ∈ Z sao cho:

Bổ đề 3 α là một tự đồng cấu trong E[n], n là một số nguyên không chia hết bởi char(K) khi

đó det(αn) ≡ deg(α) mod n.

Bổ đề 4 deg(aα + bβ) = a2deg α + b2deg β + ab(deg(α + β) − deg α − deg β)

Chứng minh. Biểu diễn các tự đồng cấu α, β bằng các ma trận αn, βn(với một số cơ sở trongE[n]), theo đó aα + bβ sẽ được biểu diễn bằng aαn+ bβn Áp dụng công thức (6.1) ta có:det(aαn+ bβn) = a2det(αn) + b2det(βn) + ab(det(αn+ βn) − det(αn) − det(βn))Theo bổ đề 3 chúng ta sẽ có:

deg(aα + bβ) = a2deg(α) + b2deg(β) + ab(deg(α + β) − deg(α) − deg(β))