Giải thuật trên số: Bài giảng Giải thuật nâng cao của TS. Ngô Quốc Việt

MỘT SỐ GIẢI THUẬT TRÊN SỐ

TS. NGÔ QUỐC VIỆT 2016

Nội dung 1. Giới thiệu 2. Phép chia và số học modular 3. Bài toán đồng dư và ứng dụng 4. Số nguyên tố

Giải thuật nâng cao-Một số giải thuật trên số

Giới thiệu

• Lý thuyết số khảo sát số nguyên, các tính chất và

các ứng dụng liên quan.

• Khảo sát: một số ký hiệu, thuật ngữ, định lý liên

quan

• Lý thuyết số ứng dụng trong nhiều giải thuật quan trọng: hàm băm, mã hóa, chữ ký số, online security.

Giải thuật nâng cao-Một số giải thuật trên số

Phép chia • Cho a, b là số nguyên, 𝑎 ≠ 0. Nói a chia hết b nếu

tồn tại số nguyên c sao cho: 𝑏 = 𝑎𝑐.

• • Ký hiệu chia hết: 𝒂 | 𝒃. Ví dụ : 3 | 12 • Ký hiệu không chia hết: 𝒂 ∤ 𝒃 (ví dụ: 5 ∤ 12) • Định lý: a,b,c  Z:

1. 𝒂|𝟎 2. (𝒂|𝒃  𝒂|𝒄)  𝒂 | (𝒃 + 𝒄) 3. 𝒂|𝒃  𝒂|𝒃𝒄 4. (𝒂|𝒃  𝒃|𝒄)  𝒂|𝒄

• Bổ đề: nếu 𝑎|𝑏, 𝑎|𝑐 thì 𝑎|𝑚𝑏 + 𝑛𝑐, 𝑎, 𝑏, 𝑐, 𝑚, 𝑛 ∈ 𝑍.

Giải thuật nâng cao-Một số giải thuật trên số

Giải thuật “Chia”

• Định lý: cho a, d là số nguyên dương, thì tồn tại duy

nhất q và r, 0 ≤ 𝑟 < 𝑑, sao cho 𝑎 = 𝑑𝑞 + 𝑟. • q: thương số; a: số bị chia; d: số chia; r: số dư • Cho số dương a và d dương, để xác định r, lặp lại trừ

d với a, cho tới khi còn lại r mà nhỏ hơn d

• Cho a âm và d dương, để xác định r, lặp lại cộng d với a, cho tới khi còn lại r, là dương (hoặc zero) nhỏ hơn d

Giải thuật nâng cao-Một số giải thuật trên số

Biểu diễn số nguyên • Cho 𝑏 > 1 nguyên dương. Có thể biểu diễn số nguyên

dương n duy nhất theo dạng

𝑛 = 𝑎𝑘𝑏𝑘 + 𝑎𝑘−1𝑏𝑘−1 + ⋯ + 𝑎1𝑏 + 𝑎0, 𝑘 ∈ 𝑁, 𝑎0, … , 𝑎𝑘 < 𝑏, 𝑎𝑘 ≠ 0

Ví dụ:

𝒃 = 𝟏𝟎 859 = 8. 102 + 5101 + 9 𝒃 = 𝟐 (10110)2 = 124 + 122 + 121 = (22)10 𝒃 = 𝟏𝟔 (3𝐴0𝐹)16 = 3163 + 10162 + 15160 = (14863)10

Giải thuật nâng cao-Một số giải thuật trên số

Số học modular • Cho a là số nguyên, m số nguyên dương. Ký hiệu 𝑎 𝑚𝑜𝑑 𝑚 biểu diễn phần dư khi a được chia cho m.

9 𝑚𝑜𝑑 4 = 1 −13 𝑚𝑜𝑑 4 = 3

• Ví dụ: • Cho a, b là số nguyên, m số nguyên dương. Khi đó “a đồng dư b modulo m” nếu: 𝒎 | 𝒂 − 𝒃. Ký hiệu: 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚).

• Ký hiệu: 𝑎 ≢ 𝑏 (𝑚𝑜𝑑 𝑚), a không đồng dư b mod m.

• Chú ý: số dư luôn dương.

Giải thuật nâng cao-Một số giải thuật trên số

Số học modular • Định lý: Cho a, b là số nguyên, m số nguyên dương. Thì 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) nếu và chỉ nếu 𝑎 𝑚𝑜𝑑 𝑚 = 𝑏 𝑚𝑜𝑑 𝑚. • Định lý: Cho m là số nguyên dương. Hai số nguyên a, b là đồng dư modulo m nếu và chỉ nếu tồn tại số k sao cho: 𝑎 = 𝑏 + 𝑘𝑚. • Ví dụ: 𝟏𝟕 = 𝟓 + 𝟐 ∗ 6 hoặc 𝟓 = 𝟏𝟕 − 𝟐 ∗ 6. (17 ≡ 5 (𝑚𝑜𝑑 2)) • Định lý: Cho m là số nguyên dương. Nếu 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) và 𝑐 ≡ 𝑑 (𝑚𝑜𝑑 𝑚) thì: (𝑎 + 𝑐) ≡ (𝑏 + 𝑑) (𝑚𝑜𝑑 𝑚) và 𝑎𝑏 ≡ 𝑐𝑑 (𝑚𝑜𝑑 𝑚).

• Bổ đề: Cho a, b là số nguyên, m số nguyên dương thì và

