Số học đồng dư (Phần 1): Đồng dư thức và Nghịch đảo modulo

By Admin 14/04/2024 0

I. Phép đồng dư thức cơ bản

Đồng dư thức là luật lệ toán lấy số dư của số này Lúc phân tách cho tới số không giống, kí hiệu là %\%. Ví dụ: 5%2=15 \% 2=1, Lúc bại rất có thể viết lách là 5≡15 \equiv 1 (mod(mod 2)2).

Phép đồng dư thức với đặc điểm phân phối so với luật lệ nằm trong, luật lệ nhân và luật lệ trừ, ví dụ như sau:

Bạn đang xem: Số học đồng dư (Phần 1): Đồng dư thức và Nghịch đảo modulo

  • (a+b)(a + b) %\% cc =[(a= [(a %\% c)+(bc) + (b %\% c)]c)] %\% cc.
  • (a−b)(a - b) %\% cc =[(a= [(a %\% c)−(bc) - (b %\% c)]c)] %\% cc.
  • (a×b)(a \times b) %\% cc =[(a= [(a %\% c)×(bc) \times (b %\% c)]c)] %\% cc.

Riêng so với luật lệ phân tách, tất cả chúng ta không tồn tại đặc điểm phân phối, nhưng mà nên dùng một lí thuyết là Nghịch hòn đảo modulo.

II. Nghịch hòn đảo modulo của một số

1. Định nghĩa

Như tất cả chúng ta đều biết rõ ở lịch trình Toán phổ thông, nghịch tặc hòn đảo của một trong những vẹn toàn aa (kí hiệu a−1a^{-1}) là số thỏa mãn: a.a−1=1a.a^{-1}=1.

Đối với nghịch tặc hòn đảo modulo, tao cũng đều có định nghĩa tương tự động, tuy nhiên là xét bên trên luyện số dư Lúc phân tách cho tới MM. Nghịch hòn đảo modulo MM của một trong những aa (cũng kí hiệu a−1a^{-1}) là số vẹn toàn thỏa mãn: a.a−1≡1 (moda.a^{-1}\equiv1\ (mod M)M) (Nói cách thứ hai, a−1a^{-1} đó là 1a\frac{1}{a} %\% M)M). Lấy ví dụ, nếu như tao lựa chọn M=109+7,a=2M={10}^9+7, a=2 thì a−1=500000004a^{-1}=500000004.

Không nên khi nào thì cũng tồn bên trên a−1a^{-1}. Chỉ Lúc GCD(a,M)=1GCD(a, M)=1 thì mới có thể tồn bên trên a−1a^{-1} là nghịch tặc hòn đảo modulo MM của aa. Để tính nghịch tặc hòn đảo modulo của một trong những, tao rất có thể dùng nhì giải thuật: Giải thuật Euclid không ngừng mở rộng hoặc dựa vào toan lý Fermat nhỏ (áp dụng giải thuật phân tách nhằm trị tính ab a^b\ %\ c).

2. Giải thuật Euclid cởi rộng

GCD(A,B)\text{GCD}(A,B) với 1 đặc điểm là luôn luôn rất có thể trình diễn bên dưới dạng phương trình:

Ax+By=GCD(A,B) (1)Ax+By=\text{GCD}(A,B) \ (1)

Giải thuật Euclid không ngừng mở rộng dùng nhằm thăm dò một cặp số vẹn toàn (x,y)(x,y) thỏa mãn nhu cầu phương trình bên trên, và còn dùng làm tính nghịch tặc hòn đảo modulo (mình tiếp tục rằng cho tới tại phần sau). Cặp số (x,y)(x,y) rất có thể có mức giá trị âm, hoặc bởi 00 đều được. Dưới phía trên tôi tiếp tục trình diễn giải thuật thăm dò GCD(A,B)\text{GCD}(A,B) và một cặp (x,y)(x,y) thỏa mãn nhu cầu phương trình.

long long d, x, y; // UCLN và cặp nghiệm (x, y).

void extended_euclid(long long A, long long B)
{
    if (B == 0)
    {
        x = 1;
        nó = 0;
        d = A;
    }
    else
    {
        extended_euclid(B, A % B);
        long long temp = x;
        x = y;
        nó = temp – (A / B) * y;
    }
}

