Bài giảng Nhập môn Số học thuật toán Nguyễn Đạt Thông: Chương 1, 2 (Mới nhất)

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Nhập môn SỐ HỌC THUẬT TOÁN

Nguyễn Đạt Thông

Bộ môn Ứng dụng Tin học

Khoa Toán - Tin học

2010

ndthong@math.hcmus.edu.vn

Nhập môn Số học và Thuật toán 1/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Giới thiệu

Tên học phần: Nhập môn số học thuật toán.

Số tín chỉ: 4.

Chuyên ngành: Phương pháp Toán trong Tin học.

Học phần tiên quyết: Đại số đại cương.

Học phần liên quan:

Phân tích thuật toán. Lý thuyết mã hóa thông tin.

Nhập môn Số học và Thuật toán 2/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Mục tiêu

Cung cấp cho sinh viên các kiến thức cơ bản của số học và thuật toán, bao gồm các định nghĩa, định lý, các bài toán cũng như các vấn đề tiêu biểu trong số học.

Trình bày các ý tưởng và các cài đặt cơ bản của các thuật toán liên quan đến việc biểu diễn, tính toán, giải quyết các vấn đề của số học trên máy tính.

Giới thiệu một số ứng dụng tiêu biểu của số học trong các lĩnh vực mật mã và mã hóa.

Nhập môn Số học và Thuật toán 3/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Yêu cầu

Sinh viên cần tham dự các buổi học lý thuyết và thực hành, tham khảo tài liệu, làm bài tập nhóm, ... để có thể nắm đầy đủ nội dung chương trình.

Sinh viên cần có các kỹ năng tính toán, suy luận, chứng minh, ... để có thể hiểu rõ và nắm vững các kiến thức nền tảng của số học.

Sinh viên cần có các kỹ năng tư duy logic, lập trình, debug, ... để có thể cài đặt và kiểm tra các thuật toán của số học.

Nhập môn Số học và Thuật toán 4/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Nội dung lý thuyết

1 Thuật toán

2 Số nguyên

3 Các hàm số học

4 Thặng dư bình phương

5 Đường cong Elliptic

6 Một số thuật toán phân tích số nguyên

7 Một số thuật toán giải bài toán logarit rời rạc

8 Ứng dụng số học vào lý thuyết mật mã

Nhập môn Số học và Thuật toán 5/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Nội dung thực hành

1 Ngôn ngữ lập trình Python

2 Tính toán trên số nguyên

3 Các hàm số học và tính thặng dư bình phương 4 Tính toán đường cong Elliptic trên trường Zp

5 Kiểm tra số nguyên tố

6 Tìm căn theo modulo n

7 Phân tích số nguyên

8 Giải bài toán logarit rời rạc

Nhập môn Số học và Thuật toán 6/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Tài liệu tham khảo

1 Hà Huy Khoái, Phạm Huy Điển, Số học thuật toán, Hà

Nội, 2002, NXB Đại học Quốc Gia Hà Nội.

2 Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 1997, CRC Press.

3 Douglas R. Stinson, Cryptography - Theory and

Practice, 3rd Edition, Ontario, 1995, CRC Press.

4 David M. Burton, Elementary Number Theory, 2nd Edition, Massachusetts, 1980, Allyn and Bacon.

5 Allen Downey, ThinkPython, Massachusetts, 2008,

Green Tee Press.

Nhập môn Số học và Thuật toán 7/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Tài liệu tham khảo

6 H. C. William, M. C. Wunderlich, On the Parallel

Generation of the Residues for the Contrinued Fraction Factoring Algorithm, Mathematics of Computation Vol 48, 1987, American Mathematical Society.

7 Donald E. Knuth, The Art of Computer Programming,

Vol. 2 - Seminumerical Algorithms, 3rd Edition, Canada, 1998, Addison Wesley.

8 T. M. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd Edition, 2001, The MIT Press.

Nhập môn Số học và Thuật toán 8/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Phương pháp đánh giá

Bài tập lý thuyết và thực hành: 20%

Kiểm tra giữa kỳ: 15%

Thảo luận đề tài: 15%

Kiểm tra cuối kỳ: 50%

Nhập môn Số học và Thuật toán 9/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Câu hỏi

Q & A

Nhập môn Số học và Thuật toán 10/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Chương 1 THUẬT TOÁN

Nguyễn Đạt Thông

Bộ môn Ứng dụng Tin học

Khoa Toán - Tin học

2010

ndthong@math.hcmus.edu.vn

Chương 1: Thuật toán 11/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Thuật toán

Định nghĩa

Thuật toán là một quy tắc để, với những dữ liệu ban đầu đã cho, tìm được lời giải sau một khoảng thời gian hữu hạn.

Tính chất