𝑎 + 𝑏 𝑚𝑜𝑑 𝑚 = 𝑎 𝑚𝑜𝑑 𝑚 + 𝑏 𝑚𝑜𝑑 𝑚 𝑚𝑜𝑑 𝑚 𝑎𝑏 𝑚𝑜𝑑 𝑚 = 𝑎 𝑚𝑜𝑑 𝑚 . (𝑏 𝑚𝑜𝑑 𝑚) 𝑚𝑜𝑑 𝑚

Giải thuật nâng cao-Một số giải thuật trên số

Số học modular

• Ví dụ: Các lớp đồng dư modulo 5.

≡ 0 (mod 5)

-1

15 10

≡ 1 (mod 5) 21

≡ 4 (mod 5)

22 ≡ 2 (mod 5)

≡ 3 (mod 5)

-7

• Hỏi: xác định vị trí của -1 và -7?

Giải thuật nâng cao-Một số giải thuật trên số

Số học modular • Đặt: 𝑍𝑚 = 𝑖 ∈ 𝑁 | 𝑖 < 𝑚 = 0, 1, … , 𝑚 − 1 . • Ký hiệu +𝑚: cộng các số trong Zm.

𝑎 +𝑚 𝑏 = 𝑎 + 𝑏 𝑚𝑜𝑑 𝑚

• Ký hiệu .𝑚: nhân các số trong Zm

𝑎.𝑚 𝑏 = 𝑎. 𝑏 𝑚𝑜𝑑 𝑚 • Các phép toán +𝑚 và .𝑚 được gọi là cộng và nhân modulo. 7 +11 9 = 7 + 9 𝑚𝑜𝑑 11 = 5 7.11 9 = 7.9 𝑚𝑜𝑑 11 = 8 • Các phép +𝑚 và .𝑚 thỏa mãn các tính chất: đóng, kết hợp,

giao hoán, phân bố, phần tử đơn vị.

• 𝑍𝑚 là nhóm giao hoán, và 𝑍𝑚 cùng với hai phép +𝑚, .𝑚 là

vành giao hoán

Giải thuật nâng cao-Một số giải thuật trên số

Ứng dụng của đồng dư modulo

• Hàm băm (xem lại bảng băm – cấu trúc dữ liệu)

• Số giả ngẫu nhiên

• Kiểm tra chữ số (digit checks)

• Mã hóa

Giải thuật nâng cao-Một số giải thuật trên số

Số giả ngẫu nhiên

• Cần mô phỏng trên máy tính để tạo ra số ngẫu

nhiên  số giả ngẫu nhiên (P.288-Rosen’s book)

• Phương pháp đồng dư tuyến tính: giải thuật phổ

biến để sinh số ngẫu nhiên

• Chọn 4 số nguyên

• Tâm (seed) x0: giá trị khởi đầu 0 ≤ 𝑥0 < 𝑚 • Modulus m • Bội số a: 2 ≤ 𝑎 < 𝑚 • Gia số c: 0 ≤ 𝑐 < 𝑚 • Sinh dãy số ngẫu nhiên, *𝑥𝑛 | 0 ≤ 𝑥𝑛 < 𝑚+, theo biểu thức:

𝑥𝑛+1 = (𝑎𝑥𝑛 + 𝑐) 𝑚𝑜𝑑 𝑚

Giải thuật nâng cao-Một số giải thuật trên số

Số giả ngẫu nhiên • Công thức: xn+1 = (axn + c) mod m • Ví dụ: Cho x0 = 3, m = 9, a = 7, and c = 4 x1 = 7x0+4 = 73+4 = 25 mod 9 = 7 x2 = 7x1+4 = 77+4 = 53 mod 9 = 8 x3 = 7x2+4 = 78+4 = 60 mod 9 = 6 x4 = 7x3+4 = 76+4 = 46 mod 9 = 1 x5 = 7x4+4 = 71+4 = 11 mod 9 = 2 x6 = 7x5+4 = 72+4 = 18 mod 9 = 0 x7 = 7x6+4 = 70+4 = 4 mod 9 = 4 x8 = 7x7+4 = 74+4 = 32 mod 9 = 5

• Các giá trị 𝑚 = 232 − 1, 𝑎 = 75 = 16,807, 𝑐 = 0 thường được dùng để sinh số ngẫu nhiên

• Yêu cầu: anh/chị hãy viết hàm sinh ra số ngẫu nhiên

Giải thuật nâng cao-Một số giải thuật trên số

The Caesar cipher

• Julius Caesar sử dụng thủ tục sau để mã hóa

messages

• Hàm f để mã hóa chữ được định nghĩa như sau:

f(p) = (p+3) mod 26 • Với p là a letter (0 là A, 1 là B, 25 là Z, etc.)

• Giải mã: f-1(p) = (p-3) mod 26

• Thủ tục này được gọi là substitution cipher

Giải thuật nâng cao-Một số giải thuật trên số

Mã hóa Caesar • Mã hóa “go cavaliers”

• Chuyển thành số: g = 6, o = 14, etc.

• Chuỗi số: 6, 14, 2, 0, 21, 0, 11, 8, 4, 17, 18

• Áp dụng cipher cho từng số: f(6) = 9, f(14) = 17, etc.

• Chuỗi đã mã: 9, 17, 5, 3, 24, 3, 14, 11, 7, 20, 21 • Chuyển số thành chuỗi: 9 = j, 17 = r, etc.

• Chuỗi chữ: jr wfdydolhuv

• Giải mã “jr wfdydolhuv”

• Chuyển thành số: j = 9, r = 17, etc.

• Chuỗi số: 9, 17, 5, 3, 24, 3, 14, 11, 7, 20, 21

• Áp dụng cipher cho từng số : f-1(9) = 6, f-1(17) = 14, etc.

• Chuỗi số đã giải mã: 6, 14, 2, 0, 21, 0, 11, 8, 4, 17, 18

