Tóm tắt luận văn Thạc sĩ Toán học: Một số thuật toán trong số học ứng dụng

Chia sẻ: Huyen Nguyen My | Ngày: | Loại File: PDF | Số trang:36

Thêm vào BST

Báo xấu

26
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn trình bày một số thuật toán số học và ứng dụng; thuật toán phân tích một số nguyên ra các thừa số nguyên tố bắt đầu từ sàng Eratosthennes, phương pháp RHO của Pollard, phân tích Fermat, phương pháp Squfof, thuật toán Dixon, thuật toán sàng bậc hai.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt luận văn Thạc sĩ Toán học: Một số thuật toán trong số học ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG NGUYỄN THỊ THANH HUYỀN MỘT SỐ THUẬT TOÁN TRONG SỐ HỌC ỨNG DỤNG TÓM TẮT LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp toán sơ cấp Mã số: 8 46 01 13 HÀ NỘI, 2018
Công trình được hoàn thành tại: Trường đại học Thăng Long NGƯỜI HƯỚNG DẪN KHOA HỌC GS TSKH HÀ HUY KHOÁI Phản biện 1: Phản biện 2: Luận văn được bảo vệ trước Hội đồng chấm luận văn tại: Trường đại học Thăng Long Vào hồi 09 giờ 00 ngày 28 tháng 12 năm 2018
Contents Trang Mở đầu 1 Chương 1 Thuật toán và tư duy thuật toán 2 1.1 Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Độ phức tạp của thuật toán . . . . . . . . . . . . . . . . . . . . . 2 1.3 Tư duy thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Chương 2 Một số thuật toán số học thông dụng 4 2.1 Kiến thức cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.1 Tính chia hết . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.2 Số nguyên tố . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.3 Đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.4 Hệ thặng dư và lớp thặng dư . . . . . . . . . . . . . . . . 6 2.1.5 Phân số liên tục . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Một số thuật toán tìm ước chung lớn nhất . . . . . . . . . . . . . 7 2.2.1 Thuật toán Euclid . . . . . . . . . . . . . . . . . . . . . . 7 2.2.2 Thuật toán J.Stein . . . . . . . . . . . . . . . . . . . . . . 7 2.2.3 Thuật toán Euclid mở rộng . . . . . . . . . . . . . . . . . 7 2.2.4 Định lý Fermat nhỏ . . . . . . . . . . . . . . . . . . . . . 9 2.3 Một số thuật toán phân tích số nguyên thành tích các thừa số nguyên tố đặc biệt . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.1 Phân tích số nguyên bằng sàng Erathostenes . . . . . . . 11 2.3.2 Pollard’s rho method . . . . . . . . . . . . . . . . . . . . . 11 2.3.3 Đường cong Eliptic . . . . . . . . . . . . . . . . . . . . . . 13 2.3.4 Phương pháp của Fermat . . . . . . . . . . . . . . . . . . 15 2.3.5 Phương pháp Squfof . . . . . . . . . . . . . . . . . . . . . 16 2.3.6 Thuật toán Dixon . . . . . . . . . . . . . . . . . . . . . . 16 2.3.7 Thuật toán Sàng bậc hai-Quadratic Sieve . . . . . . . . . 17 iii
Chương 3 Hệ mã khóa RSA, chữ ký số và hàm băm mật mã 19 3.1 Hệ mã hóa RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Tạo khóa, mã hóa, giải mã của hệ RSA . . . . . . . . . . . . . . 19 3.3 Chữ ký điện tử-Chữ ký số . . . . . . . . . . . . . . . . . . . . . . 20 3.4 Hàm băm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4.1 Phương thức mã hóa MD5 . . . . . . . . . . . . . . . . . 21 3.4.2 Phương thức mã hóa SHA1 . . . . . . . . . . . . . . . . . 25 Kết luận 31 Tài liệu tham khảo 32 iv
Mở đầu Số học là một môn khoa học lý thú, hấp dẫn những người học và làm toán, các giáo viên, học sinh trên khắp thế giới. Mặc dù khoa học kỹ thuật ngày nay rất phát triển nhưng có những bài toán từ thời cổ đại vẫn còn giá trị đến tận bây giờ và việc đi tìm một thuật toán phân tích số nguyên ra tích các thừa số nguyên tố là một trong những thuật toán như vậy. Chính nhờ độ khó của việc phân tích số nguyên thành tích các thừa số nguyên tố đã là cơ sở cho sự ra đời của mật mã học. Luận văn này trình bày một số thuật toán số học và ứng dụng. Thuật toán phân tích một số nguyên ra các thừa số nguyên tố bắt đầu từ sàng Eratosthennes, phương pháp RHO của Pollard, phân tích Fermat, phương pháp Squfof, thuật toán Dixon, thuật toán sàng bậc hai. Luận văn được chia làm ba chương: 1. Chương 1: Thuật toán và tư duy thuật toán trình bày những khái niệm cơ bản về thuật toán, độ phức tạp và tư duy thuật toán. 2. Chương 2: Một số thuật toán thông dụng trình bày một số kiến thức cơ bản về một số thuật toán số học thông dụng. 3. Chương 3: Hệ mã khóa RSA và chữ ký số trình bày một số ứng dụng của thuật toán phân tích số nguyên thành tích các thừa số nguyên tố vào mật mã và tạo chữ ký số. 1
Chương 1 Thuật toán và tư duy thuật toán Chương này trình bày những khái niệm cơ bản về thuật toán, độ phức tạp và tư duy thuật toán. Nội dung của chương này được hình thành từ tài liệu [1]. 1.1 Thuật toán Định nghĩa 1.1. Thuật toán là một quy tắc, thao tác để với những dữ liệu ban đầu đã cho, ta tìm được lời giải cho bài toán sau một khoảng thời gian hữu hạn. Trong thuật toán cần có: Đầu vào: input. Đầu ra: output. Thuật toán phải bao gồm nhiều bước và phải thỏa mãn yêu cầu sau: 1. Tính hữu hạn 2. Tính xác định 3. Tính hiệu quả 4. Tính phổ dụng 1.2 Độ phức tạp của thuật toán Để ước lượng độ phức tạp của thuật toán, ta dùng khía niệm bậc O-lớn Định nghĩa 1.2. Giả sử f(n) và g(n) là hai hàm xác định trên tập hợp các số nguyên dương. Ta nói f(n)có bậc O-lớn của g(n) và viết: f(n)= O(g(n)) hoặc f=O(g), nếu tồn tại số C ̸= 0, sao cho với n đủ lớn, các hàm f(n) và g(n) đều f (n) dương và lim = C. n→+∞ g(n) 2
Nếu thuật toán có thời gian thực hiện f(n) = O(g(n)) ta nói thời gian thực hiện là cấp g(n). Chúng ta cần lưu ý thêm một điểm sau đây. Trong thực tế chúng ta còn nhắc đến thuật toán ”xác suất” tức là thuật toán phụ thuộc vào một hay nhiều tham số ngẫu nhiên. Những ” thuật toán”này, về nguyên tắc không được gọi là thuật toán, vì chúng có thể, với xác suất quá bé, không bao giờ kết thúc. Tuy nhiên, thực nghiệm chỉ ra rằng, các thuật toán xác suất thường hữu hiệu hơn các thuật toán tất định. Thậm chí, trong rất nhiều trường hợp, chỉ có các thuật toán như thế là sử dụng được. Ta định nghĩa thêm: Lx [u; v] = exp(v(lnx)u .(lnlnx)1−u ). Trong suốt luận văn hàm Ln được dùng để tính thời gian chạy. Ta có: Ln [0; v] = exp(v(lnlnn)) = (lnn)v và Ln [1; v] = exp(v(lnn)) = nv . Thời gian chạy Ln [u, v] với u < 0 và v là hằng số là thời gian mũ(subexponential time.) 1.3 Tư duy thuật toán Tư duy thuật toán là sự tổng hợp các năng lực tư duy để giải quyết vấn đề theo một quy trình xác định hướng đến một tác nhân tương thích (tác nhân ở đây muốn nói là con người, máy tính, hay bất cứ một thiết bị nào có chức năng tính toán tự động có thể hiểu và thực hiện được thuật toán). Tư duy thuật toán luôn định hướng vào việc mở ra một con đường lớn, một giải pháp vạn năng cho việc giải quyết hàng loạt vấn đề. Tư duy thuật toán giúp làm thay đổi quan điểm nhìn nhận vấn đề và thay đổi thói quen làm toán cho học sinh thay vì làm theo mẹo mực biến đổi thì sẽ làm toán theo cơ bản và có tính ứng dụng rộng rãi, tổng quát cho nhiều trường hợp. Thuật toán có các đặc điểm[1]: Đó là một dãy hữu hạn các bước sắp xếp theo một trình tự nhất định Mỗi bước là một thao tác sơ cấp, trường hợp đặc biệt cũng có thể là một thuật toán đã biết. Các bước rõ ràng, thao tác chính xác (trong cùng một điều kiện, hai bộ xử lí cùng thực hiện một thuật toán thì phải cho ra cùng một kết quả). Có tính kết thúc Tư duy thuật toán là cách suy nghĩ để nhận thức, để giải quyết vấn đề một cách có trình tự (sắp xếp lần lượt, thứ tự trước sau).[1] 3
Chương 2 Một số thuật toán số học thông dụng Chương này trình bày những kiến thức cơ bản của số học và một số thuật toán số học thông dụng. Nội dung của chương này cơ bản được hình thành từ các tài liệu [2] và [3]. 2.1 Kiến thức cơ bản Mục này trình bày một số khái niệm cơ bản số học như tính chia hết, số nguyên tố, đồng dư, thặng dư, ... cần thiết cho nội dung của luận văn. 2.1.1 Tính chia hết Định nghĩa 2.1. Chúng ta ký hiêu: N: tập hợp của các số tự nhiên. Z+ = {0, 1, ...}: tập các số nguyên không âm. Z: tập các số nguyên. Q: tập các số hữu tỉ. R, R1 : tập các số thực. Định nghĩa 2.2. Với hai số nguyên a, b, a ̸= 0 ta nói a chia hết b đối với số nguyên c nào đó, nếu b = ac và ký hiệu a|b. Ta cũng nói b chia hết cho a, hay . là bội của a và viết b..a. Định lý 2.1. Với mọi số nguyên dương a, b tồn tại duy nhất cặp số nguyên không âm (q, r) sao cho: b = aq + r, r < a. Định nghĩa 2.3. Trong định lý trên, khi a là số chia hết b thì số q được gọi là thương(quotient). Số r được gọi là số dư(remainder). 4
Nhận xét 2.1. Thuật toán chia có thể mở rộng ra tập số nguyên Z như sau. Với mọi số nguyên a, b, a ̸= 0, tồn tại duy nhất cặp số nguyên (q, r) ∈ Z × Z, sao cho b = aq + r, 0 ≤ r < |a|. 2.1.2 Số nguyên tố Định nghĩa 2.4. Số nguyên tố là số nguyên lớn hơn 1, không chia hết cho số nguyên dương nào ngoài 1 và chính nó. Số nguyên lớn hơn 1 không phải số nguyên tố được gọi là hợp số. Các tính chất của số nguyên tố: Định lý 2.2. (Euclid) i) 2 là số nguyên tố nhỏ nhất và là số chẵn duy nhất. ii) Số các số nguyên tố là vô hạn. √ Định lý 2.3. Mọi hợp số n đều có ước nguyên tố không vượt quá n. Với mỗi số thực dương x cho trước, ta kí hiệu π(x) là số các số nguyên tố không vượt quá x. Khi đó, ta có: π(x) Định lý 2.4. lim x =1 n→+∞ logx √ √ √ n 2 n Như vậy, số các số nguyên tố không vượt quá n là vào khoảng √ log n = logn . Định lý 2.5. Mọi số nguyên tố lớn hơn 1 đều phân tích được một cách duy nhất thành tích các thừa số nguyên tố, trong đó, các thừa số viết với thứ tự không giảm. 2.1.3 Đồng dư Trong phần này chúng ta hiểu các chữ ký hiệu thay số là các số nguyên. Định nghĩa 2.5. Giả sử n là một số nguyên dương. Ta nói, hai số nguyên a, b là đồng dư với nhau theo modulo n nếu a − b chia hết cho n và ký hiệu a ≡ b(mod n). Hệ thức trên gọi là đồng dư thức. Như vậy, a ≡ b(mod n) khi và chỉ khi tồn tại số nguyên k, sao cho: a = b + kn. Nếu a ̸≡ b(mod n) có nghĩa là a − b không chia hết cho n. . Định nghĩa 2.6. Nếu a ≡ 0(mod n) thì ta nói a chia hết cho n và ký hiệu a..n. Chúng ta cũng nói n là ước của a. Ước chung lớn nhất của hai số a, b được ký hiệu là gcd(a, b). 5
Định nghĩa 2.7. (Nguyên tố cùng nhau). Hai số nguyên a, b được gọi là nguyên tố cùng nhau nếu gcd(a, b) là 1. Định nghĩa 2.8. (Phần tử nghịch đảo). Nếu hai số nguyên a và n nguyên tố cùng nhau, tồn tại số nguyên x sao cho: a.x ≡ 1(mod n) thì ta gọi x là phần tử nghịch đảo của a trong phép modulo cho n và ký hiệu là a−1 . 2.1.4 Hệ thặng dư và lớp thặng dư Định nghĩa 2.9. Giả sử m và r là số tự nhiên và 0 ≤ r ≤ m − 1. Ký hiệu Ar là tập hợp tất cả các số nguyên đồng dư với r theo modulo m và được gọi là lớp thặng dư modulo m. Mỗi phần tử của Ar được gọi là một thặng dư modulo m. 2.1.5 Phân số liên tục Định nghĩa 2.10. Cho a, b là các số nguyên, b > 0. Thực hiện thuật toán Euclid ta được: a = ba0 , 0 ≤ c0 < b b = c 0 a1 + c 1 , 0 ≤ c1 < c 0 ··· cn−3 = cn−2 an−1 + cn−1 , 0 ≤ cn−1 < cn−2 , cn−2 = cn−1 an . a Như vậy, phân số b có thể viết: a b = a0 + c0 b = a0 + 1 b = · · · = a0 + a1 + 1 1 . c0 ···+an−1 + a1 n a Cách viết trên được gọi là biểu diễn số hữu tỷ b dưới dạng phân số liên tục. Chúng ta quan tâm đến các định lý sau(phần chứng minh xem [1]) Định lý 2.6. Giả sử a0 , a1 , · · · , an , · · · là các số thực, trong đó a1 , · · · , an > 0. Đặt b0 = a0 , b1 = a1 b0 + 1, q0 = 1, q1 = a1 , và với mỗi k ≥ 2, bk = ak bk−1 + bk−2 , qk = ak qk−1 + qk−2 . Khi đó, i) Ck = [a0 ; a1 , · · · , ak ] = qbkk . ii) Với mỗi k ≥ 1, ta có bk qk−1 − bk+1 qk = (−1)k+1 . Định lý 2.7. Giả sử n là số không chính phương và qbkk là các phân số hội tụ √ √ riêng của n. Ta đặt α0 = n, và các số αk , Qk , Pk được định nghĩa như sau: √ Pk + n αk = , Qk ak = [αk ], Pk+1 = ak Qk − Pk , (n − Pk+1 2 ) Qk = . Qk 6
Khi đó, ta có: b2k − nqk2 = (−1)k+1 Qk+1 . Hệ quả 2.1. Giả sử n là số tự nhiên không chính phương. Gọi qbkk là các phân √ số hội tụ riêng của n. Thế thì, đồng dư b2k mod n lấy theo thặng dư tuyệt đối √ bé nhất, có giá trị tuyệt đối bé hơn 2 n. 2.2 Một số thuật toán tìm ước chung lớn nhất 2.2.1 Thuật toán Euclid Định lý 2.8. Với mọi số nguyên a ≥ 0; b > 0 thì gcd(a, b) = gcd(b, a mod b). Thuật toán Euclid:a hoặc b bằng 0 trả về gcd(a,b)= 0. function gcd(a,b) begin while b ̸= 0 do begin r := a mod b; a := b; b := r; end; Result:=a end; 2.2.2 Thuật toán J.Stein Năm 1967 J.Stein xây dựng một thuật toán khá thuận tiện để tìm UCLN trong trường hợp các số đã cho viết dưới dạng nhị phân. Thuật toán trên dựa trên những nhận xét đơn giản sau: 1. gcd(a, 0)=a trong trường hợp đặc biệt thì gcd(0, 0) = 0 ( ) 2. Nếu a, b là các số chẵn thì (a, b) = 2 a2 , 2b ; ( ) 3. Nếu a chẵn, b lẻ, thì (a, b) = a2 , b ; 4. Nếu a, b đều lẻ thì a − b chẵn và | a − b |< max (a, b) . (a, b) = (a − b, b) Định lý 2.9. Nếu N có các ước không tầm thường s, t với N = s.t và s ≤ t, √ thì s ≤ N . 2.2.3 Thuật toán Euclid mở rộng Thuật toán Euclid mở rộng hơn thuật toán Euclid ở điểm trong trường hợp a và b nguyên tố cùng nhau gcd(a, b) = 1 với b ≥ a > 0 thì thuật toán cho biết thêm a−1 của a trong phép chia modulo b tức là: a.a−1 ≡ 1(mod b) 7
Định nghĩa 2.11. Nếu số nguyên dương a và số nguyên b nguyên tố cùng nhau thì tồn tại duy nhất một số x ∈ {0, 1, 2, · · · , b − 1} sao cho ax ≡ 1(mod b). Số x này được gọi là nghịch đảo của a theo modulo b (hoặc ngược lại, nói a là nghịch đảo của x (mod b). Ký hiệu a−1 ≡ x(mod b) hoặc x−1 ≡ a(mod b). Tìm nghịch đảo của a theo modulo b. Ta có: . (ax − 1) .. b ⇔ ax − 1 = by ⇔ ax − by = 1. Vậy, nghịch đảo của a theo modulo b tồn tại khi và chỉ khi gcd(a, b) = 1. Thuật toán Euclid mở rộng Việc xác định các số nguyên x và y với ax + by = gcd(a, b) được biết đến như là thuật toán Euclid mở rộng. Ta có: gcd(x, 0) = x. gcd(x, z) = gcd(z, x mod z) nếu z ̸= 0. Nếu x ≥ z và phần dư không âm nhỏ nhất được thay thế, cặp ’mới’ (z, x mod z) là nhỏ hơn so với cặp cũ (x, z). Cho hai số nguyên không âm u,v tìm (u1 ; u2 ; u3 ) sao cho: (u, v) = u3 = uu1 + uu2 . Trong tính toán, ta thêm các ẩn phụ (v1 ; v2 ; v3 ), (t1 ; t2 ; t3 ) và luôn có trong mọi bước các đẳng thức sau: ut1 + vt2 = t3 , uv1 + vv2 = v3 ; uu1 + vv2 = v3 Đặt (u1 ; u2 ; u3 ) ← (1, 0, u), (v1 ; v2 ; v3 ) ← (0, 1, v) Kiểm tra v3 = 0 thuật toán kết thúc. [ ] Đặt:q ← uv33 , và sau đó ta đặt (t1 ; t2 ; t3 ) ← (u1 ; u2 ; u3 ) − q (v1 ; v2 ; v3 ) , (u1 ; u2 ; u3 ) ← (v1 ; v2 ; v3 ) , (v1 ; v2 ; v3 ) ← (t1 ; t2 ; t3 ) và quay về bước 2. Giả sử rằng, 0 ≤ x < z chúng ta có: r1 = 0, s1 = z, r2 = 1, và s2 = x. 8
Dòng thứ (i + 1) theo sau từ thứ (i − 1) và i bằng cách khấu trừ lần thứ i càng nhiều càng tốt từ lần thứ (i − 1), mà không làm cho phía tay phải của kết quả của dòng thứ (i + 1) là âm. Quá trình chấm dứt ngay khi một số si = 0; nếu sk = 0 sau đó sk−1 = gcd(x, z) và nếu sk−1 = 1, thì (rk−1 ≡ x1 mod z) Thuật toán Euclid mở rộng: Cho a, b không đồng thời bằng 0, trả về cặp (x,y): a.x + b.y = gcd(a, b). Về tư tưởng là quá trình tính cặp số (x, y) vào trong vòng lặp chính của thuật toán Euclid function Extended gcd(a, b); Begin (xa , ya ) := (1, 0); (xb , yb ) := (0, 1); while b ̸= 0 do Begin [a] q := b r := a mod b; a := b; b := r (xr , yr ) := (xa , ya ) − q.(xb , yb ) (xa , ya ) := (xb , yb ); (xb , yb ) := (xr , yr ); end result := (xa , ya ) end 2.2.4 Định lý Fermat nhỏ Định lý 2.10. Nếu p là một số nguyên tố, thì với số nguyên a bất kỳ, không chia hết cho p thì ap−1 − 1 sẽ chia hết cho p hay ap−1 ≡ 1 mod p. Định nghĩa 2.12. Số Carmichael: Hợp số n là số Carmichael nếu nó là số giả nguyên tố Fermat với mọi cơ sở a: ƯCLN (a, n) = 1. 2 • Gần đây đã chứng minh được có vô số số Carmichael. Có ít nhất x 7 trong số chúng ≤ x, một khi x đủ lớn. Điều này làm mất hiệu lực của phép thử dựa trên định lý nhỏ Fermat: Cho một số Carmichael p thử nghệm ap−1 ≡ 1 mod p không bao giờ thất bại, nếu p và a nguyên tố cùng nhau, và do đó không bao giờ chứng minh được p là hợp số. Nhưng nhờ giải thuật kiểm tra Miler-Kabin-thuật toán xác suất để kiểm tra tính nguyên tố. 9
Kiểm tra Miler-Rabin: Bổ đề 2.1. Với p là số nguyên tố, x là số nguyên: x2 ≡ 1( mod p) khi và chỉ khi x ≡ 1( mod p) hoặc x ≡ (p − 1)( mod p). Bổ đề 2.2. Với p là số nguyên tố, x là số nguyên: x2 ≡ 1( mod p) khi và chỉ khi x ≡ 1( mod p) hoặc x ≡ (p − 1)( mod p). p là số nguyên tố viết lại p dưới dạng p = 2k .q + 1 trong đó q là số lẻ, a là số nguyên dương bé hơn p. Ta có: • Hoặc aq ≡ 1( mod p). k−1 • Hoặc trong dãy số aq ; a2q ; a4q ; · · · ; a2 q tồn tại một số mà đồng dư với (p − 1) mod p. Thuật toán Miller-Rabin kiểm tra tính nguyên tố của số nguyên p. Định nghĩa 2.13. Giả sử n là số nguyên dương lẻ n − 1 = 2s .t trong đó s là số nguyên không âm, t là số nguyên dương lẻ. Ta nói n được kiểm tra Miller cơ j sở b, nếu hoặc bt ≡ 1 mod n hoặc b2 .t ≡ −1 mod n với j nào đó, 0 ≤ j ≤ s − 1. INPUT Số tự nhiên lẻ N. OUTPUT N là số nguyên tố: TRUE/FALSE. MR1.(Xuất phát): Phân tích Đặt q ← N − 1, t ← 0 và nếu q chẵn ta đặt q ← 2q , t ← t + 1 (bây giờ ta có) N − 1 = 2t .q , q lẻ. Sau đó, đặt c ← 20. MR2.(Chọn a mới): Chọn ngẫu nhiên số tự nhiên a trong khoảng 1 < a < N. Đặt e ← 0, b ← aq mod N . Nếu b = 1, chuyển sang MR4. MR3.(Bình phương): Nếu b ̸≡ ±1( mod N ) và e < t − 2 ta đặt b := b mod N , e ← e + 1. Nếu b ̸= N − 1,in ra thông báo ”n là hợp số” và kết 2 thúc thuật toán. MR4. Đặt c ← c − 1. Nếu c > 0, chuyển sang MR2.Nếu c = 0 in ra thông báo ”N là số nguyên tố”. Trả lời FALSE. Kết thúc. Đối với số lẻ n có thể chứng minh rằng một số nguyên ngẫu nhiên được chọn một ∈ (2, 3, ..., n − 1) có cơ hội ít nhất 75% không thỏa mãn các điều kiện này và do đó là một chứng minh cho tính hợp nhất của n xem [38,49]); xem thêm [3]. Điều này chứng tỏ n là hợp số. 10
Định lý 2.11. Nếu p là một hợp số dương lẻ thì tồn tại không quá p−1 4 cơ sở b, 1 ≤ b ≤ p − 1 sao cho p trải qua được kiểm tra Miler đối với các cơ sở đó. (xem [1]) 2.3 Một số thuật toán phân tích số nguyên thành tích các thừa số nguyên tố đặc biệt 2.3.1 Phân tích số nguyên bằng sàng Erathostenes Theo định lý 2.4 ở chương I để tìm một ước số nguyên tố của một hợp số √ N ta phải chia N cho các số nguyên tố không vượt quá N. • Ưu điểm: sàng của Erathostenes cho ta thuật toán xác định mọi số nguyên tố không vượt quá một số cho trước. Đối với hầu hết các con số, nó rất hiệu quả vì hầu hết các con số đều có các ước nguyên tố nhỏ: 88% số nguyên dương có một ước nguyên tố < 100, và gần 92% có ước nguyên tố < 1000. • Nhược điểm: độ phức tạp quá lớn. Bởi vì, theo định lý (số nguyên tố): limx→∞ ( π(x) x ) = 1. trong đó π(x) là các số nguyên tố không vượt lnx √ quá √ x. Như vậy, số các số nguyên tố không vượt quá n là vào khoảng n √ √ = ln2 √nn . Chúng ta cần O(log2 n. log2 m) phép tính bit để chia n cho ln n m. Như vậy, số các phép tính bit cần thiết để phân tích số n vào khoảng √ √ 2 n ln n .C. log2 n = C n. Nếu n vào cỡ khoảng 100 chữ số thập phân, thì số các phép tính phải dùng cỡ 1050 . Với những máy tính thực hiện cỡ một triệu phép tính một giây, thời gian cần thiết sẽ vào khoảng 3, 1.1036 năm.(xem [1]) Vì vậy, chúng ta ít dùng để xác định xem một số có phải số nguyên tố hay không? 2.3.2 Pollard’s rho method Pollard sử dụng một hàm giả ngẫu nhiên để sinh dãy x1 ; x2 ; · · · ; xk . Hàm đơn giản nhất thỏa mãn chính là: f (x) = x2 + 1 mod N (1). Như vậy, chúng ta chỉ sinh ra một số x1 hoàn toàn ngẫu nhiên và các phần tử còn lại sẽ được sinh dựa trên hàm f (x). Dãy số ngẫu nhiên ta thu được cuối cùng là: x1 ; x2 = f (x1 ); x3 = f (x2 ); · · · ; xk = f (xk−1 )(2). Do dãy x2 ; x3 ; · · · ; xk được sinh bởi hàm f(x), nếu tồn tại xi ≡ xj mod p thì ta dễ dàng suy ra: xi+1 ≡ xj+1 mod p, xi+2 ≡ xj+2 mod p, · · · (3). 11
Nói cách khác, ta sẽ có một vòng trong các dãy số bởi f (x) khi lấy mod p (giống như hình vẽ vòng liên kết ở trên). Những ý tưởng này có thể được kết hợp thành một thuật toán theo cách sau: • Chọn f (x) = x2 + 1 • Chọn một giá trị x0 nào đó và tính theo phép lặp bởi ánh xạ f dãy sau: x1 = f (x0 ), x2 = f (x1 ), · · · , x( j + 1) = f (xj ), j = 0; 1; 2; · · · Sau đó, xét hiệu giữa các xj với hi vọng tìm thấy xj , xk nào đó sao cho: xj ∈ / xk ( mod n) nhưng xj ≡ xk ( mod n), trong đó d là một ước không tầm thường nào đó của n. Khi đó, bằng cách tính (xj − xk , n) ta thu được một ước thực sự của n. ρ Figure 2.1: rho Thuật toán: INPUTS: n là số nguyên cần phân tích. f(x) là hàm tạo số giả ngẫu nhiên. OUTPUT: Ước thực sự(̸= 1; ̸= n) của n hoặc không thực hiện được 1)x ← 2; y ← 2; d ← 1 2)While d = 1 • x ← f (x) • y ← f (f (x)) • d ← gcd(| x − y |, n) 3) Nếu d = n, return (không thực hiện). 4)Else, return d. 12
Thành công đáng chú ý nhất của phương pháp rho của Pollard cho tới nay là khám phá vào năm 1980 bởi Brent và Pollard về việc phân tích nhân tố số 8 Fermat thứ tám (xem [2]): 22 + 1 = 1238926361552897.p62 trong đó p62 biểu thị số nguyên tố 62 chữ số. Pollard’s p − 1 method Giả sử cần phân tích số nguyên n và p là một ước nguyên tố của n. Nếu p − 1 không có các ước nguyên tố lớn thì thuật toán p − 1 của Pollard là rất hiệu quả. Thuật toán 1) Chọn một số k sao cho nó chia hết cho hầu hết các số nguyên nhỏ hơn một số B nào đó. Chẳng hạn k là B! hoặc k là bội chung nhỏ nhất của tất cả các số từ 1 đến B . 2) Chọn ngẫu nhiên một số nguyên a trong khoảng từ 2 đến n − 2. 3) Tính ak ( mod n) (bằng thuật toán bình phương liên tiếp). 4) Tính (ak − 1, n) (Bằng thuật toán Euclid.) 5) Nếu d = (ak − 1, n) không phải là một ước thực sự của n, ta lặp lại quá trình trên với một số a khác, hoặc k khác(hoặc cả a và k khác). Nhược điểm của phương pháp (p − 1) của Pollard là nó làm việc có hiệu quả nếu thừa số của nó có yếu tố p : p − 1 là B -mịn nên phương pháp này chỉ hiệu quả khi có chút may mắn. Thuật toán đường cong elliptic mạnh hơn được Lesntra xây dựng vào những năm 1980 trên thực tế là sự tổng quát hóa của phương pháp p − 1 Pollard. Phương pháp đường cong eliptic khắc phục hoàn toàn được nhược điểm trên. Trong bất kỳ thử nghiệm nào trong đó mỗi lần thử nghiệm bất kỳ không cần yếu tố may mắn. Một thử nghiệm thành công nếu một số ngẫu nhiên gần với một số nguyên tố của n là B− mịn. 2.3.3 Đường cong Eliptic Đường cong elliptic được Lenstra đề xuất, và độ phức tạp của phương pháp 1 này là e((2+o(1)) log p log log p) 2 . Phép cộng: Để xác định điểm R(xR ; yR ) = P (xP ; yP ) + Q(xQ ; yQ ) ta tính xR và yR như sau: yQ − yP λ= mod n x Q − xP xR = (λ2 − xP − xQ ) mod n yR = (λ(xP − xQ ) − yP ) mod n 13
-Điểm tại vô cùng O là điểm cộng với bất kỳ điểm nào cũng sẽ ra chính điểm đó. Nghĩa là :∀P ∈ E, P + O = O + P = P -Điểm đối xứng của P (xP ; yP ) ∈ E là −P (xP ; yP ) ∈ E thỏa mãn các điều kiện: yP′ ∈ ZP sao cho (yP′ + yP ) mod n;P + (−P ) = 0 Phép nhân đôi: -Để xác định điểm R(xR ; yR ) = 2P (xP ; yP ) với yP ̸= 0, ta tính xR và yR như sau: 3x2P + a λ= mod p. 2yP xR = (λ2 − 2xP ) mod p. yR = (λ(xP − xR ) − yP ) mod p. Mở rộng ra,phép nhân kP nhận được bằng cách thực hiện k lần phép cộng. Thuật toán nhân đôi và thêm cho ta cách làm như sau: • Lấy P • Tăng gấp đôi để được 2P • Thêm P vào 2P để được 21 P + 20 P • Nhân đôi 2P để được 22 P • Thêm vào để được 22 P + 21 P + 20 P • Gấp đôi 22 P để được 23 P • Gấp đôi 23 P để được 24 P • Thêm nó vào kết quả trước để được 24 P + 23 P + 22 P + 21 P + 20 P • … • Cuối cùng chúng ta tính toán 151P thực hiện chỉ bảy lần nhân đôi và bốn phép cộng bổ sung Thuật toán nhân tử hóa với một đường cong elliptic Cho k là hợp số sao cho k = k1 .k2 khi đó ta có thể tính kP = k1 (k2 P ). Đầu vào của thuật toán là số tự nhiên n và các tham số v; w ∈ N , phụ thuộc vào n. Cũng như a; x; y ∈ Zn , sao cho P (x; y; 1) ∈ Vn từ y 2 = x3 + ax + b ⇔ b ≡ y 2 − x3 − ax( mod n) thỏa mãn điều kiện (4a3 + 27b2 ∈ Zn. ) Thuật toán tìm kiếm ước số tự nhiên d của số n: 1 < d < n. Đối với từng số r ∈ N, √ e(r) = max {m |∈ Z≥0 , rm ≤ v + 2 v + 1}, và sau đó: 14
∏ k= re(r) (r là số nguyên tố; e(r) là một số nguyên dương)2 ≤ r ≤ w chúng ta giả sử: Giả sử P (x : y : 1) ∈ Vn .Khi đó,P nằm trên đường cong Eliptic Ea;b ttrong vành Zn , được xác định bởi phương trình y 2 = x3 + ax + b. Chúng ta tính điểm kP,nếu trong quá trình tính toán tìm được ước của số n,1 < d < n, thì chúng ta phân tích được n ra thừa số và thuật toán dừng.Nếu như tìm được kP và không tìm được d thì thuật toán dừng và thông báo và thuật toán phân tích thành nhân tử không thành công.Thuật toán kết thúc. Định lý 2.12. Giả sử E là đường cong elliptic cho bởi phương trình y 2 = x3 + ax + b, trong đó a, b ∈ Z và (4a3 + 27b2 , n) = 1. Giả sử P1 và P2 là hai điểm trên E có mẫu số của các tọa độ nguyên tố cùng nhau với n, đồng thời P1 ̸= −P2 . Khi đó điểm P1 + P2 có tọa độ với mẫu số nguyên tố cùng nhau với n nếu và chỉ nếu không tồn tại ước nguyên tố nào của n, p | n với tính chất sau đây. Các điểm P1 mod P và P2 mod P trên E mod p có tổng là điểm O mod p ∈ E mod p. (E mod p là đường cong trên trường Fp nhận được bằng cách lấy đồng dư rút gọn modulo p các hệ số của phương trình y 2 = x3 + ax + b.) Thuật toán nhân tử hóa với một đường cong elliptic. Cho k là hợp số sao cho k = k1 .k2 khi đó ta có thể tính kP = k1 (k2 P ). Đầu vào của thuật toán là số tự nhiên n và các tham số v; w ∈ N , phụ thuộc vào n. Cũng như a; x; y ∈ Zn , sao cho P (x; y; 1) ∈ Vn từ y 2 = x3 + ax + b ⇔ b ≡ y 2 − x3 − ax( mod n) thỏa mãn điều kiện (4a3 + 27b2 ∈ Zn. ) Thuật toán tìm kiếm ước số tự nhiên d của số n : 1 < d < n. Đối với từng số r ∈ N, √ e(r) = max {m |∈ Z≥0 , rm ≤ v + 2 v + 1}, và sau đó: ∏ k = re(r) (r là số nguyên tố; e(r) là một số nguyên dương)2 ≤ r ≤ w Giả sử P (x : y : 1) ∈ Vn . Khi đó, P nằm trên đường cong elliptic Ea;b trong vành Zn , được xác định bởi phương trình y 2 = x3 + ax + b. Chúng ta tính điểm kP , nếu trong quá trình tính toán tìm được ước của số n, 1 < d < n, thì chúng ta phân tích được n ra thừa số và thuật toán dừng. Nếu như tìm được kP và không tìm được d thì thuật toán dừng và thông báo và thuật toán phân tích thành nhân tử không thành công. Thuật toán kết thúc. 2.3.4 Phương pháp của Fermat Tính gcd(n; xy) tính ước số chung lớn nhất của n và xy . Nếu n là hợp số, không phải là số nguyên tố, và x, y là các số nguyên ngẫu nhiên thỏa mãn 15
x2 ≡ y 2 thì có ít nhất 50% cơ hội cho gcd(x − y; n) và gcd(x + y; n) các thừa số không nhỏ của n. Thuật toán Phân tích hợp số n √ 1) Chọn số nguyên x > n. 2) Kiểm tra xem x2 − n có là số chính phương không? • Nếu x2 − n không là số chính phương, thì ta quay lại bước 1 và tăng giá trị của x. • Nếu x2 − n là số chính phương y 2 , thì ta chuyển sang bước sau. 3) n = x2 − y 2 = (x − y)(x − y). 2.3.5 Phương pháp Squfof Squfof là từ viết tắt của”square form factorization” phân tích các dạng chính phương. Ta xuất phát từ nhận xét sau đây: Nếu ta tìm được các số x, y sao cho:x − y ̸= 1 và x2 − y 2 = n thì ta tìm được ước số không tầm thường của n vì n = x2 − y 2 = (x + y)(x − y). Bây giờ, ta có kết quả yếu hơn: Giả sử có x, y : x2 ≡ y 2 ( mod n) và 0 < x < y < n, x + y ̸= n khi đó n là một ước của tích (x + y)(x − y) và rõ ràng n không là ước của x + y cũng như x − y và do đó d1 = gcd(x − y, n) và d2 = gcd(x + y, n) là các ước số không tầm thường của n. Các ước số này được tìm nhanh chóng thông qua thuật toán Euclid. Từ định lý 2.9 cho ta phương pháp tìm x, y cần thiết. Ta có p2k ≡ (−1)k+1 Qk+1 ( mod n) như vậy, ta phải tìm được các Qk+1 với chỉ . số chẵn và là số chính phương y 2 thì x2 ≡ y 2 ( mod n). Khi đó, (xk +y)(xk −y)..n. Như vậy, các ước số chung lớn nhất d1 = (xk + y, n) và d2 = (xk − y, n) , có nhiều khả năng là các ước không tầm thường của n, vì các số xk + y, xk − y, không nhất thiết bé hơn n. 2.3.6 Thuật toán Dixon Thuật toán: INPUTS: Số nguyên n cần kiểm tra. Bước 1: Chúng ta cần tìm các số m1 , · · · , mk+1 bằng cách lựa chọn ngẫu nhiên sao cho: 1 < mi < n α α Q(mi ) = p1 i,1 ...pk i,k m2i ≡ Q(mi )( mod n). 16