1 Tính hữu hạn. Thuật toán cần phải kết thúc sau một số hữu

hạn bước. Khi ngừng làm việc, kết quả của thuật toán phải được xác định.

2 Tính xác định. Ở mỗi bước, thuật toán cần phải xác định,

nghĩa là chỉ rõ việc cần làm.

Chương 1: Thuật toán 12/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Ví dụ về thuật toán

Bài toán

Cho n số X[1], X[2], ..., X[n], tìm m và j sao cho

X[k]

m = X[j] = max 1≤k≤n

và j lớn nhất có thể.

Thuật toán

1 [Xuất phát] Đặt j ← n, k ← n − 1, m ← X[n].

2 [Kết thúc] Nếu k = 0, kết thúc.

3 [So sánh] Nếu X[k] ≤ m, chuyển sang bước 5. 4 [Cập nhật] Đặt j ← k, m ← X[k].

5 [Giảm k] Đặt k ← k − 1, quay lại bước 2.

Chương 1: Thuật toán 13/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Độ phức tạp của thuật toán

Độ phức tạp của thuật toán được đo bằng số phép tính nhị phân phải làm khi thực hiện thuật toán.

Với cùng một thuật toán, số phép tính cần thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Nói cách khác, độ phức tạp của thuật toán là một hàm số phụ thuộc độ lớn của đầu vào.

Hàm số độ phức tạp của thuật toán được ước lượng trong trường hợp xấu nhất của thuật toán.

Cỡ n của dữ liệu đầu vào tương đương với cỡ k = [log2 n] + 1 trên máy tính.

Chương 1: Thuật toán 14/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Bậc O-lớn

Định nghĩa

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 một số C > 0 sao cho với n đủ lớn, các hàm f (n) và g(n) đều dương, đồng thời f (n) < Cg(n).

Bậc O-lớn là công cụ được dùng để ước lượng hàm số độ phức tạp của thuật toán.

Nếu hàm số độ phức tạp của một thuật toán được ước lượng bởi O(g), ta nói thuật toán này có độ phức tạp O(g).

Nếu một thuật toán có độ phức tạp O(g), thì cũng có thể nói nó có độ phức tạp O(h) với mọi hàm h > g.

Tuy nhiên, ước lượng độ phức tạp của thuật toán phải là ước lượng tốt nhất có thể để tránh hiểu sai về độ phức tạp thực sự của thuật toán.

Chương 1: Thuật toán 15/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Tính chất của O-lớn

Tính chất

1 Nếu f (n) = adnd + ad−1nd−1 + ... + a1n + a0 thì f (n) = O(nd).

2 Nếu f1(n) = O(g(n)) và f2(n) = O(g(n)) thì f1 + f2 = O(g).

3 Nếu f1 = O(g1) và f2 = O(g2) thì f1f2 = O(g1g2).

thì f = O(g).

4 Nếu tồn tại giới hạn hữu hạn lim n→∞

f (n) g(n)

5 Với mọi số ε > 0, log n = O(nε).

Chương 1: Thuật toán 16/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Độ phức tạp đa thức

Định nghĩa

Một thuật toán được gọi là có độ phức tạp đa thức, hoặc có thời gian đa thức, nếu số các phép tính cần thiết khi thực hiện thuật toán không vượt quá O(logd n), trong đó n là độ lớn của đầu vào, và d là số nguyên dương nào đó.

Nếu một thuật toán có độ phức tạp đa thức và có đầu vào n là một số k-bit thì độ phức tạp của thuật toán này là O(kd), tức một đa thức của k.

Các thuật toán có thời gian O(αn), với α > 1, được gọi là các thuật toán có độ phức tạp mũ, hoặc thời gian mũ.

Các thuật toán có thời gian O(nd) với d > 1 là các thuật toán có độ phức tạp tương đương mũ.

Chương 1: Thuật toán 17/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Độ phức tạp dưới mũ

Ngoài ra còn có những thuật toán có độ phức tạp trung gian giữa đa thức và mũ, được gọi là các thuật toán dưới mũ. Chẳng hạn, thuật toán nhanh nhất được biết hiện nay để phân tích một số nguyên n ra thừa số nguyên tố là thuật toán có độ phức tạp

√

log n log log n

Với một máy tính có khả năng thực hiện 1 triệu phép tính trong 1 giây, thời gian cần thiết để chạy thuật toán này được mô tả trong bảng sau:

Số phép tính bit Thời gian

Số chữ số thập phân 50 75 100 200 300 500

1.4 × 1010 9.0 × 1012 2.3 × 1015 1.2 × 1023 1.5 × 1029 1.3 × 1039

3.9 giờ 104 ngày 74 năm 3.8 × 109 năm 4.9 × 1015 năm 4.2 × 1025 năm