• Chuyển số thành chuỗi: 6 = g, 14 = 0, etc.

• Chuỗi gốc: “go cavaliers”

Giải thuật nâng cao-Một số giải thuật trên số

Số nguyên tố và ước chung lớn nhất

• Số nguyên dương p được gọi là số nguyên tố nếu chỉ chia hết cho chính nó và 1. Ngược lại gọi là số hợp nguyên (composite integer).

• Chú ý: 1 không phải là số nguyên tố

Giải thuật nâng cao-Một số giải thuật trên số

Số nguyên tố và ước chung lớn nhất

• Định lý số học cơ bản: mọi số nguyên đều có thể biểu

diễn duy nhất bởi tích của các số nguyên tố.

• Định lý: số hợp nguyên n có số chia nguyên tố nhỏ

hơn hoặc bằng 𝒏.

• Suy ra: n là số nguyên tố nếu không chia hết cho bất

kỳ số nguyên tố nào nhỏ hơn hay bằng 𝑛.

• Định nghĩa: hai số nguyên a, b là nguyên tố cùng nhau nếu ước chung lớn nhất (GCD) của chúng là 1.

• Định nghĩa: Các số 𝑎1, 𝑎2, … , 𝑎𝑛 là đôi một nguyên tố cùng nhau nếu: 𝑔𝑐 𝑑 𝑎𝑖, 𝑎𝑗 = 1, 1 ≤ 𝑖 < 𝑗 ≤ 𝑛

Giải thuật nâng cao-Một số giải thuật trên số

Một số định lý

• Định lý Bézout :

• ∀𝑎, 𝑏 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠, 𝑎, 𝑏 > 0: ∃𝑠, 𝑡: gcd 𝑎, 𝑏 = 𝑠𝑎 + 𝑡𝑏

• Bổ đề 1:

• ∀𝑎, 𝑏, 𝑐 > 0: gcd 𝑎, 𝑏 = 1 𝑎𝑛𝑑 𝑎 | 𝑏𝑐 thì 𝑎 | 𝑐.

• Bổ đề 2:

• Nếu p là số nguyên tố và 𝑝 | 𝑎1𝑎2 … 𝑎𝑛 thì ∃𝑖: 𝑝 | 𝑎𝑖

• Định lý 2:

• Nếu 𝑎𝑐 ≡ 𝑏𝑐 (𝑚𝑜𝑑 𝑚) và gcd 𝑐, 𝑚 = 1

thì

𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚)

Giải thuật nâng cao-Một số giải thuật trên số

Chứng minh định lý Bézout

lý Bézout: 𝑎 ≥ 𝑏 ≥ 0 𝑠, 𝑡: gcd (𝑎, 𝑏) =

Định 𝑠𝑎 + 𝑡𝑏

Chứng minh Bổ đề Bézout là hệ quả của Euclidean division. 𝑎 = 𝑏𝑥1 + 𝑟1, 0 < 𝑟1 < 𝑏 , gcd 𝑎, 𝑏 = gcd (𝑏, 𝑟1)

1. Start with (a,b) such that a >= b 2. Take reminder r of a/b 3. Set a := b, b := r so that a >= b 4. Repeat until b = 0

Giải thuật nâng cao-Một số giải thuật trên số

Chứng minh định lý Bézout

gcd 𝑎, 𝑏 = gcd (𝑏, 𝑐)

𝑎 = 𝑏𝑥1 + 𝑟1, 0 < 𝑟1 < 𝑏 ,

𝑏 = 𝑟1𝑥2 + 𝑟2, 0 < 𝑟2 < 𝑟1 ⋮ 𝑟𝑛−1 = 𝑟𝑛𝑥𝑛+1 + 𝑟𝑛+1, 0 < 𝑟𝑛+1 < 𝑟𝑛, 𝑟𝑛 = 𝑟𝑛+1𝑟𝑛+2 • 𝑟𝑛+1 là phần dư khác zero cuối cùng trong tiến trình trên. 𝑟𝑛+1 là linear combination của 𝑟𝑛 và 𝑟𝑛−1, 𝑟𝑛 là linear combination của 𝑟𝑛−1 và 𝑟𝑛−2, • ⋯ • 𝑟𝑛+1 là linear combination của a và b và là gcd của chúng.

Giải thuật nâng cao-Một số giải thuật trên số

gcd(252,198) = gcd(198,54) = gcd(54,36) = gcd(36,18) = gcd(18,0) = 18

Ví dụ về định lý Bézout gcd(252,198) = 18. Biểu diễn 18 là kết hợp tuyến tính của 252 và 198. Sử dụng divisions theo Euclid Algorithm: 252 = 1 198 + 54 (252 mod 198 = 54) 198 = 3  54 + 36 (198 mod 54 = 36) 54 = 1  36 +18 etc. 36 = 2  18 Vì, 18 = 54 - 1  36 (3rd equation) 36 = 198 – 3  54 (2th equation) Do đó 18 = 54 - 1  (198 – 3  54) = 4  54 – 1  198 Nhưng 54 = 252 - 1 198; thay thế 54 trong biểu thức này : 18 = 4 (252 - 1 198) - 1  198 = 4  252 – 5  198

Giải thuật nâng cao-Một số giải thuật trên số

Chứng minh Bổ đề 1

Giải thuật nâng cao-Một số giải thuật trên số

Chứng minh bổ đề 2 Bổ đề 2: Nếu p là số nguyên tố và 𝑝 | 𝑎1𝑎2 … 𝑎𝑛 thì ∃𝑖: 𝑝 | 𝑎𝑖 Chứng minh quy nạp: n = 1, hiển nhiên Giả sử đúng với 𝑛 < 𝑘 . Giả sử 𝑝 | 𝑎1𝑎2 … 𝑎𝑘 . Đặt 𝑚 = 𝑎1𝑎2 … 𝑎𝑘−1 Trường hợp 1: nếu 𝑝 | 𝑚, ∃𝑖: 𝑝 | 𝑎𝑖 Trường hợp 2: nếu ≦𝑝 | 𝑚 ⇒ gcd 𝑝, 𝑚 = 1. Ngoài ra 𝑝 | 𝑚𝑎𝑘 (giả thiết). Theo bổ đề 1 thì: 𝑝 | 𝑎𝑘 

Giải thuật nâng cao-Một số giải thuật trên số

Chứng minh định lý 2 Định lý 2: Nếu 𝑎𝑐 ≡ 𝑏𝑐 (𝑚𝑜𝑑 𝑚) và gcd 𝑐, 𝑚 = 1 thì 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) Do: 𝑎𝑐 ≡ 𝑏𝑐 (𝑚𝑜𝑑 𝑚) nên: 𝑚 𝑎𝑐 − 𝑏𝑐 ⟹ 𝑚 𝑐 (𝑎 − 𝑏) Theo bổ đề 1 với: gcd 𝑐, 𝑚 = 1 và 𝑚| 𝑐 (𝑎 − 𝑏) nên 𝑚 | (𝑎 − 𝑏) Vì vậy: 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) 

Giải thuật nâng cao-Một số giải thuật trên số

Ứng dụng của định lý 2

𝑛𝑚𝑜𝑑 𝑚, (giả sử gia số

𝑛(𝑚𝑜𝑑 𝑚)

• Trong phát sinh số giả ngẫu nhiên: chọn bội số a là nguyên tố cùng nhau với m. Nghĩa là: gcd (𝑚, 𝑎) = 1. Thì: • Hàm chuyển từ xn thành xn+1 là đơn ánh • Vì nếu: 𝑥𝑛+1 ≡ 𝑎𝑥𝑛 𝑚𝑜𝑑 𝑚 = 𝑎𝑥′ 𝑐 = 0), thì: 𝑥𝑛 ≡ 𝑥′

• Nghĩa là: dãy số giả ngẫu nhiên không lặp lại cho đến khi gặp lại số x0 ban đầu

Giải thuật nâng cao-Một số giải thuật trên số

Lũy thừa modulo • Cho m nguyên dương, giá trị của 𝑏𝑛 𝑚𝑜𝑑 𝑚 được gọi là lũy thừa modulo. • Không thực tế nếu tính 𝑎 = 𝑏𝑛, sau đó tính 𝑎 𝑚𝑜𝑑 𝑚 • Dựa trên khai triển nhị phân của số nguyên để tính 𝑏𝑛

𝒃𝒏 = 𝒃𝒂𝒌−𝟏𝟐𝒌−𝟏+𝒂𝒌−𝟐𝟐𝒌−𝟐+⋯+𝒂𝟏𝟐+𝒂𝟎 = 𝒃𝒂𝒌−𝟏𝟐𝒌−𝟏

… 𝒃𝒂𝟏𝟐𝒃𝒂𝟎

tính

thì

𝑏𝑛 𝑚𝑜𝑑 𝑚 𝑚𝑜𝑑 𝑚, 𝑏23

𝑚𝑜𝑑 𝑚, … , 𝑏2𝑘−1

cần 𝑚𝑜𝑑 𝑚

tính: (bổ

• Để 𝑏2 𝑚𝑜𝑑 𝑚, 𝑏22 đề: 𝑎𝑏 𝑚𝑜𝑑 𝑚 = 𝑎 𝑚𝑜𝑑 𝑚 . (𝑏 𝑚𝑜𝑑 𝑚) 𝑚𝑜𝑑 𝑚 )

Giải thuật nâng cao-Một số giải thuật trên số

Giải thuật tính lũy thừa modulo

• Bổđề:

𝑎𝑏 𝑚𝑜𝑑 𝑚 = 𝑎 𝑚𝑜𝑑 𝑚 . (𝑏 𝑚𝑜𝑑 𝑚) 𝑚𝑜𝑑 𝑚

Giải thuật nâng cao-Một số giải thuật trên số

Giải thuật tính lũy thừa modulo: ví dụ • Tính 3644 𝑚𝑜𝑑 645

Giải thuật nâng cao-Một số giải thuật trên số

Số Mersenne • Số có dạng: 2𝑛 − 1 • Số nguyên tố Mersenne: là số nguyên tố có dạng 2𝑝 − 1, với p nguyên tố. • Ví dụ: 25-1 = 31 là nguyên tố Mersenne, nhưng 211-1 = 2047

không phải là nguyên tố Mersenne

• Nếu M là nguyên tố Mersenne thì M(M+1)/2 là số hoàn hảo (số bằng với tổng các thương của nó – ví dụ: 28 = 1 + 2 + 4 + 7 + 14 ) • Ví dụ: 25-1 = 31 là nguyên tố Mersenne, thì 31*32/2=496 là số

hoàn hảo

• 496 = 2*2*2*2*31  1+2+4+8+16+31+62+124+248 = 496 • Số nguyên tố lớn nhất xác định được là số

Mersenne.

Giải thuật nâng cao-Một số giải thuật trên số

Số nguyên tố Mersenne • Định lý: có vô hạn số nguyên tố • Kiểm tra Lucas-Lehmer: xác định số nguyên tố

Mersenne

• Số nguyên tố lớn nhất được tìm thấy: 12 triệu chữ số

(tháng 10/2014)

Giải thuật nâng cao-Một số giải thuật trên số

Định lý số nguyên tố • Tỉ lệ của số lượng các số nguyên tố không lớn

hơn x và x/ln(x) tiến tới 1 khi x tăng vô hạn • Số lượng các số nguyên tố nhỏ hơn x xấp xỉ bằng

x/ln(x) (in 1792 by Gauss at 15...)

• Cơ hội để số x là số nguyên tố xấp xỉ bằng: 1/ln(x).

• Ví dụ: xét số nguyên tố có 200 chữ số

• 𝑙𝑛 10200 ≈ 460 • Trong 460 số nguyên có 200 chữ số thì có có thể có 1 số

nguyên tố.

• Manindra Agrawal et al (2002) giới thiệu giải thuật 𝑂 𝑙𝑜𝑔𝑛 6 để xác định số n có phải là số nguyên tố

Giải thuật nâng cao-Một số giải thuật trên số

Ước chung lớn nhất

• Cho hai số nguyên a, b: có thể sử dụng biểu diễn

dạng tích của các nguyên tố để xác định GCD.

𝑏𝑛 . Các số mũ là

𝑎2 … 𝑝𝑛

𝑏2 … 𝑝𝑛

𝑎𝑛, 𝑏 = 𝑝1

𝑏1𝑝2

𝑎1𝑝2 • 𝑎 = 𝑝1 nguyên không âm

min (𝑎𝑛,𝑏𝑛)

min (𝑎2,𝑏2) … 𝑝𝑛

min (𝑎1,𝑏1)𝑝2

• Thì 𝑔𝑐𝑑 𝑎, 𝑏 = 𝑝1 • Ví dụ: 120 = 23. 3.5, 500 = 22. 53 . Khi đó: 𝑔𝑐𝑑 120,500 = 2min (3,2)3min (1,0)5min (1,3) = 20

• Nhận xét: biểu diễn dạng thừa số nguyên tố có thể

xác định được bội chung nhỏ nhất

Giải thuật nâng cao-Một số giải thuật trên số

𝑏𝑛. Các số mũ

𝑏2 … 𝑝𝑛

𝑎2 … 𝑝𝑛

𝑎𝑛, 𝑏 = 𝑝1

𝑏1𝑝2

max (𝑎𝑛,𝑏𝑛)

max (𝑎2,𝑏2) … 𝑝𝑛

Bội chung nhỏ nhất 𝑎1𝑝2 • Cho 𝑎 = 𝑝1 là nguyên không âm, thì: max (𝑎1,𝑏1)𝑝2

• 𝑙𝑐𝑚 𝑎, 𝑏 = 𝑝1 • Ví dụ: 95256 = 23. 35. 72; 432 = 24. 33. Khi đó:

𝑙𝑐𝑚 95256,432 = 2max (3,4)3max (5,3)7max (2,0)

= 190512

Giải thuật nâng cao-Một số giải thuật trên số

Định lý LCM & GCD

• Định lý: cho a, b là hai số nguyên dương, thì

𝑎 × 𝑏 = 𝑔𝑐𝑑 (𝑎, 𝑏) × 𝑙𝑐𝑚 𝑎, 𝑏

• Ví dụ: : 𝑔𝑐𝑑 (10,25) = 5, 𝑙𝑐𝑚 (10,25) = 50, vì vậy

10 × 25 = 5 × 50

• Định lý: cho 𝑎 = 𝑏𝑞 + 𝑟, với a, b, q, r là số nguyên.

Thì 𝑔𝑐𝑑 (𝑎, 𝑏) = 𝑔𝑐𝑑 (𝑏, 𝑟).

Giải thuật nâng cao-Một số giải thuật trên số

Giải thuật Euclid xác định GCD

• Tính GCD dựa trên phân tích thừa số nguyên tố: hạn

chế vì cần xác định các thừa số nguyên tố • Nhận xét: Với mọi cặp số nguyên a, b thì: 𝑔𝑐𝑑 (𝑎, 𝑏) = 𝑔𝑐𝑑 𝑎 𝑚𝑜𝑑 𝑏, 𝑏 procedure procedure (a,b:positive integers) x := a y := b while y  0 begin r := x mod y x := y y := r end { gcd(a, b) is x }

Giải thuật nâng cao-Một số giải thuật trên số

Giải thuật Euclid-Ví dụ gcd(372,164) = gcd(164, 372 mod 164).

372 mod 164 = 372164 372/164 = 372164·2 = 372328 = 44.

gcd(164,44) = gcd(44, 164 mod 44).

164 mod 44 = 16444 164/44 = 16444·3 = 164132 = 32.

gcd(44,32) = gcd(32, 44 mod 32) = gcd(32,12) = gcd(12, 32 mod 12) = gcd(12,8) = gcd(8, 12 mod 8) = gcd(8,4) = gcd(4, 8 mod 4) = gcd(4,0) = 4.

Giải thuật nâng cao-Một số giải thuật trên số

Đồng dư tuyến tính-nghịch đảo

• Đồng dư tuyến tính có dạng: 𝑎𝑥 ≡ 𝑏 (𝑚𝑜𝑑 𝑚). Mục

tiêu là tìm x thỏa biểu thức trên

• Gọi a’ là nghịch đảo (modulo m)của a, nếu:

𝑎′𝑎 ≡ 1 (𝑚𝑜𝑑 𝑚)

• Nếu tồn tại a’, biểu thức trên:

𝑎′𝑎𝑥 ≡ 𝑎′𝑏 (𝑚𝑜𝑑 𝑚) 1. 𝑥 ≡ 𝑎′𝑏 (𝑚𝑜𝑑 𝑚)

Định lý: nếu gcd (𝑎, 𝑚) = 1 và 𝑚 > 1 thì tồn tại duy nhất a’ là nghịch đảo (modulo m) của a.

Giải thuật nâng cao-Một số giải thuật trên số

Ví dụ: đồng dư tuyến tính-nghịch đảo

• Tìm nghịch đảo của 4 (modulo 9)

𝑔𝑐𝑑 4,9 = 1

9 = 2  4 + 1 1 = −2  4 + 19 −𝟐  4 ≡ 1 (𝑚𝑜𝑑 9) Các số đồng dư tuyến tính với -2 (mod 9) đều là nghịch đảo của 4 (modulo 9)

Giải thuật nâng cao-Một số giải thuật trên số

Định lý phần dư Trung hoa • Định lý: cho 𝑚1, … , 𝑚𝑛 > 1 là nguyên tố cùng nhau, và 𝑎1, … , 𝑎𝑛 là các số nguyên bất kỳ . Thì hệ phương trình 𝑚𝑜𝑑 𝑚𝑖 , 𝑖 = 1 → 𝑛 có lời giải duy nhất modulo 𝑥 ≡ 𝑎𝑖 𝑚 = 𝑚1 · ⋯ · 𝑚𝑛. Nghĩa là 0 ≤ 𝑥 < 𝑚, và nếu có y thỏa hệ phương trình trên thì 𝑥 ≡ 𝑦 (𝑚𝑜𝑑 𝑚).

𝑚𝑜𝑑 𝑚𝑖 = 𝑎𝑖𝑦𝑖𝑀𝑖 𝑚𝑜𝑑 𝑚𝑖 =

𝑙

Đặt: 𝑀𝑖 = 𝑚/𝑚𝑖 thì gcd 𝑀𝑖, 𝑚𝑖 = 1 ⇒ ∃! 𝑦𝑖: 𝑦𝑖𝑀𝑖 ≡ 1 (𝑚𝑜𝑑 𝑚𝑖) (định lý về đồng dư nghịch đảo) Đặt 𝒙 = 𝒂𝒊𝒚𝒊𝑴𝒊 𝒊 Vì: 𝑚𝑖|𝑀𝑘, 𝑘 ≠ 𝑖, nên 𝑀𝑘 ≡ 0 (𝑚𝑜𝑑 𝑚𝑖) 𝑥 𝑚𝑜𝑑 𝑚𝑖 = 𝑎𝑙𝑦𝑙𝑀𝑙 Nên: 𝑎𝑖 𝑚𝑜𝑑 𝑚𝑖 Vậy: 𝑥 ≡ 𝑎𝑖 𝑚𝑜𝑑 𝑚𝑖, ∀𝑖 = 1 → 𝑛. Và x là lời giải cần tìm.

Giải thuật nâng cao-Một số giải thuật trên số

Định lý phần dư Trung hoa-ví dụ

m = m1·…·mn.

Dựa trên định lý phần dư Trung hoa

Mi = m/mi yi Mi ≡ 1 (mod mi).

a1 = 2, a2 = 3, a3 = 2 m1 = 3, m2 = 5, m3 = 7

x = ∑i ai yi Mi

Tìm x sao cho: 𝑥 ≡ 2 (𝑚𝑜𝑑 3), 𝑥 ≡ 3 (𝑚𝑜𝑑 7), 𝑥 ≡ 2 (𝑚𝑜𝑑 7) m = 357 = 105 M1 = m/3 = 105/3 = 35 2 là nghịch đảo của M1 = 35 (mod 3) (vì 35x2 ≡ 1 (mod 3)) M2 = m/5 = 105/5 = 21 1 là nghịch đảo của M2 = 21 (mod 5) (vì 21x1 ≡ 1 (mod 5)) M3 = m/7 = 15 1 là nghịch đảo của M3 = 15 (mod 7) (vì 15x1 ≡ 1 (mod 7)) Vậy , x ≡ 2  2  35 + 3  1  21 + 2  1  15 = 233 ≡ 23 (mod 105) Lời giải: x ≡ 23 (mod 105)

Giải thuật nâng cao-Một số giải thuật trên số

Định lý phần dư Trung hoa-MATLAB

CM=CM*p(i);

M(i)=CM/p(i);

IM(i)=invmodan(M(i),p(i)); x=x+r(i)*M(i)*IM(i);

function x=CRT(r,p) if (length(r)==length(p)) l=length(r); CM=1; for i=1:l end M=zeros(1,l); for i=1:l end IM=zeros(1,l); x=0; for i=1:l end display('Value of x: '); x=mod(x,CM); else display('Length of r and p matrices must be same'); end

Giải thuật nâng cao-Một số giải thuật trên số

a(i+1)=rem((a(i))^2,p);

if b(i)=='0' a(i)=1; end mul=mul*a(i); mul=rem(mul,p);

Định lý phần dư Trung hoa-MATLAB function y=invmodn(x,p) n=eulerphi(p); % Compute Euler's totient function of p b=dec2bin(n-1); len=length(b); a=ones(1,len); a(1)=rem(x,p); for i=1:(len-1) end b=fliplr(b); mul=1; for i=1:len end y=rem(mul,p);

Giải thuật nâng cao-Một số giải thuật trên số

phi=phi*(f(i)-1);

f=factor(n); l=length(f); phi=1; for i=1:l end

Định lý phần dư Trung hoa-MATLAB function phi=eulerphi(n) if (n>1 && mod(n,1)==0) elseif (n==1) phi=1; else display('Invalid number entered'); end

Giải thuật nâng cao-Một số giải thuật trên số

Tính toán số nguyên lớn • Cho số nguyên a bất kỳ, 0 ≤ 𝑎 < 𝑚 , với 𝑚 = 𝑚𝑖 , gcd 𝑚𝑖, 𝑚𝑗≠𝑖 = 1 thì a có thể được biểu diễn bởi các phần dư của a với mi. Nghĩa là bộ n 𝑎 𝑚𝑜𝑑 𝑚1, 𝑎 𝑚𝑜𝑑 𝑚2, … , 𝑎 𝑚𝑜𝑑 𝑚𝑛 .

𝑚𝑜𝑑 𝑚𝑖 , với 𝑎𝑖 = 𝑎 𝑚𝑜𝑑 𝑚𝑖. Thì tồn

• Xét hệ phương trình: 𝑥 ≡ 𝑎𝑖 tại duy nhất nghiệm x.

• Xét: 𝑥 = 𝑎 𝑚𝑜𝑑 𝑚, thì x là nghiệm của hệ phương

trình trên.

Giải thuật nâng cao-Một số giải thuật trên số

Tính toán số nguyên lớn Hãy biểu diễn số nguyên x nhỏ hơn 12 bởi một cặp. Chọn cặp là hai số nguyên tố cùng nhau. Ví dụ 3 và 4. Biểu diễn x theo các bộ (𝑥 𝑚𝑜𝑑 3, 𝑥 𝑚𝑜𝑑 4). Xác định phần dư của các số chia cho 3 và 4. 0=(0,0); 1=(1,1); 2=(2,2); 3=(0,3); 4=(1,0); 5=(2,1); 6=(0,2); 7=(1,3); 8=(2,0); 9= (0,1); 10 = (1,2); 11= (2,3) • Ví dụ: 11 = (11 mod 3, 11 mod 4) = (2, 3) Vậy: có thể sử dụng hai số nguyên nhỏ để biểu diễn số nguyên nhỏ hơn 12.

Giải thuật nâng cao-Một số giải thuật trên số

Tính toán số nguyên lớn

• Để thực hiện tính toán trên số nguyên lớn, thực hiện theo các bước sau • Thực hiện trên các phép toán trên các phần

dư! • Có thể thực hiện song song. • Hay thực hiện tuần tự trên máy đơn.

• Tiếp tục đến khi desired result < m.

Giải thuật nâng cao-Một số giải thuật trên số

123684 có thể biểu diễn bởi

413456 có thể biểu diễn bởi

Tính toán số nguyên lớn Ví dụ: giả sử có thể tính toán dễ với các số nhỏ hơn 100; Khi đó có thể giới hạn tính toán các số nguyên thành tính các số nhỏ hơn 100, nếu có thể biểu diễn ở dạng phần dư đôi một nguyên tố cùng nhau, ví dụ: 99, 98, 97, 95. Theo định lý phần dư Trung Hoa, mọi số nhỏ hơn 9998 9795 = 89.403.930 có thể biểu diễn duy nhất theo các phần dư của chúng với các số 99, 98 , 97 , 95. Ví dụ, số (123684 mod 99; 123684 mod 98; 123684 mod 97; 123684 mod 95) = (33,8,9,89) (413456 mod 99; 413456 mod 98; 413456 mod 97; 413456 mod 95)= (32,92,42,16)

Giải thuật nâng cao-Một số giải thuật trên số

x ≡ 65 (mod 99) x ≡ 2 (mod 98) x ≡ 51 (mod 97) x ≡ 10 (mod 95)

Tính toán số nguyên lớn Để cộng hai số 123.684, và 413456. (33, 8, 9, 89)+(32, 92 , 42, 16) = (65 mod 99, 100 mod 98, 51 mod 97, 105 mod 95) = (65, 2, 51, 10) Để tìm tổng: giải hệ phương trình đồng dư tuyến tính sau Lời giải: x= 537,140

Giải thuật nâng cao-Một số giải thuật trên số

Tính toán số nguyên lớn

• Vd:. 1030 = (r1 = 20900945;

r2 = 18304,504;

r3 = 65829085;

• Ví dụ, các số sau là nguyên tố cùng nhau: m1 = 225−1 = 33,554,431 = 31 · 601 · 1,801 m2 = 227−1 = 134,217,727 = 7 · 73 · 262,657 m3 = 228−1 = 268,435,455 = 3 · 5 · 29 · 43 · 113 · 127 m4 = 229−1 = 536,870,911 = 233 · 1,103 · 2,089 m5 = 231−1 = 2,147,483,647 (prime) • Vậy, có thể biểu diễn số nguyên lớn • m = ∏mi ≈ 1.4×1042 ≈ 2139.5 theo các phần dư ri modulo với các mi trên. r4 = 516865185; r5 = 1234980730)

• Để cộng hai số theo biểu diễn đồng dư

• Cộng các phần dư tương ứng. • Lấy kết quả mod 2k−1:

• Nếu ≥ giá trị 2k−1, trừ nó với 2k−1

• Chú ý: No carries are needed between the different pieces!

Giải thuật nâng cao-Một số giải thuật trên số

Pseudoprimes • Nếu n nguyên tố thì 2𝑛−1 ≡ 1 (𝑚𝑜𝑑 𝑛), tuy nhiên điều ngược lại không đúng [nghĩa là nếu 2𝑛−1 ≡ 1 (𝑚𝑜𝑑 𝑛) thì n có thể không nguyên tố]. • Ví dụ: 2𝟑𝟒𝟏−1 ≡ 1 (𝑚𝑜𝑑 341) , nhưng 341 = 11 × 31

không phải là số nguyên tố.

• Số n với tính chất này được gọi là pseudoprime.

• Tổng quát, nếu 𝒃𝒏−𝟏 ≡ 𝟏 (𝒎𝒐𝒅 𝒏) và n là số hợp nguyên, thì n được gọi là pseudoprime cơ số b.

Giải thuật nâng cao-Một số giải thuật trên số

Định lý nhỏ của Fermat

• Định lý: (Fermat’s Little Theorem.)

• Nếu p nguyên tố và a nguyên không chia hết p; (𝑎 ∤

𝑝), thì

𝑎𝑝−1 ≡ 1 (𝑚𝑜𝑑 𝑝) • Ngoài ra, với mọi số nguyên a thì

𝑎𝑝 ≡ 𝑎 (𝑚𝑜𝑑 𝑝)

• Nhận xét: nếu 𝑎 ∈ 𝑍𝑝 thì 𝑎𝑝−1 ≡ 1 trong Zp.

Giải thuật nâng cao-Một số giải thuật trên số

Các số Carmichael • Định nghĩa: số hợp nguyên n thỏa mãn 𝑏𝑛−1 ≡ 1 𝑚𝑜𝑑 𝑛 , ∀𝑏: gcd 𝑏, 𝑛 = 1 được gọi là số Carmichael.

• Ví dụ: 561 là số Carmichael

• 561=3.11.17 • Nếu

gcd (𝑏, 561) = 1

thì

gcd (𝑏, 3) = 1, gcd (𝑏, 11) = 1, gcd (𝑏, 17) = 1

• 𝑏2 ≡ 1 𝑚𝑜𝑑 3 ; 𝑏1 ≡ 1 𝑚𝑜𝑑 11 ; 𝑏16 ≡ 1 𝑚𝑜𝑑 17 ; • 𝑏560 = 𝑏2 280 ≡ 1 (𝑚𝑜𝑑 3) • 𝑏560 = 𝑏10 56 ≡ 1 (𝑚𝑜𝑑 11) • 𝑏560 = 𝑏16 35 ≡ 1 (𝑚𝑜𝑑 16)

• Các số: 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341

là số Carmichael

Giải thuật nâng cao-Một số giải thuật trên số

Chọn hai prime numbers p và q (ngẫu nhiên).

Mã RSA http://mathworld.wolfram.com/RSAEncryption.html Phát sinh mã 1. 2. 𝑛 = 𝑝𝑞, dùng làm modulus. 3. 𝜑(𝑛) = 𝜑(𝑝)𝜑(𝑞) = (𝑝 − 1)(𝑞 − 1) = 𝑛 − (𝑝 + 𝑞 − 1)

hàm

totient), là private key Chọn số e sao cho 1 < 𝑒 < 𝜑(𝑛), và gcd(e, φ(n)) = 1.

• e là public key exponent. • Giá trị e nhỏ không hiệu quả để bảo mật.

Tìm: d ≡ e−1 (mod φ(n)).

• d là private key exponent

• Public key: số n và e. • Private key: số d.

Giải thuật nâng cao-Một số giải thuật trên số

Mã RSA http://mathworld.wolfram.com/RSAEncryption.html Mã hóa 1. A gởi 𝑛, 𝑒 (public key - gởi đi) cho B. A giữ bí mật giá trị d. 2. B cần gởi gói tin M mã với 𝑛, 𝑒 để gởi cho A. 3. Chuyển M thành giá trị nguyên m. 4. Tính 𝑐 ≡ 𝑚𝑒 𝑚𝑜𝑑 𝑛 , là gói B gởi cho A. Giải mã • A cần phục hồi m, M khi nhận được c từ B. • 𝑚 ≡ 𝑐𝑑 𝑚𝑜𝑑 𝑛

Giải thuật nâng cao-Một số giải thuật trên số

Mã RSA-ví dụ • Cho 𝑝 = 61, 𝑞 = 5. • 𝑛 = 61 ∗ 53 = 3233 • 𝜑 3233 = 3120 • Chọn 1 < 𝑒 < 3120 nguyên tố cùng nhau với 3120.

Chọn e = 17.

• 𝑒 × 𝑑 = 1 (𝑚𝑜𝑑 3120)  d = 2753. • Public key: 𝑛 = 3233, 3 = 17 • Private key: 𝑑 = 2753.

• Cho m = 65 • Mã hóa m: 𝑐 = 6517 𝑚𝑜𝑑 3233 = 2790. • Giải mã c: 𝑚 = 27902753 𝑚𝑜𝑑 3233 = 65.

Giải thuật nâng cao-Một số giải thuật trên số

Bài tập 1. Tìm nghiệm: 2 22006

𝑚𝑜𝑑 3 = 2 2.22005 = 4 22205

2 22006

≡1 (𝑚𝑜𝑑 3)

2. Chứng minh: nếu tồn tại số đảo (multiplicative inverse hoặc reciprocal) modulo N, thì nó là duy nhất. Giả sử tồn tại hai số đảo x1, x2 khác nhau của a. 𝑥1 = 𝑥1. 1 = 𝒙𝟏. 𝒂. 𝑥2 = 1. 𝑥2 = 𝑥2 𝑚𝑜𝑑 𝑁

Giải thuật nâng cao-Một số giải thuật trên số

Bài tập

3. Xét RSA, p=7, q=11. Tìm e và d.

𝑝 − 1 ∗ 𝑞 − 1 = 60

Tìm e nguyên tố cùng nhau với 60, và có số nghịch đảo. Chọn e=11  d= 11 (mod 60). Có thể chọn các cặp (e, d) khác: (7, 43); (13, 37); (17, 53); (19, 59); (23, 47); (29, 29); (31, 31); (41, 41).

4. Cài đặt và thuyết minh RSA bằng MATLAB.

Giải thuật nâng cao-Một số giải thuật trên số