CHƯƠNG I. CƠ SỞ TOÁN HỌC CỦA MẬT MÃ HIỆN ĐẠI I.1 Tổng quan về số nguyên tố: 1.1 Số nguyên tố a, Số lượng số nguyên tố Số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó. Ví dụ, 2, 3, 7 là ba số nguyên tố đầu tiên. Ba số nguyên tố lớn nhất được tìm ra cho đến nay là STT Số nguyên tố Số chữ số Ngày tìm raNgười/Tổ chức tìm ra 1 242.064 12 tháng 4 GIMPS / năm 2009 Odd M.189 23 tháng 8 GIMPS / năm 2008 Edson Smith 3 257.170 25 tháng 1 GIMPS / năm 2013 Curtis Coope Các số nguyên tố lớn đóng vai trò cốt yếu trong việc xây dựng các hệ mật mã hiện đại, như hệ mật RSA, ElGamal và hệ mật trên đường cong Eliptic.
Vì vậy, việc tìm ra các số nguyên tố lớn luôn giành được sự quan tâm đặc biệt của cộng đồng toán học và công nghệ thông tin. Câu hỏi đặt ra là số các số nguyên tố có đủ nhiều cho các ứng dụng của chúng ta hay không? Hơn 2.000 năm trước Euclid đã chứng minh được tính vô hạn của các số nguyên tố. Cụ thể hơn, các nhà toán học sau đó đã tìm ra được phân bố của các số nguyên tố trong định lý sau: Định lý 1. Định lý về số các số nguyên tố x Giả sử ( x) là số các số nguyên tố nhỏ hơn hoặc bằng x, khi đó ( x) theo ln x nghĩa ( x) / ( x / ln x) 1 khi x.
Tôi không đưa ra chứng minh định lý này ở đây vì ra ngoài nội dung của luận văn, mà tôi đưa ra bảng sau để chứng tỏ số nguyên tố quả thực là đủ dùng cho các ứng dụng của chúng ta. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 Bảng một số giá trị của π(x) x π(x) 15 10 29844570422669 16 10 279238341033925 17 10 2623557157654233 18 10 24739954287740860 19 10 234057667276344607 20 10 2220819602560918840 21 10 211272694860018731928 22 10 201467286689315906290 23 10 1925320391606803968923 24 10 18435599767349200867866 Hơn nữa, nếu giả thiết Riemann đúng, khi đó ta có đánh giá số các số nguyên tố như sau: x dt ( x) O( xe c log x ) (1.1) 2 ln t hay công thức hiệu quả hơn: x dt ( x) O ( x ln x) (1.2) 2 ln t Tuy nhiên cho đến nay chúng ta chưa biết giả thiết Riemann đúng hay không. Đây là một trong bảy bài toán được Viện toán cao cấp Clay treo giải 1 triệu USD vào năm 2000. Một số nguyên dương n > 1 bất kỳ luôn có biểu diễn duy nhất dưới dạng: n p11 p22 .3) ở đây p1<p2< …<pk là các số nguyên tố và 1, 2, …, k là các số nguyên dương.
Sau đây là các số nguyên tố lớn được tham khảo từ trang https://primes.html: b, Mười số nguyên tố lớn nhất thuộc lớp Mersenne: rank prime Digits who when Reference 1 257885161-1 17425170 G13 2013 Mersenne 48?? 2 243112609-1 12978189 G10 2008 Mersenne 47?? 3 242643801-1 12837064 G12 2009 Mersenne 46?? 4 237156667-1 11185272 G11 2008 Mersenne 45? LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 5 232582657-1 9808358 G9 2006 Mersenne 44? 6 230402457-1 9152052 G9 2005 Mersenne 43? 7 225964951-1 7816230 G8 2005 Mersenne 42 8 224036583-1 7235733 G7 2004 Mersenne 41 9 220996011-1 6320430 G6 2003 Mersenne 40 10 213466917-1 4053946 G5 2001 Mersenne 39 Các số nguyên tố không thuộc lớp Mersenne Số nguyên tố lớn nhất không thuộc dạng số Mersenne được phát hiện là số 19. Ngày được kiểm định là 26 tháng 3 năm 2007. c, Số nguyên tố dạng n!+1 Số nguyên tố lớn nhất dạng n!+1 là số 150.355 chữ số, được chứng minh vào tháng 10 năm 2011. Mười số nguyên tố lớn nhất dạng n!+1 rank prime Digits Who When reference 1 150209!+1 712355 p3 2011 Factorial 2 147855!-1 700177 p362 2013 Factorial 3 110059!+1 507082 p312 2011 Factorial 4 103040!-1 471794 p301 2010 Factorial 5 94550!-1 429390 p290 2010 Factorial 6 34790!-1 142891 p85 2002 Factorial 7 26951!+1 107707 p65 2002 Factorial 8 21480!-1 83727 p65 2001 Factorial 9 6917!-1 23560 g1 1998 Factorial 10 6380!+1 21507 g1 1998 Factorial d, Các số nguyên tố dạng p#±1 Số nguyên tố lớn nhất dạng p#±1 (tích của các số nguyên tố nhỏ hơn hoặc bằng p cộng trừ 1) là số 1.311 chữ số, được phát hiện ra vào tháng 3 năm 2012.
Mười số nguyên tố lớn nhất dạng p#±1: rank Prime Digits who when Reference 1 1098133#-1 476311 p346 2012 Primorial 2 843301#-1 365851 p302 2010 Primorial 3 392113#+1 169966 p16 2001 Primorial LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 4 366439#+1 158936 p16 2001 Primorial 5 145823#+1 63142 p21 2000 Primorial 6 42209#+1 18241 p8 1999 Primorial 7 24029#+1 10387 C 1993 Primorial 8 23801#+1 10273 C 1993 Primorial 9 18523#+1 8002 D 1989 Primorial 10 15877#-1 6845 CD 1992 Primorial e, Cặp số nguyên tố sinh đôi n±1: Cặp số nguyên tố sinh đôi lớn nhất là cặp 3756801695685x2666669±1, được tìm ra vào tháng 12 năm 2011. Mười số nguyên tố dạng sinh đôi lớn nhất: rank Prime digits Who when Reference 1 3756801695685·2666669+1 200700 L1921 2011 Twin (p+2) 2 3756801695685·2666669-1 200700 L1921 2011 Twin (p) 3 65516468355·2333333+1 100355 L923 2009 Twin (p+2) 4 65516468355·2333333-1 100355 L923 2009 Twin (p) 5 2003663613·2195000+1 58711 L202 2007 Twin (p+2) 6 2003663613·2195000-1 58711 L202 2007 Twin (p) 7 38529154785·2173250+1 52165 L3494 2014 Twin (p+2) 8 38529154785·2173250-1 52165 L3494 2014 Twin (p) 9 194772106074315·2171960+1 51780 x24 2007 Twin (p+2) 10 194772106074315·2171960-1 51780 x24 2007 Twin (p) g, Các số nguyên tố dạng Sophie German: Số nguyên tố p được gọi là số nguyên tố dạng Sophie German nếu 2p+1 cũng là số nguyên tố. Mười số nguyên tố dạng Sophie German lớn nhất là: rank Prime digits who when reference 1 18543637900515·2666667-1 200701 L2429 2012 Sophie Germain (p) 2 183027·2265440-1 79911 L983 2010 Sophie Germain (p) 3 648621027630345·2253824-1 76424 x24 2009 Sophie Germain (p) 4 620366307356565·2253824-1 76424 x24 2009 Sophie Germain (p) 5 607095·2176311-1 53081 L983 2009 Sophie Germain (p) 6 48047305725·2172403-1 51910 L99 2007 Sophie Germain (p) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 7 137211941292195·2171960-1 51780 x24 2006 Sophie Germain (p) 8 31737014565·2140003-1 42156 L95 2010 Sophie Germain (p) 9 14962863771·2140001-1 42155 L95 2010 Sophie Germain (p) 10 33759183·2123458-1 37173 L527 2009 Sophie Germain (p) 1.2 Một số định lý cơ bản Định nghĩa 1.1 Giả sử a Z và n n . Phần tử nghịch đảo của số nguyên a theo modulo n là số nguyên x thỏa mãn ax ≡ 1(modn).
Nếu x là số nguyên dương nhỏ nhất thỏa mãn là phần tử nghịch đảo của a, ta ký hiệu x=a-1.2 Định lý Wilson Nếu p là số nguyên tố, khi đó (p - 1) !≡ -1(modp). Chứng minh Kết quả là tầm thường với p≤3, bởi vậy ta xét với p>3. Theo định nghĩa 1.1, với số nguyên a Z bất kỳ với 2≤a≤p-2 ta có duy nhất a 1 Z với 2≤ a-1 ≤p-2. Ngoài ra, ta nhận thấy a=a-1 nếu và chỉ nếu a=1 hoặc a=p-1, do đó tích của các số a-1 với 2≤ a-1 ≤p-2 cũng chính là tích của các số a=2, 3, …, p-2 được săp theo 1 thứ tự nào đó.
Bới vậy, sau khi hoán vị các phần tử một cách thích hợp, ta có : (p – 2) ! ≡ 1(modn).1 Nếu p=17, khi đó với mỗi a , với 2≤a≤15 ta có 2. 3 Định lý ngược của định lý Wilson Nếu n thuộc N và (n-1) !≡-1(modn), khi đó n là số nguyên tố. 4 Định lý nhỏ Fermat Nếu a thuộc Z, và p là số nguyên tố sao cho gcd(a, p)=1, khi đó : ap-1≡1(modp) Định nghĩa 1. 2 Hàm Ф-Euler Cho n bất kỳ thuộc N, hàm Ф-Euler của n là số phần tử m thuộc N và nhỏ hơn n và gcd(m, n)=1.
5 Tính chất số học của hàm Ф-Euler k aj Nếu n j 1 p j ở đây pj là các số nguyên tố khác nhau, khi đó LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 6 Tổng quát hóa Định lý nhỏ Fermat Nếu n thuộc N và m thuộc Z sao cho gcd(m, n) = 1, khi đó mФ(n)≡1(modn).3 Thuật toán kiểm định số nguyên tố Miller – Selfridge – Rabin (MSR). Bài toán là kiểm định số n>1 lẻ xem có phải là số nguyên tố hay không. Chúng ta giả sử n-1=2tm, ở đây m là số nguyên lẻ thuộc N và t thuộc N.
Số n được sử dụng trong các bước tính toán sau, trong đó ta sử dụng “thuật toán bình phương và nhân” Bước 1: Chọn ngẫu nhiên số a thỏa 2≤a≤n-2. Bước 2 : Tính x0≡am(modn) Nếu x0 1(mod n) Khi đó ta kết thúc thuật toán và kết luận n có thể là số nguyên tố. Nếu x0 1(mod n) và t=1, ta cũng kết thúc thuật toán và kết luận n là hợp số. Nếu khác, ta đặt j=1 và đi đến bước (3).
Nếu xj≡1(modn) thì ta kết thúc thuật toán và kết luận “n là hợp số”. Nếu xj≡ -1(modn), ta kết thúc thuật toán với kết luận “n có thể là số nguyên tố”. Nếu khác, đặt j=j+1 và đi đến bước (4). Bước 4: Nếu j=t-1, khi đó đi tới bước (5).
Nếu khác, quay lại bước (3). t 1 Bước 5: Tính xt 1 a 2 m (mod n) Nếu xt-1≠-1(modn), khi đó kết thúc thuật toán với kết luận “n là hợp số”. Nếu xt-1≡-1(modn), khi đó kết thúc thuật toán với kết luận “n có thể là số nguyên tố”. Khi đó x0≡227≡645(modn), bởi vậy, ta đặt j=1 và tính x1≡22.27≡1065(modn), bởi vậy, ta đặt j=2 và tính x2≡24.
Như vậy, theo bước (3) của Tiêu chuẩn MRS chúng ta có thể kết luận n là hợp số. Nhận xét: Nếu n là hợp số nhưng theo cở sở a và thuật toán Miller – Selfrdge - Rabin lại được tuyên bố là “nguyên tố theo xác suất” thì n được gọi là số giả nguyên tố mạnh LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 theo cơ sở a. Khi n là hợp số nhưng thuật toán lại tuyên bố n là số nguyên tố với xác suất sai nhiều nhất là 25%.4 Các tiêu chuẩn đường cong Elliptic Trước hết, chúng ta giới thiệu một số kiến thức cơ sở.1 Đường cong Elliptic Giả sử F là trường hữu hạn với các chỉ số đặc trưng không bằng 2 và 3. Nếu a và b thuộc F được cho sao cho 4a3+27b2≠0 trong F, khi đó đường cong Elliptic E được cho trên F được xác định bởi phương trình y2=x3+ax+b thuộc F[x].
Tập tất cả các nghiệm (x, y) thuộc F của phương trình y2=x3+ax+b cùng với 1 điểm O, được gọi là điểm vô hạn, được ký hiệu là E(F), được gọi là tập các điểm =-hữu tỷ trên E. Ví dụ: ( E) y2= x3+2x+9 a= 2; b=9 và xác định trên R. Bây giờ ta xét E trên trường F=(Z19 ; +, * theo md19) 4a3+27b2= 4*8+27*81(mod19)=15 Giá trị Δ( E) = -16(4a3+27b2) được gọi là biệt số của đường cong E.