I. Phép đồng dư thức

1. Định nghĩa

Đồng dư thức là phép toán mang số dư của số này khi phân chia cho số khác, kí hiệu là %\%%. Ví dụ: 5%2=15 \% 2=15%2=1, khi đó có thể viết là 5≡15 equiv 15≡1 (mod(mod(mod 2)2)2).

Bạn đang xem: Đồng dư thức

Phép đồng dư thức có đặc điểm phân phối so với phép cộng, phép nhân với phép trừ, rõ ràng như sau:

(a+b)(a + b)(a+b) %\%% ccc =<(a= <(a=<(a %\%% c)+(bc) + (bc)+(b %\%% c)>c)>c)> %\%% ccc.- (a−b)(a - b)(a−b) %\%% ccc =<(a= <(a=<(a %\%% c)−(bc) - (bc)−(b %\%% c)>c)>c)> %\%% ccc.(a×b)(a imes b)(a×b) %\%% ccc =<(a= <(a=<(a %\%% c)×(bc) imes (bc)×(b %\%% c)>c)>c)> %\%% ccc.

Riêng đối với phép chia, chúng ta không có đặc điểm phân phối, nhưng phải thực hiện một lí thuyết là Nghịch đảo modulo.

2. Nghịch đảo modulo của một số

Như chúng ta đều biết ở chương trình Toán phổ thông, nghịch hòn đảo của một vài nguyên aaa (kí hiệu a−1a^-1a−1) là số thỏa mãn: a.a−1=1a.a^-1=1a.a−1=1.

Đối cùng với nghịch hòn đảo modulo, ta cũng đều có khái niệm tương tự, tuy thế là xét bên trên tập số dư khi phân tách cho MMM. Nghịch hòn đảo modulo MMM của một trong những aaa (cũng kí hiệu a−1a^-1a−1) là số nguyên thỏa mãn: a.a−1≡1 (moda.a^-1equiv1 (moda.a−1≡1 (mod M)M)M) (Nói bí quyết khác, a−1a^-1a−1 đó là 1afrac1aa1​ %\%% M)M)M). Rước ví dụ, giả dụ ta chọn M=109+7,a=2M=10^9+7, a=2M=109+7,a=2 thì a−1=500000004a^-1=500000004a−1=500000004.

Không nên lúc nào thì cũng tồn tại a−1a^-1a−1. Chỉ khi GCD(a,M)=1 extGCD(a, M)=1GCD(a,M)=1 thì mới tồn trên a−1a^-1a−1 là nghịch hòn đảo modulo MMM của aaa. Để tính nghịch đảo modulo của một số, ta hoàn toàn có thể sử dụng hai giải thuật: lời giải Euclid mở rộng hoặc dựa vào định lý Fermat nhỏ dại (áp dụng giải thuật chia để trị tính ab % ca^b \% cab % c).

2.1. Sử dụng lời giải Euclid mở rộng

Như đã trình diễn ở trên, theo lời giải Euclid mở rộng, ví như GCD(a,M)=1GCDleft(a,M ight)=1GCD(a,M)=1, ta luôn kiếm được xxx và yyy thỏa mãn: a.x+M.y=1a.x+M.y=1a.x+M.y=1. Nhưng M.yM.yM.y chia hết mang lại MMM, cho nên phương trình trở thành:

a.x≡1(mod M)a.x equiv 1 ( extmod M)a.x≡1(mod M)

Từ phía trên suy ra xxx đó là a−1a^-1a−1. Tuy nhiên trong giải thuật Euclid mở rộng, xxx rất có thể mang quý hiếm âm, yêu cầu ta sẽ kiểm soát và điều chỉnh một chút để tính giá tốt trị a−1a^-1a−1 luôn luôn không âm.

long long x;long long modulo_inverse(long long a, long long M) long long gcd = extended_euclid(a, M); if (gcd != 1) return -1; // a với M ko nguyên tố cùng nhau, không tồn tại nghịch hòn đảo modulo M của a. Return (x % M + M) % M; // vì chưng x rất có thể âm, ta có tác dụng dương nó.