Chương 1: Thuật toán 18/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Câu hỏi

Một thuật toán cần khoảng 1027 năm để hoàn thành thì có thể xem là một thuật toán xác định không?

Có 2 thuật toán phân tích thừa số nguyên tố chạy trên cùng một hệ thống máy tính. Thuật toán thứ nhất mất 3 ngày để hoàn thành, thuật toán thứ hai chạy 27 ngày vẫn chưa xong. Có thể nói thuật toán thứ nhất tốt hơn (hiệu quả hơn) thuật toán thứ hai không?

Có 2 thuật toán sắp xếp dãy số chạy trên cùng một hệ thống máy tính. Để sắp xếp một dãy gồm n phần tử, thuật toán thứ nhất cần thực hiện 2n2 phép tính trong khi thuật toán thứ hai cần 50n log2 n. Có thể nói thuật toán thứ hai phức tạp hơn thuật toán thứ nhất không?

Chương 1: Thuật toán 19/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Chương 2 SỐ NGUYÊN

Nguyễn Đạt Thông ndthong@math.hcmus.edu.vn

Bộ môn Ứng dụng Tin học

Khoa Toán - Tin học

2010

Chương 2: Số nguyên 20/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Hệ cơ số

Định lý

Giả sử b là một số nguyên lớn hơn 1. Khi đó mọi số nguyên n có thể viết duy nhất dưới dạng

n = akbk + ak−1bk−1 + ... + a1b + a0

trong đó aj là số nguyên, 0 ≤ aj ≤ b − 1, j = 0, 1, ..., k và hệ số đầu tiên ak (cid:54)= 0.

Số b được gọi là cơ số của biểu diễn. Các hệ số aj được gọi là các chữ số.

Số chữ số của n khi biểu diễn theo cơ số b là (cid:21)

+ 1

k = [logb n] + 1 =

(cid:20) log n log b

Trong cơ số tùy ý, ta có k = O(log n).

Chương 2: Số nguyên 21/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Biểu diễn và tính toán số nguyên trên máy tính

Các số nguyên được biểu diễn theo cơ số nhị phân trên máy tính.

Các số nguyên lớn hơn cỡ từ w của máy tính sẽ được biểu diễn theo cơ số w.

Để cộng hoặc trừ hai số nguyên k-bit, ta cần O(k) phép tính bit.

Để nhân hoặc chia hai số nguyên k-bit theo qui tắc thông thường, ta cần O(k2) phép tính bit.

Để cải tiến tốc độ nhân hoặc chia hai số nguyên, ta có các thuật toán:

Thuật toán Karatsuba - Ofman (1962).

Thuật toán Sch¨onhage - Strassen (1996).

Chương 2: Số nguyên 22/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Thuật toán Karatsuba - Ofman

Giả sử cần nhân hai số nguyên 2k-bit

a = (a2k−1a2k−2...a1a0)2

b = (b2k−1b2k−2...b1b0)2

Ta tách các số nguyên a, b thành các số nguyên k-bit bằng cách đặt

A1 = (a2k−1a2k−2...ak)2, A2 = (ak−1ak...a1a0)2

B1 = (b2k−1b2k−2...bk)2, B2 = (bk−1bk...b1b0)2

Khi đó a = 2nA1 + A0 và b = 2nB1 + B0.

Kết quả của phép nhân sẽ là

ab = (22k + 2k)A1B1 + 2k(A1 − A0)(B1 − B0) + (2k + 1)A0B0

Thuật toán có độ phức tạp O(klog2 3).

Chương 2: Số nguyên 23/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Thuật toán Sch¨onhage - Strassen

Giả sử cần nhân hai số nguyên (r + 1)k-bit

a = (a(r+1)k−1a(r+1)k−2...a1a0)2

b = (b(r+1)k−1b(r+1)k−2...b1b0)2

Ta tách các số nguyên a, b thành các số nguyên k-bit:

a = Ar2rk + ... + A12k + A0

b = Br2rk + ... + B12k + B0

Thuật toán có độ phức tạp O(klogr+1 (2r+1)).

Bằng các phương pháp tối ưu thuật toán và chọn r thích hợp, Sch¨onhage - Strassen đưa ra thuật toán có độ phức tạp O(k log k log log k).

Chương 2: Số nguyên 24/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Quan hệ đồng dư

Định nghĩa

Giả sử m là một số nguyên dương. Hai số a và b là đồng dư với nhau theo modulo m nếu m chia hết hiệu a − b. Ký hiệu a ≡ b mod m.

Định lý (Wilson)

Số p là nguyên tố khi và chỉ khi (p − 1)! ≡ −1 mod p.

Định lý (Fermat bé)

Nếu p là số nguyên tố và a là số không chia hết cho p thì ap−1 ≡ 1 mod p.

Hệ quả. Nếu p là số nguyên tố và a là số nguyên dương thì ap ≡ a mod p. Hệ quả. Nếu p là số nguyên tố và a là số nguyên không chia hết cho p thì ap−2a ≡ 1 mod p.

Chương 2: Số nguyên 25/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Câu hỏi

Số thập phân x = 2a − 5 được biểu diễn bởi 2 chữ số trong hệ cơ số a, giá trị của a là bao nhiêu?

Làm thế nào để chuyển một số từ hệ cơ số a sang hệ cơ số b?

Làm thế nào để chuyển một số từ hệ cơ số 2 sang hệ cơ số 16 và ngược lại?

Giá trị của (11200121)3 ở hệ cơ số 9 là bao nhiêu?

Nếu nhân hai số có 8 chữ số bất kỳ trong hệ cơ số 16 theo phương pháp thông thường thì cần phải thực hiện khoảng bao nhiêu phép tính bit?

Giả sử x ≡ y mod ni với 1 ≤ i ≤ k, các ni nguyên tố cùng nhau đôi một. Chứng minh rằng x ≡ y mod n1n2...nk.

Chương 2: Số nguyên 26/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Số nguyên tố

Định nghĩa

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 là số nguyên tố thì được gọi là hợp số.

Số các số nguyên tố là vô hạn.

√

Mọi hợp số n đều có ước nguyên tố không vượt quá

Bài toán đặt ra:

Thuật toán kiểm tra một số nguyên n có phải là số nguyên tố hay không.

Thuật toán kiểm tra một số nguyên lớn n có phải là số nguyên tố hay không.

Chương 2: Số nguyên 27/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Định lý số nguyên tố

Định lý

Đặt π(x) là số các số nguyên tố không vượt quá x, ta có

π(x)

lim x→∞

x(log x)−1 = 1

√

Số các số nguyên tố không vượt quá

n là vào khoảng

√ 2 n log n

√

(cid:19)

√

(cid:18) 2

hiện việc kiểm tra, ta cần

C log2 n = C

Nếu chia n cho m cần O(log2 n log2 m) phép tính bit, thì để thực n log n

Để kiểm tra số n gồm 100 chữ số thập phân có phải số nguyên tố không, ta cần khoảng 1050 phép tính bit, tương đương 3.1 × 1036 năm khi thực hiện trên máy tính có khả năng tính 1 triệu phép tính mỗi giây.

Chương 2: Số nguyên 28/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Số giả nguyên tố

Định nghĩa (Số nguyên tố xác suất Fermat)

Giả sử b là một số nguyên dương. Nếu n là số tự nhiên và bn ≡ b mod n, thì n được gọi là số nguyên tố xác suất Fermat cơ sở b.

Định nghĩa (Số giả nguyên tố Fermat)

Giả sử b là một số nguyên dương. Nếu n là hợp số nguyên dương và bn ≡ b mod n, thì n được gọi là số giả nguyên tố Fermat cơ sở b.

Trường hợp gcd(n, b) = 1, n là số giả nguyên tố cơ sở b khi bn−1 ≡ 1 mod n.

Số 561 là một số giả nguyên tố cơ sở 2 do 561 là hợp số và 2560 ≡ 1 mod 561.

Với mỗi cơ sở tùy ý, số các số giả nguyên tố là vô hạn.

Chương 2: Số nguyên 29/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Số Carmichael

Định nghĩa

Hợp số nguyên n thỏa mãn bn−1 ≡ 1 mod n với mọi số nguyên dương b sao cho gcd(n, b) = 1 được gọi là số Carmichael.

2 ...qrk

k , n là số Carmichael khi và chỉ khi với mọi

Định lý Nếu n = qr1 1 qr2 1 ≤ j ≤ k: (qj − 1)|(n − 1).

Tồn tại vô hạn số Carmichael.

Giả sử bn−1 ≡ 1 mod n. Nếu n là số nguyên tố thì b(n−1)/2 ≡ ±1 mod n. Ngược lại, n là hợp số.

Số 561 là số Carmichael.

Chương 2: Số nguyên 30/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Kiểm tra Miller

Định nghĩa

Giả sử n là số nguyên dương lẻ, ta viết n − 1 = 2st, với s ≥ 1 và t lẻ. Ta nói n trải qua được kiểm tra Miller cơ sở b, nếu bt ≡ 1 mod n hoặc b2j t ≡ −1 mod n với 0 ≤ j ≤ s − 1.

Nếu n là số nguyên tố thì n trải qua được kiểm tra Miller với mọi cơ sở b không chia hết cho n.

Nếu hợp số n trải qua được kiểm tra Miller cơ sở b thì nó được gọi là số giả nguyên tố mạnh cơ sở b.

Tồn tại vô hạn số giả nguyên tố mạnh cơ sở 2.

Ví dụ:

Số giả nguyên tố mạnh lẻ cơ sở 2 bé nhất là 2047. Số giả nguyên tố mạnh lẻ cơ sở 2 và 3 bé nhất là 1373653. Số giả nguyên tố mạnh lẻ cơ sở 2, 3 và 5 bé nhất là 25326001. Số giả nguyên tố mạnh lẻ cơ sở 2, 3, 5 và 7 bé nhất là 3215031751.

Chương 2: Số nguyên 31/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Thuật toán Rabin - Miller

Định lý

Nếu n là một hợp số dương lẻ thì tồn tại không quá (n − 1)/4 cơ sở b, 1 ≤ b ≤ n − 1, sao cho n trải qua đuợc kiểm tra Miller.

Ta kết luận số n là số nguyên tố nếu nó trải qua được kiểm tra Miller với hơn (n − 1)/4 cơ sở.

Nếu n là hợp số và số b được chọn ngẫu nhiên sao cho 1 ≤ b ≤ n − 1, thì xác suất để n trải qua được kiểm tra Miller cơ sở b sẽ không quá 1/4.

Nếu n là hợp số và k số được chọn ngẫu nhiên trong {1, ..., n − 1}, thì xác suất để n trải qua được kiểm tra Miller đối với k cơ sở này sẽ không quá 4−k.

Với k đủ lớn (ví dụ k = 20), và n trải qua được kiểm tra Miller đối với k cơ sở ngẫu nhiên, thì ta có thể tin "gần như chắc chắn" n là số nguyên tố.

Chương 2: Số nguyên 32/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Thuật toán Rabin - Miller

Thuật toán

1 [Xuất phát] Đặt c ← 20. Đặt t ← n − 1 và s ← 0. Nếu t còn

chẵn thì đặt t ← t/2 và s ← s + 1.

2 [Chọn b mới] Chọn ngẫu nhiên số b trong khoảng 1 < b < n.

Đặt e ← 1 và tính r ← bt mod n. Nếu r = 1 chuyển sang bước 5.

3 [Bình phương] Nếu b (cid:54)≡ ±1 mod n và e < s − 1, ta đặt r ← r2

và e ← e + 1.

4 [Kiểm tra] Nếu r (cid:54)≡ −1 mod n, kết thúc với kết luận "n là hợp

số".

5 [Kết thúc] Đặt c ← c − 1. Nếu c > 0 quay lại bước 2, ngược lại

thì kết thúc với kết luận "n là số nguyên tố".

Chương 2: Số nguyên 33/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Các số giả ngẫu nhiên

Các số ngẫu nhiên trên máy tính thường được sinh một cách có hệ thống, nghĩa là bằng một phương pháp nào đó.

Dãy số ngẫu nhiên được sinh một cách có hệ thống dĩ nhiên không phải là được chọn ngẫu nhiên. Khi biết số xuất phát, dãy hoàn toàn xác định.

Một ví dụ là phương pháp bình phương - ở giữa của Von Neumann. Để sinh các số ngẫu nhiên có 4 chữ số, ta bắt đầu bởi một số tùy ý, chẳng hạn 9011. Bình phương số này, ta được 81198121. Lấy các số ở giữa là 1981.

Các số nguyên trong dãy được sinh bởi một phương pháp nào đó, nhưng xuất hiện ngẫu nhiên, được gọi là các số giả ngẫu nhiên.

Độ dài lớn nhất của dãy số ngẫu nhiên mà không có số lặp lại được gọi là độ dài tuần hoàn của dãy.

Chương 2: Số nguyên 34/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Phương pháp đồng dư tuyến tính

Chọn các số nguyên m, a, c, x0 sao cho m > 0, 2 ≤ a ≤ m, 0 ≤ c ≤ m, 0 ≤ x0 ≤ m. Dãy các số giả ngẫu nhiên xác định bởi công thức

xn+1 ≡ axn + c mod m

Định lý

mod m

bởi công thức

xk ≡ akx0 + c

Các số giả ngẫu nhiên sinh bởi phương pháp đồng dư tuyến tính cho ak − 1 a − 1

Định lý

Với phương pháp đồng dư tuyến tính, dãy nhận được có độ dài tuần hoàn m nếu và chỉ nếu gcd(c, m) = 1, a ≡ 1 mod p với mọi ước nguyên tố p của m, và a ≡ 1 mod 4 nếu 4|m.

Chương 2: Số nguyên 35/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Định lý cơ bản của số học

Định lý

Mọi số nguyên lớn hơn 1 đều phân tích được một cách duy nhất thành tích các số nguyên tố, trong đó các thừa số được viết với thứ tự không giảm.

n = pr1

1 pr2

2 ...prt

Phân tích trên của các số nguyên được gọi là phân tích ra thừa số nguyên tố.

Phân tích một số nguyên lớn ra thừa số nguyên tố là một bài toán khó của số học.

Bài toán đặt ra:

Thuật toán phân tích một số nguyên ra thừa số nguyên tố.

Thuật toán phân tích một số nguyên lớn n ra thừa số nguyên tố.

Chương 2: Số nguyên 36/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Câu hỏi

Chứng minh rằng nếu ước nguyên tố bé nhất p của số nguyên √ dương n vượt quá 3

n thì n

p là số nguyên tố.

Chứng minh rằng nếu p1 = 6m + 1, p2 = 12m + 1, p3 = 18m + 1 là các số nguyên tố thì p1p2p3 là một số Carmichael.

Chứng minh rằng n = 6601 là một số Carmichael.

Chứng minh rằng n = 2047 = 23.89, là một số giả nguyên tố mạnh cơ sở 2.

Giả sử p là số nguyên tố. Chứng minh rằng a2 ≡ 1 mod p khi và chỉ khi a ≡ ±1 mod p.

Trình bày thuật toán kiểm tra số nguyên tố với xác suất bị sai không quá 0.000001.

Chương 2: Số nguyên 37/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Ước số chung lớn nhất

Định nghĩa

Ước số chung lớn nhất của hai (hoặc nhiều) số nguyên không đồng thời bằng không, là số nguyên dương lớn nhất chia hết các số này. Ký hiệu: gcd(a, b), gcd(a1, a2, ..., an).

Hai số nguyên được gọi là nguyên tố cùng nhau nếu ước số chung lớn nhất của chúng bằng 1.

Mọi ước chung của a và b đều chia hết gcd(a, b).

gcd(a, 0) = |a|, với a (cid:54)= 0. gcd(a + mb, b) = gcd(a, b), với m ∈ Z.

Nếu m > 0, thì gcd(ma, mb) = m gcd(a, b).

Nếu m là một ước chung của a và b, thì gcd( a

m , b

m ) = gcd(a,b) m .

Chương 2: Số nguyên 38/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Thuật toán Euclide

Thuật toán (Euclide)

1 [Kết thúc] Nếu b = 0, dừng với kết quả là a.

2 [Chia Euclide] Tính r ← a mod b, và đặt a ← b, b ← r. Quay

lại bước 1.

Định lý (Lamé)

Số phép chia cần thiết để tìm ước chung lớn nhất của hai số nguyên dương bằng thuật toán Euclide không vượt quá 5 lần số chữ số thập phân của số bé trong hai số đã cho.

Hệ quả. Giả sử a < b, khi đó số các phép tính bit cần thiết để thực hiện thuật toán Euclide là O((log2 a)3).

Chương 2: Số nguyên 39/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Thuật toán J. Stein

Thuật toán J. Stein tìm ước số chung lớn nhất của hai số nguyên được biểu diễn dưới dạng nhị phân.

Các phép chia 2 của thuật toán J. Stein được thực hiện bằng thao tác dịch bit sang phải.

(cid:19)

1 Nếu a, b là các số chẵn, thì gcd(a, b) = 2 gcd

Thuật toán J. Stein dựa trên những nhận xét sau: b 2

(cid:18) a 2

(cid:17)

2 Nếu a chẵn, b lẻ, thì gcd(a, b) = gcd

, b

(cid:16) a 2

3 Nếu a, b đều lẻ thì a − b chẵn và |a − b| < max(a, b).

4 gcd(a, b) = gcd(a − b, b).

Chương 2: Số nguyên 40/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Thuật toán J. Stein

Thuật toán

1 [Tìm lũy thừa 2] Đặt k ← 0. Lặp lại các phép tính sau cho đến

khi ít nhất một trong hai số a, b lẻ:

k ← k + 1, a ← a/2, b ← b/2

2 [Xuất phát] Nếu a lẻ, đặt t ← −b và chuyển sang bước 4. Ngược

lại, đặt t ← a.

3 [Chia đôi t] Đặt t ← t/2.

4 [Kiểm tra t chẵn] Nếu t chẵn, quay lại bước 3.

5 [Sắp xếp lại] Nếu t > 0, đặt a ← t. Ngược lại, đặt b ← −t.

6 [Kết thúc] Đặt t ← a − b. Nếu t (cid:54)= 0, quay lại bước 3. Ngược lại,

kết thúc vói kết quả là a2k.

Chương 2: Số nguyên 41/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Thuật toán Euclide mở rộng

Định lý

Ước chung lớn nhất của hai số nguyên a và b là số d dương nhỏ nhất biểu diễn được dưới dạng tổ hợp tuyến tính của a và b.

Trong một số trường hợp, ta không chỉ cần tìm ước chung lớn nhất của hai số nguyên, mà còn muốn tìm biểu diễn của ước chung này dưới dạng tổ hợp tuyến tính của hai số nguyên ban đầu.

Tiêu biểu là bài toán tìm nghịch đảo của một số nguyên theo modulo n.

Thuật toán Euclide mở rộng nhận đầu vào là hai số nguyên a, b, và cho kết quả là bộ số (m, n, d) sao cho

gcd(a, b) = d = ma + nb

Chương 2: Số nguyên 42/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Thuật toán Euclide mở rộng

Thuật toán

1 [Xuất phát] Đặt (m, n, d) ← (1, 0, a) và (u1, u2, u3) ← (1, 0, b).

2 [Kết thúc] Nếu u3 = 0, kết thúc thuật toán.

(cid:23)

3 [Tính toán] Đặt q =

, và đặt

(cid:22) d u3

(v1, v2, v3) ← (m, n, d) − q(u1, u2, u3)

(m, n, d) ← (u1, u2, u3), (u1, u2, u3) ← (v1, v2, v3)

và quay lại bước 2.

Ở mỗi lần lặp, thuật toán đều đảm bảo các đẳng thức sau

ma + nb = d,

u1a + u2b = u3,

v1a + v2b = v3

Chương 2: Số nguyên 43/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Câu hỏi

Chứng minh rằng một số nguyên x biểu diễn được dưới dạng tổ hợp tuyến tính của a và b khi và chỉ khi x sẽ chia hết cho ước số chung lớn nhất của a, b.

Chứng minh rằng tồn tại vô số cặp (x, y) ∈ Z2 sao cho ax + by = d với d là ước số chung lớn nhất của a và b.

Chứng minh rằng gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).

Chứng minh rằng tồn tại x, y, z ∈ Z sao cho ax + by + cz = gcd(a, b, c).

Chứng minh rằng gcd(ma1, ma2, ..., mak) = m gcd(a1, a2, ..., ak) với m > 0 nào đó.

Chương 2: Số nguyên 44/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Định lý Trung Quốc về phần dư

Định lý

Nếu m1, m2, ..., mr là các số nguyên dương nguyên tố cùng nhau từng cặp, thì hệ phương trình đồng dư

x ≡ a1 mod m1 ... x ≡ ar mod mr

có nghiệm duy nhất theo modulo M = m1m2...mr.

Ta có gcd(Mk, mk) = 1 với Mk = m1m2...mk−1mk+1...mr.

Tồn tại yk sao cho ykMk ≡ 1 mod mk.

Nghiệm của hệ là x = a1y1M1 + a2y2M2 + ... + aryrMr. Nếu x và x(cid:48) là hai nghiệm phân biệt của hệ thì x ≡ ak ≡ x(cid:48) mod mk. Suy ra x ≡ x(cid:48) mod M .

Chương 2: Số nguyên 45/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Định lý Trung Quốc về phần dư

Khi cho trước các module nguyên tố cùng nhau m1, m2, ..., mr, một số dương n < M = m1m2...mr được xác định duy nhất bởi các thặng dư của nó theo modulo mj với j = 1, 2, ..., r.

Chẳng hạn ta có các máy tính với cỡ từ 100, và các module nguyên tố cùng nhau là m1 = 99, m2 = 98, m3 = 97, m4 = 95. Khi đó, các số nguyên bé hơn M = 99.98.97.95 = 89403930 được biểu diễn duy nhất thành bộ 4 số theo modulo m1, m2, m3, m4.

Để cộng các số nguyên n1, n2 < M , ta chỉ cần cộng các thặng dư của chúng theo modulo m1, m2, ..., mr.

Chẳng hạn số x = 123684 được biểu diễn bởi (33, 8, 9, 89) mod (99, 98, 97, 95), số y = 413456 được biểu diễn bởi (32, 92, 42, 16) mod (99, 98, 97, 95). Như vậy, x + y được biểu diễn bởi (65, 2, 51, 10) mod (99, 98, 97, 95).

Dùng định lý Trung Quốc về phần dư, ta tính được x + y ≡ 537140 mod 89403930.

Chương 2: Số nguyên 46/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Tính toán các số nguyên lớn trên máy tính

Bổ đề

Nếu a và b là các số nguyên dương thì thặng dư bé nhất modulo 2b − 1 của 2a − 1 là 2r − 1, trong đó r là thặng dư bé nhất của a modulo b. Nghĩa là nếu a ≡ r mod b, thì 2a − 1 ≡ 2r − 1 mod 2b − 1. Hệ quả. Nếu a và b là các số nguyên dương, thì gcd(2a − 1, 2b − 1) = 2gcd(a,b) − 1.