int main()
{
    cin >> A >> B;
    extended_euclid(A, B);
    cout << d << ' ' << x << ‘  ‘ << y;
    return 0;
}

Cơ chế của giải thuật như sau: Ban đầu lịch trình thực đua tương đương giải thuật Euclid, cho tới Lúc B=0,B=0, Lúc bại tao sẽ sở hữu AA là ước cộng đồng lớn số 1 của AA và B,B, tiếp sau đó đặt điều x=1,y=0x=1,y=0. Bởi vì như thế B=0B=0 và lúc này GCD(A,B)=A\text{GCD}(A,B)=A nên phương trình (1)(1) trở thành:

A.1+0.0=AA.1+0.0=A

Sau bại lịch trình gọi lại những mệnh lệnh bên dưới điều gọi đệ quy nhằm thăm dò đi ra xx và yy. Chứng minh như sau:

  • Sau Lúc gọi đệ quy, phương trình ở bước tiếp sau của giải thuật là:

B.x+(A%B).y=GCD(A,B) (2)B.x+(A \% B).y=\text{GCD}(A,B) \ (2)

  • Thay A % B=A−⌊AB⌋.BA \ \% \ B=A-\left \lfloor{\frac{A}{B}} \right \rfloor .B, phương trình (2)(2) trở thành:

B.x+(A-\left \lfloor{\frac{A}{B}} \right \rfloor.B).y=\text{GCD}(A,B)$$ $$\Leftrightarrow A.y+B.(x-\left \lfloor{\frac{A}{B}} \right \rfloor.y)=\text{GCD}(A,B)

  • Từ phía trên được công thức đệ quy:

x′=y;y′=x−⌊AB⌋.yx' = y; y' = x - \left \lfloor{\frac{A}{B}} \right \rfloor.y

  • Như vậy kể từ bước cơ bạn dạng x=1,y=0;x=1,y=0; lịch trình tiếp tục nối tiếp tính ngược lên nhằm đi ra được x,yx,y thỏa mãn nhu cầu phương trình lúc đầu. Độ phức tạp giải thuật là O(log⁡(max⁡(A,B)))O\Big(\log\big(\text{max}⁡(A,B)\big)\Big).

Ngoài đi ra, giải thuật Euclid không ngừng mở rộng còn rất có thể dùng nhằm giải phương trình Diophantine tuyến tính, sẽ tiến hành rằng cho tới ở một nội dung bài viết không giống.

3. Tính toán nghịch tặc hòn đảo Modulo của một số

Sử dụng giải thuật Euclid cởi rộng

Như tiếp tục trình diễn phía trên, theo dõi giải thuật Euclid không ngừng mở rộng, nếu như GCD(a,M)=1GCD\left(a,M\right)=1, tao luôn luôn tìm ra xx và yy thỏa mãn: a.x+M.y=1a.x+M.y=1. Mà M.yM.y phân tách không còn cho tới MM, vì thế phương trình trở thành:

a.x≡1(mod M)a.x \equiv 1 (\text{mod} \ M)

Xem thêm: Người bán vé số lời bao nhiêu? Thu nhập trung bình khi bán 100 tờ

Từ phía trên suy đi ra xx đó là a−1a^{-1}. Tuy nhiên nhập giải thuật Euclid không ngừng mở rộng, xx rất có thể đem độ quý hiếm âm, nên tao tiếp tục kiểm soát và điều chỉnh một chút ít nhằm tính giá tốt trị a−1a^{-1} luôn luôn ko âm. Code tiếp sau đây tiếp tục tái mét dùng lại đoạn code giải thuật Euclid không ngừng mở rộng ở phía trên:

long long modulo_inverse(long long a, long long M)
{
    extended_euclid(a, M);
	  
    // a và M ko nhân tố bên nhau, ko tồn bên trên nghịch tặc hòn đảo modulo M của a.
    if (d != 1)
        return -1; 

    // Do x rất có thể âm, tao thực hiện dương nó.
    return (x % M + M) % M; 
}

Tính nghịch tặc hòn đảo modulo bởi toan lý Fermat nhỏ

Theo toan lý Fermat nhỏ, tao có: Nếu MM là số nhân tố và aa ko phân tách không còn cho tới MM thì:

a^{M-1}\equiv 1 \ (\text{mod} \ M)$$ hoặc rằng cơ hội khác: $$a\times a^{M-2} \equiv 1 \ (\text{mod} \ M)

Điều này tương tự với việc nếu như MM là số nhân tố và aa ko phân tách không còn cho tới MM thì aM−2a^{M-2} đó là nghịch tặc hòn đảo modulo MM của aa, cũng tương tự với aM−2a^{M-2} %\% MM là nghịch tặc hòn đảo modulo MM của aa.

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);
}

4. gí dụng nghịch tặc hòn đảo modulo nhằm tính ab % c\frac{a}{b} \ \% \ c

Mình tiếp tục rằng ở mục 11, luật lệ phân tách không tồn tại đặc điểm phân phối so với luật lệ đồng dư thức tương đương tựa như những luật lệ nằm trong, trừ và nhân. Để tính ab % c,\frac{a}{b} \ \% \ c, tao thực hiện như sau:

  • Tách ab=(a×1b) % c=(a×b−1) % c,\frac{a}{b} = \left(a \times \frac{1}{b}\right) \ \% \ c =\left(a \times b^{-1}\right) \ \% \ c, nhập bại b−1b^{-1} là nghịch tặc hòn đảo modulo cc của bb.
  • Sau bại vận dụng đặc điểm phân phối của luật lệ nhân so với luật lệ đồng dư thức, thời điểm hiện tại luật lệ phân tách modulo phát triển thành luật lệ nhân với nghịch tặc hòn đảo modulo. Lưu ý, tùy nhập độ quý hiếm cc nhưng mà tao chọn lựa cách thăm dò nghịch tặc hòn đảo modulo phù hợp (cc với là số nhân tố hoặc 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;
}

III. Một số kỹ năng và kiến thức nâng lên khác

1. Bậc lũy quá theo dõi modulo NN (Multiplicative Order)

Xét nhì số vẹn toàn aa và NN nhân tố bên nhau, bậc lũy thừa của aa theo dõi modulo NN là số vẹn toàn dương KK nhỏ nhất thỏa mãn: aK≡1 (mod N)a^K \equiv 1 \text{ } (mod \text{ } N), kí hiệu là ordN(a)ord_N(a).

Theo toan lý Euler, vì như thế aa và NN là nhì số nhân tố bên nhau nên aϕ(N)≡1 (mod N),a^{\phi(N)} \equiv 1 \ (\text{mod} \ N), với ϕ(N)\phi(N) là con số số vẹn toàn dương ko vượt lên trên quá NN và nhân tố bên nhau với NN. Mà ϕ(N)≤N\phi(N) \le N, vì thế ordN(a)≤Nord_N(a) \le N, vậy nhằm thăm dò ordN(a)ord_N(a) chỉ việc duyệt một vòng lặp kể từ 11 cho tới NN với chừng phức tạp 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;
    }
}

2. Tiêu chuẩn chỉnh Euler (Euler's Criterion)

Đầu tiên, tao thích nghi với định nghĩa Thặng dư bậc hai: Một số vẹn toàn qq được gọi là thặng dư bậc hai theo dõi modulo NN nếu mà nó đồng dư với một trong những chủ yếu phương theo dõi modulo N,N, tức thị tồn bên trên một trong những vẹn toàn xx sao cho tới x2≡q (mod N)x^2 \equiv q \ (\text{mod} \ N).

Trong lý thuyết số, tiêu chuẩn chỉnh Euler là một trong những công thức dùng làm xác lập coi một trong những vẹn toàn với nên là một trong những thặng dư bậc nhì theo dõi modulo PP (với PP là một trong những vẹn toàn tố) hay là không. Theo bại, xét nhì số vẹn toàn aa và PP nhân tố bên nhau, nhập bại PP là một trong những nhân tố lẻ. Ta với công thức sau:

aP−12≡{1 (mod P),neˆˊu a laˋ thặng dư bậc hai của P.−1 (mod P),neˆˊu a khoˆng laˋ thặng dư bậc hai của P.a^{\frac{P - 1}{2}} \equiv \begin{cases}1 \text{ }(\text{mod} \ P),&\text{nếu }a \text{ là thặng dư bậc nhì của }P. \\ -1\text{ }(\text{mod} \ P),& \text{nếu }a \text{ ko là thặng dư bậc nhì của }P.\end{cases}

Đối với tình huống P=2,P=2, từng số vẹn toàn đều là thặng dư bậc nhì theo dõi modulo PP.

Ví dụ, xét P=7P = 7, tao với a=2a = 2 là thặng dư bậc nhì của 77, vì như thế tồn bên trên nhì số vẹn toàn x=3x = 3 và x=4x = 4 thỏa mãn nhu cầu a≡x2 (mod P)a \equiv x^2 \text{ } (mod \text{ } P).

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;
}
    
// Kiểm tra N với nên thặng dư bậc 2 của P.. hay là 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 tình huống NN và PP cùng theo với dạng 4i+3 (i>0)4i + 3 \ (i > 0), thì độ quý hiếm xx thỏa mãn nhu cầu x2≡N (mod P)x^2 \equiv N \ (\text{mod} \ P) (nếu tồn tại) chỉ rất có thể là: x=± NP+14x=\pm \text{ }N^{\frac{P + 1}{4}}. Dựa nhập phán xét này tao rất có thể tính thời gian nhanh đi ra độ quý hiếm xx. Chứng minh phán xét như sau:

Xem thêm: Tải phim về xem offline

  • Theo toan lý Euler, tao có: NP−12 % P=1N^{\frac{P - 1}{2}} \ \% \ P.. = 1.
  • Nhân cả nhì vế với NN:

NP+12 % P=N % P (1)N^{\frac{P + 1}{2}} \ \% \ P.. = N \ \% \ P.. \ (1)

  • Lại có: x2≡N (mod P)x^2 \equiv N \ (\text{mod} \ P).       ⇔x2≡NP+12 (mod P)\Leftrightarrow x^2 \equiv N^{\frac{P+1}{2}} \ (\text{mod} \ P) (do đẳng thức (1)(1)).       ⇔x2≡N2i+2 (mod P)\Leftrightarrow x^2 \equiv N^{2i + 2} \ (\text{mod} \ P) (do N=4i+3N=4i + 3).       ⇔x≡ Ni+1 (mod P)\Leftrightarrow x \equiv \ N^{i + 1} \ (\text{mod} \ P).       ⇔x≡± NP+14 (mod P)\Leftrightarrow x \equiv \pm \ N^{\frac{P + 1}{4}} \ (\text{mod} \ P) (do P=4i+3P=4i + 3).

Cài đặt:

int find_quadratic_residue(int N, int P)
{
    // P.. và N ko ở chính dạng 4i + 3, ko tính được Theo phong cách này.
    if (P % 4 != 3 || N % 4 != 3)
        return -1;
            
    int x = power_mod(N, (P + 1) / 2, P);

    // Kiểm tra độ quý hiếm x loại nhất với hợp thức ko.
    if ((x * x) % P.. == N % P)
        return x;

    // Kiểm tra độ quý hiếm x loại nhì với hợp thức ko.
    x = P.. - x;
    if ((x * x) % P.. == N % P)
        return x;

     // Nếu ko tồn bên trên x, Kết luận N ko nên thặng dư bậc 2 của P
    return -1;
}

IV. Tài liệu tham ô khảo

  • https://en.wikipedia.org/wiki/Quadratic_residue
  • https://en.wikipedia.org/wiki/Euler%27s_criterion
  • https://vnoi.info/wiki/translate/he/So-hoc-Phan-1-Modulo-gcd.md
  • https://vnoi.info/wiki/algo/math/modular-inverse.md
  • https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
  • https://en.wikipedia.org/wiki/Multiplicative_order
  • https://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_Euler
  • https://www.geeksforgeeks.org/find-square-root-under-modulo-p-set-1-when-p-is-in-form-of-4i-3/

©️ Tác giả: Vũ Quế Lâm kể từ Viblo