2.2. Tính nghịch đảo modulo bởi định lý Fermat nhỏ

Theo định lý Fermat nhỏ, ta có: trường hợp MMM là số nguyên tố cùng aaa không chia hết mang lại MMM thì:

aM−1≡1 (mod M)a^M-1 equiv 1 ( extmod M)aM−1≡1 (mod M)

hay nói biện pháp khác:

a×aM−2≡1 (mod M)a imes a^M-2 equiv 1 ( extmod M)a×aM−2≡1 (mod M)

Điều này tương đương với việc nếu MMM là số nguyên tố với aaa không phân tách hết mang đến MMM thì aM−2a^M-2aM−2 chính là nghịch đảo modulo MMM của aaa, cũng tương tự với aM−2a^M-2aM−2 %\%% MMM là nghịch đảo modulo MMM của aaa.

long long power_mod(long long a, long long b, long long M) // Tính a^b % M. If (b == 0) return 1; if (b == 1) return a; long long half = power_mod(a, b / 2, M) % M; if (b % 2 == 0) return (half * half) % M; else return (((half * half) % M) * a) % M;long long modulo_inverse(int a, int M) return power_mod(a, M – 2, M);

3. Áp dụng nghịch hòn đảo modulo để tính ab % cfracab \% cba​ % c

Mình sẽ đề cập làm việc mục 111, phép chia không tồn tại tính chất phân phối đối với phép đồng dư thức giống như các phép cộng, trừ và nhân. Để tính ab % c,fracab \% c,ba​ % c, ta làm cho như sau:

Tách ab=(a×1b) % c=(a×b−1) % c,fracab = left(a imes frac1b ight) \% c =left(a imes b^-1 ight) \% c,ba​=(a×b1​) % c=(a×b−1) % c, trong số đó b−1b^-1b−1 là nghịch hòn đảo modulo ccc của bbb.Sau đó áp dụng đặc điểm phân phối của phép nhân đối với phép đồng dư thức, từ bây giờ phép phân chia modulo đổi mới phép nhân cùng với nghịch đảo modulo. Lưu lại ý, tùy vào giá trị ccc mà lại ta chọn cách tìm nghịch hòn đảo modulo thích hợp (ccc có là số nguyên tố giỏi không).

Cài đặt:

long long modulo_divide(long long a, long long b, long long c) long long inverse = modulo_inverse(b, c); return (a % c * inverse) % c;

4. Bậc lũy thừa theo modulo NNN (Multiplicative Order)

Xét hai số nguyên aaa và NNN nguyên tố cùng nhau, bậc lũy thừa của aaa theo modulo NNN là số nguyên dương KKK nhỏ dại nhất thỏa mãn: aK≡1 (mod N)a^K equiv 1 ext (mod ext N)aK≡1 (mod N), kí hiệu là ordN(a)ord_N(a)ordN​(a).

Theo định lý Euler, vày aaa với NNN là hai số nguyên tố thuộc nhau đề nghị aϕ(N)≡1 (mod N),a^phi(N) equiv 1 ( extmod N),aϕ(N)≡1 (mod N), cùng với ϕ(N)phi(N)ϕ(N) là số lượng số nguyên dương không vượt vượt NNN và nguyên tố cùng mọi người trong nhà với NNN. Mà lại ϕ(N)≤Nphi(N) le Nϕ(N)≤N, vì thế ordN(a)≤Nord_N(a) le NordN​(a)≤N, vậy để tìm ordN(a)ord_N(a)ordN​(a) chỉ cần duyệt một vòng lặp tự 111 tới NNN cùng với độ phức tạp O(N−1)O(N - 1)O(N−1).

int find_m_order(int a, int N) int mul = 1; for (int i = 1; i N; ++i) mul = (mul * a) % N; if (mul == 1) return i;

5. Tiêu chuẩn chỉnh Euler (Euler"s Criterion)

Đầu tiên, ta làm cho quen với tư tưởng Thặng dư bậc hai: một trong những nguyên qqq được gọi là thặng dư bậc hai theo modulo NNN nế như đó đồng dư với một số chính phương theo modulo N,N,N, nghĩa là tồn tại một trong những nguyên xxx sao cho x2≡q (mod N)x^2 equiv q ( extmod N)x2≡q (mod N).

Trong định hướng số, tiêu chuẩn Euler là một trong những công thức dùng làm xác định xem một số nguyên bao gồm phải là một trong những thặng dư bậc hai theo modulo PPP (với PPP là một trong những nguyên tố) tốt không. Theo đó, xét hai số nguyên aaa và PPP nguyên tố thuộc nhau, trong các số ấy PPP là một vài nguyên tố lẻ. Ta tất cả công thức sau:

*

Đối với trường hợp P=2,P=2,P=2, phần lớn số nguyên phần nhiều là thặng dư bậc nhì theo modulo PPP.

Ví dụ, xét P=7P = 7P=7, ta có a=2a = 2a=2 là thặng dư bậc nhì của 7,7,7, vì chưng tồn tại nhị số nguyên x=3x = 3x=3 với x=4x = 4x=4 vừa lòng a≡x2 (mod P)a equiv x^2 ext (mod ext P)a≡x2 (mod P).

Xem thêm: Các Bài Giảng Toán Lớp 2 Năm 2021, Toán Lớp 2 Bài 2: Số Hạng

long long power_mod(long long a, long long b, long long P) if (b == 0) return 1; if (b == 1) return a; long long half = power_mod(a, b / 2, P) % P; if (b % 2 == 0) return (half * half) % P; else return (((half * half) % P) * (a % P)) % P; // khám nghiệm N bao gồm phải thặng dư bậc 2 của p hay không.bool check_quadratic_residue(long long N, long long P) if (P == 2) return true; else return (power_mod(N, (P - 1) / 2, P) == 1);Trong trường hợp NNN và PPP cùng gồm dạng 4i+3 (i>0)4i + 3 (i > 0)4i+3 (i>0), thì quý giá xxx thỏa mãn nhu cầu x2≡N (mod P)x^2 equiv N ( extmod P)x2≡N (mod P) (nếu tồn tại) chỉ rất có thể là: x=± NP+14x=pm ext N^fracP + 14x=± N4P+1​. Phụ thuộc vào nhận xét này ta rất có thể tính nhanh ra quý giá xxx. Minh chứng nhận xét như sau:

Theo định lý Euler, ta có: NP−12 % P=1N^fracP - 12 \% p = 1N2P−1​ % P=1.Nhân cả hai vế với NNN:

NP+12 % P=N % P (1)N^fracP + 12 \% p = N \% phường (1)N2P+1​ % P=N % P (1)

Lại có: x2≡N (mod P)x^2 equiv N ( extmod P)x2≡N (mod P). ⇔x2≡NP+12 (mod P)Leftrightarrow x^2 equiv N^fracP+12 ( extmod P)⇔x2≡N2P+1​ (mod P) (do đẳng thức (1)(1)(1)). ⇔x2≡N2i+2 (mod P)Leftrightarrow x^2 equiv N^2i + 2 ( extmod P)⇔x2≡N2i+2 (mod P) (do N=4i+3N=4i + 3N=4i+3). ⇔x≡ Ni+1 (mod P)Leftrightarrow x equiv N^i + 1 ( extmod P)⇔x≡ Ni+1 (mod P). ⇔x≡± NP+14 (mod P)Leftrightarrow x equiv pm N^fracP + 14 ( extmod P)⇔x≡± N4P+1​ (mod P) (do P=4i+3P=4i + 3P=4i+3).

Cài đặt:

int find_quadratic_residue(int N, int P) N % 4 != 3) return -1; int x = power_mod(N, (P + 1) / 2, P); // soát sổ giá trị x đầu tiên có hợp lệ không. If ((x * x) % phường == N % P) return x; // kiểm soát giá trị x thứ hai bao gồm hợp lệ không. X = p. - x; if ((x * x) % p == N % P) return x; // còn nếu không tồn trên x, kết luận N không phải thặng dư bậc 2 của phường return -1;II. Tư liệu tham khảo: