Modular Arithmetic

Greatest Common Divisor

Ước số chung lớn nhất (GCD), đôi khi được gọi là nhân tử chung cao nhất, là số lớn nhất chia hết cho hai số nguyên dương (a, b).

Với a = 12, b = 8 chúng ta có thể tính các ước số của a: {1,2,3,4,6,12} và các ước số của b: {1,2,4,8}. So sánh hai tập hợp này, chúng ta thấy rằng gcd(a,b) = 4.

Bây giờ hãy tưởng tượng chúng ta lấy a = 11, b = 17. Cả a và b đều là số nguyên tố. Vì một số nguyên tố chỉ có chính nó và 1 là ước số, gcd(a,b) = 1.

Chúng ta nói rằng với bất kỳ hai số nguyên a,b nào, nếu gcd(a,b) = 1 thì a và b là các số nguyên tố cùng nhau.

Nếu a và b là số nguyên tố, chúng cũng là số nguyên tố cùng nhau. Nếu a là số nguyên tố và b < a thì a và b là số nguyên tố cùng nhau.

Hãy suy nghĩ về trường hợp a là số nguyên tố và b > a, tại sao chúng không nhất thiết phải là số nguyên tố cùng nhau?

Có nhiều công cụ để tính GCD của hai số nguyên, nhưng đối với nhiệm vụ này, chúng tôi khuyên bạn nên tìm hiểu Thuật toán Euclid.

Extended Euclidean Algorithm

Cho a và b là các số nguyên dương.

Thuật toán Euclid mở rộng là một cách hiệu quả để tìm các số nguyên u,v sao cho

a * u + b * v = gcd(a,b)

Modular Arithmetic

Các số nguyên modulo p (p là số nguyên tố) xác định một trường, ký hiệu là Fp.

Nếu modulus không phải là số nguyên tố, tập hợp các số nguyên modulo n xác định một vành.

Một trường hữu hạn Fp là tập hợp các số nguyên {0,1,...,p-1}, và dưới cả phép cộng và phép nhân, có một phần tử nghịch đảo b cho mọi phần tử a trong tập hợp, sao cho a + b = 0 và a * b = 1.

Giả sử chúng ta chọn p = 17. Tính 3^17 mod 17. Bây giờ làm tương tự nhưng với 5^17 mod 17.

Bạn mong đợi nhận được gì cho 7^16 mod 17? Hãy thử tính toán điều đó.

Sự thật thú vị này được gọi là định lý nhỏ của Fermat. Chúng ta sẽ cần điều này (và các khái quát hóa của nó) khi xem xét mật mã RSA.

Modular Inverting

Như chúng ta đã thấy, chúng ta có thể làm việc trong một trường hữu hạn Fp, cộng và nhân các phần tử, và luôn thu được một phần tử khác của trường.

Summary

Đối với tất cả các phần tử g trong trường, tồn tại một số nguyên duy nhất d sao cho g * d ≡ 1 mod p. Đây là nghịch đảo nhân của g.

Ví dụ: 7 * 8 = 56 ≡ 1 mod 11

Phần tử nghịch đảo là gì: 3 * d ≡ 1 mod 13?

Quadratic Residues

Chúng ta đã xem xét phép nhân và phép chia trong số học modular, nhưng việc lấy căn bậc hai modulo một số nguyên có nghĩa là gì?

Để thảo luận sau đây, hãy làm việc modulo p = 29. Chúng ta có thể lấy số nguyên a = 11 và tính a^2 = 5 mod 29.

Vì a = 11, a^2 = 5, chúng ta nói căn bậc hai của 5 là 11.

Điều này có vẻ ổn, nhưng bây giờ hãy nghĩ về căn bậc hai của 18. Từ trên, chúng ta biết chúng ta cần tìm một số nguyên a sao cho a^2 = 18.

Ý tưởng đầu tiên của bạn có thể là bắt đầu với a = 1 và lặp đến a = p-1. Trong cuộc thảo luận này, p không quá lớn và chúng ta có thể nhanh chóng xem xét.

Hãy thử, hãy thử viết mã này và xem bạn tìm thấy gì. Nếu bạn viết mã đúng, bạn sẽ thấy rằng với mọi a ∈ Fp* bạn sẽ không bao giờ tìm thấy một a sao cho a^2 = 18.

Điều chúng ta đang thấy là, đối với các phần tử của F*p, không phải mọi phần tử đều có căn bậc hai. Trên thực tế, điều chúng ta thấy là đối với khoảng một nửa số phần tử của Fp*, không có căn bậc hai.

Summary

Chúng ta nói rằng một số nguyên x là một Thặng dư bậc hai (Quadratic Residue) nếu tồn tại một a sao cho a^2 = x mod p. Nếu không có giải pháp như vậy, thì số nguyên đó là một Bất thặng dư bậc hai (Quadratic Non-Residue). Nói cách khác, x là một thặng dư bậc hai khi có thể lấy căn bậc hai của x modulo một số nguyên p.

Trong danh sách dưới đây có hai bất thặng dư bậc hai và một thặng dư bậc hai.

Tìm thặng dư bậc hai và sau đó tính căn bậc hai của nó. Trong hai nghiệm có thể có, hãy gửi nghiệm nhỏ hơn làm cờ.

Summary

Nếu a^2 = x thì (-a)^2 = x. Vì vậy, nếu x là một thặng dư bậc hai trong một trường hữu hạn nào đó, thì luôn có hai giải pháp cho a.

Legendre Symbol

Trong Thặng dư bậc hai, chúng ta đã học được ý nghĩa của việc lấy căn bậc hai modulo một số nguyên. Chúng ta cũng đã thấy rằng việc lấy căn không phải lúc nào cũng có thể.

Trong trường hợp trước đó khi p = 29, ngay cả phương pháp đơn giản nhất để tính căn bậc hai cũng đủ nhanh, nhưng khi p lớn hơn, phương pháp này trở nên hoàn toàn không hợp lý.

May mắn cho chúng ta, chúng ta có một cách để kiểm tra xem một số nguyên có phải là một thặng dư bậc hai hay không với một phép tính duy nhất nhờ Legendre. Trong phần sau, chúng ta sẽ giả định rằng chúng ta đang làm việc modulo một số nguyên tố p.

Trước khi xem xét ký hiệu của Legendre, hãy đi một đoạn ngắn để xem một thuộc tính thú vị của các thặng dư (không) bậc hai.

Thặng dư bậc hai * Thặng dư bậc hai = Thặng dư bậc hai
Thặng dư bậc hai * Bất thặng dư bậc hai = Bất thặng dư bậc hai
Bất thặng dư bậc hai * Bất thặng dư bậc hai = Thặng dư bậc hai

Summary

Mẹo để nhớ điều này: Thay thế “Thặng dư bậc hai” bằng +1 và “Bất thặng dư bậc hai” bằng -1, cả ba kết quả đều giống nhau!

Vậy thủ thuật là gì? Ký hiệu Legendre cung cấp một cách hiệu quả để xác định xem một số nguyên có phải là thặng dư bậc hai modulo một số nguyên tố lẻ p hay không.

Ký hiệu của Legendre: (a / p) ≡ a(p-1)/2 mod p tuân theo:

(a / p) = 1 nếu a là một thặng dư bậc hai và a ≢ 0 mod p
(a / p) = -1 nếu a là một bất thặng dư bậc hai mod p
(a / p) = 0 nếu a ≡ 0 mod p

Điều đó có nghĩa là với bất kỳ số nguyên a nào, việc tính pow(a,(p-1)//2,p) là đủ để xác định xem a có phải là một thặng dư bậc hai hay không.

Bây giờ là cờ. Với số nguyên tố 1024 bit sau đây và 10 số nguyên, hãy tìm thặng dư bậc hai và sau đó tính căn bậc hai của nó; căn bậc hai là cờ của bạn. Trong hai nghiệm có thể có, hãy gửi nghiệm lớn hơn làm câu trả lời của bạn.

Summary

Ký hiệu của Legendre cho chúng ta biết số nguyên nào là thặng dư bậc hai, nhưng làm thế nào để chúng ta tìm căn bậc hai?! Số nguyên tố được cung cấp tuân theo p = 3 mod 4, cho phép chúng ta dễ dàng tính toán căn bậc hai. Câu trả lời có trên mạng, nhưng bạn có thể tự mình tìm ra nếu bạn suy nghĩ về định lý nhỏ của Fermat.

Modular Square Root

Trong Ký hiệu Legendre, chúng tôi đã giới thiệu một cách nhanh chóng để xác định xem một số có phải là căn bậc hai modulo một số nguyên tố hay không. Chúng ta có thể đi xa hơn: có các thuật toán để tính toán hiệu quả các căn như vậy. Tốt nhất trong thực tế được gọi là Tonelli-Shanks, có cái tên ngộ nghĩnh từ thực tế là nó được mô tả lần đầu tiên bởi một người Ý vào thế kỷ 19 và được Daniel Shanks khám phá lại một cách độc lập vào những năm 1970.

Tất cả các số nguyên tố không phải là 2 đều có dạng p ≡ 1 mod 4 hoặc p ≡ 3 mod 4, vì tất cả các số lẻ đều tuân theo các đồng dư này. Như thử thách trước đã gợi ý, trong trường hợp p ≡ 3 mod 4, một công thức thực sự đơn giản để tính căn bậc hai có thể được suy ra trực tiếp từ định lý nhỏ của Fermat. Điều đó vẫn để lại cho chúng ta trường hợp p ≡ 1 mod 4, vì vậy cần có một thuật toán tổng quát hơn.

Trong một đồng dư có dạng r^2 ≡ a mod p, Tonelli-Shanks tính r.

Summary

Tonelli-Shanks không hoạt động đối với các modulus hỗn hợp (không phải số nguyên tố). Việc tìm căn bậc hai modulo các số hỗn hợp tương đương về mặt tính toán với việc phân tích nhân tử số nguyên - nghĩa là, đó là một vấn đề khó.

Trường hợp sử dụng chính cho thuật toán này là tìm tọa độ đường cong elliptic. Hoạt động của nó hơi phức tạp nên chúng ta sẽ không thảo luận chi tiết, tuy nhiên, việc triển khai rất dễ tìm và Sage có một cái được tích hợp sẵn.