Hệ quả. gcd(2a − 1, 2b − 1) = 1 khi và chỉ khi gcd(a, b) = 1.

Hệ cơ số của máy tính là hệ cơ số nhị phân, và cỡ từ của máy tính thường là một lũy thừa của 2, chẳng hạn 232 hoặc 264.

Để có thể biểu diễn và tính toán với các số nguyên có cỡ lớn hơn cỡ từ của máy, ta có thể chọn các module nguyên tố cùng nhau có dạng 2a − 1 sao cho tích của các module này đạt (hoặc vượt) cỡ của các số nguyên đó.

Chương 2: Số nguyên 47/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Câu hỏi

Trên một máy tính có cỡ từ là 25, có thể áp dụng định lý Trung Quốc về phần dư để biểu diễn các số có 14-bit được không?

Trong số các số không quá 28, tìm x thỏa hệ phương trình đồng dư x ≡ 3 mod 4, x ≡ 4 mod 5, và x ≡ 6 mod 7.

Giả sử n|ab nhưng n (cid:54) |a và n (cid:54) |b. Chứng minh rằng 1 < gcd(a, n) < n và 1 < gcd(b, n) < n.

Chương 2: Số nguyên 48/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Phân số liên tục

Định nghĩa

Giả sử a và b là các số nguyên dương, a > b. Khi đó, phân số

có

a b

thể viết dưới dạng

= a0 +

a b

c0 b

1 b c0 1

= a0 +

a b

c0 b

a1 +

a2 +

1 ...

. Cách viết trên được gọi là dạng phân số liên tục của số hữu tỷ

a b

Chương 2: Số nguyên 49/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Phân số liên tục

Ký hiệu

+ ... =

= [a0; a1, a2, ...] = a0 +

a b

1 a1+

1 a2+

a0 + 1/(a1 + 1/(a2 + 1/(...))).

Phân số liên tục [a0; a1, a2, ..., an] được gọi là phân số liên tục hữu hạn.

Một số hữu tỷ bất kỳ có thể được biểu diễn dưới dạng phân số liên tục hữu hạn.

Một số thực bất kỳ có thể biểu diễn dưới dạng phân số liên tục, hữu hạn hoặc vô hạn.

Giả sử x = [a0; a1, a2, ..., an, ...], phân số hội tụ riêng thứ k của x là các số

Ck = [a0; a1, a2, ..., ak]

Chương 2: Số nguyên 50/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Các tính chất

Định lý

Giả sử a0, a1, ..., an là các số thực, trong đó a0, a1, ..., an > 0. Đặt

p0 = a0, p1 = a0a1 + 1, pk = akpk−1 + pk−2,

q0 = 1 q1 = a1 qk = akqk−1 + qk−2

Khi đó ta có Ck = [a0; a1, a2, ..., ak] =

pk qk

Định lý

Ta có

i) C1 > C3 > C5 > ... iii) C2j+1 > C2k với mọi j, k

ii) C0 < C2 < C4 < ... Ck = x iv) lim k→∞

Chương 2: Số nguyên 51/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Các tính chất

Định lý

pkqk+1 − pk+1qk = (−1)k+1.

Với mọi k ≥ 1, ta có: Từ đó ta suy ra rằng, các số pk, qk nguyên tố cùng nhau.

Định lý

Giả sử n là một số tự nhiên không chính phương và

là các phân số

pk qk

√

n, P0 = 0, Q0 = 1, và các số αk,

n. Đặt α0 =

hội tụ riêng của Qk, Pk được định nghĩa như sau: √

Pk+1 = akQk − Pk

αk =

Pk + Qk

ak = (cid:98)αk(cid:99)

Qk+1 = (n − P 2

n+1)/Qk

Khi đó ta có:

k − nq2 p2

k = (−1)k−1Qk+1.

Chương 2: Số nguyên 52/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục

Phân tích thừa số nguyên tố

Nếu tìm được các số x, y sao cho x − y (cid:54)= 1 và x2 − y2 = n thì ta tìm được ước số không tầm thường của n.

Nếu tìm được các số x, y sao cho 0 < x < y < n, x + y (cid:54)= n, và x2 ≡ y2 mod n thì gcd(x − y, n) và gcd(x + y, n) là các ước không tầm thường của n, vì n|(x + y)(x − y) nhưng n (cid:54) |(x + y) và n (cid:54) |(x − y).

Theo định lý trên ta có

k−1 ≡ (−1)k−2Qk mod n p2

Nếu tìm được số Qk là một số chính phương với k chẵn, thì có thể tìm được một ước số không tầm thường của n.

Chương 2: Số nguyên 53/54

Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục