Lý thuyết toán học

Về cơ bản a ≡ b(mod n) nếu a = b+kn trong đó k là một số nguyên. Nếu a và b dương và a nhỏ hơn n, bạn có thể nghĩ rằng a là phần dư của b khi chia cho n. Nói chung a và b đều là phần dư khi chia cho n. Đôi khi b gọi là thặng dư của a, modulo n, đôi khi a gọi là đồng dư của b, modulo n.

Tập hợp các số nguyên từ 0 đến n-1 còn được gọi là tập hợp thặng dư hoàn toàn modulo n. Điều này có nghĩa là, với mỗi số nguyên a, thì thặng dư modulo n là một số từ 0 đến n-1.

Modulo số học cũng giống như số học bình thường, bao gồm các phép giao hoán, kết hợp và phân phối. Mặt khác giảm mỗi giá trị trung gian trong suốt quá trình tính toán.

(a+b) mod n = ((a mod n) + (b mod n)) mod n

(a- b) mod n = ((a mod n) - (b mod n)) mod n

(a×b) mod n = ((a mod n) × (b mod n)) mod n

(a×(b + c)) mod n = (((a × b) mod n) + ((a × c) mod n)) mod n

Hệ thống mã hoá sự dụng nhiều sự tính toán modulo n, bởi vì vấn đề này giống như tính toán logarithm rời rạc và diện tích hình vuông là khó khăn. Mặt khác nó làm việc dễ hơn, bởi vì nó bị giới hạn trong tất cả giá trị trung gian và kết quả. Ví dụ : a là một số k bits, n là kết quả trung gian của phép cộng, trừ, nhân sẽ không vượt quá 24 bits. Như vậy chúng ta có thể thực hiện hàm mũ trong modulo số học mà không cần sinh ra kết quả trung gian đồ sộ.

Số nguyên tố là một số lớn hơn 1, nhưng chỉ chia hết cho 1 và chính nó, ngoài ra không còn số nào nó có thể chia hết nữa. Số 2 là một số nguyên tố. Do vậy 7, 17, 53, 73, 2521, 2365347734339 cũng là số nguyên tố. Số lượng số nguyên tố là vô tận. Hệ mật mã thường sử dụng số nguyên tố lớn cỡ 512 bits và thậm chí lớn hơn như vậy.

Hai số gọi là cặp số nguyên tố khi mà chúng không có thừa số chung nào khác 1, hay nói một cách khác, nếu ước số chung lớn nhất của a và n là bằng 1. Chúng ta có thể viết như sau :

gcd(a,n)=1

Số 15 và 28 là một cặp số nguyên tố, nhưng 15 và 27 thì không phải cặp số nguyên tố do có ước số chung là 1 và 3, dễ dàng thấy 13 và 500 cũng là một cặp số nguyên tố. Một số nguyên tố là một cặp số nguyên tố với tất cả những số khác loại trừ những số là bội số.

Một cách dễ nhất để tính toán ra ước số chung lớn nhất của hai số là nhờ vào thuật toán Euclid. Knuth mô tả thuật toán và một vài mô hình của thuật toán đã được sửa đổi.

Dưới đây là đoạn mã nguồn trong ngôn ngữ C.

/* Thuật toán tìm ước số chung lớn nhất của x và y, giả sử x,y>0 */

int gcd(int x, int y)

{
    int g;
    if(x<0)
        x=-x; 
    if(y<0)
        y=-y;
    g=y;
    while(x>0){
        g=x;
        x=y%x;
        y=g;
    }
    return g;
}
    

Thuật toán sau đây có thể sinh ra và trả lại ước số chung lớn nhất của một mảng m số.

int multiple gcd ( int m, int *x)
{
    size t, i ;
    int g;
    if(m<1)
         return(0);
    g = x[0];
    for(i=1;i<m;++i){
         g=gcd(g,x[i]);
         if(g==1)
             return 1;
    }
    return g;
}
    

Số nghịch đảo của 10 là 1/10, bởi vì 10 × 1/10=1. Trong số học modulo thì vấn đề nghịch đảo phức tạp hơn.

4 × x ≡ 1 mod 7

Phương trình trên tương đương với tìm x và k sao cho

4x = 7k+1

với điều kiện là cả x và k đều là số nguyên.

Vấn đề chung đặt ra tại đây là tìm x sao cho

1 = (a × x) mod n

có thể viết lại như sau :

a^-1 ≡ x(mod n )

Sự thu nhỏ vấn đề Modulo là rất khó giải quyết. Đôi khi nó là một vấn đề, nhưng đôi khi lại không phải vậy.

Trong trường hợp chung a^-1 ≡ x (mod n) chỉ có duy nhất một giải pháp nếu a và n là một cặp số nguyên tố. Nếu a và n không phải là cặp số nguyên tố, thì a^-1 ≡ x (mod n) không có giải pháp nào. Thuật toán Euclid có thể tính ra được số nghịch đảo của số Modulo n, đôi khi thuật toán này còn gọi là thuật toán Euclid mở rộng. Sau đây thuật toán được mô tả trong ngôn ngữ C.

static void Update(int *un,int *vn, int q)
{
    int tn;
    

tn = *un-vn*q;
    *un = *vn;
    *vn = tn;
    }
    
        int extended euclidian(int u,int v,int u1_out,int u2_out)
    {
    int u1=1;
    int u3=u;
    int v1=0;
    int v3=v;
    int q;
    while(v3>0){
        q=u3/v3;
        Update(&u1,&v1,q);
        Update(&u3,&v,q);
    }
    *u1_out=u1;
    *u2_out=(u3-u1*u)/v;
    return u3;
}
    

Ký hiệu L(a,p) được định nghĩa khi a là một số nguyên và p là một số nguyên tố lớn hơn 2. Nó nhận ba giá trị 0, 1, -1 :

L(a,p) = 0 nếu a chia hết cho p.

L(a,p) = 1 nếu a là thặng dư bậc 2 mod p.

L(a,p) = -1 nếu a không thặng dư mod p.

Một phương pháp dễ dàng để tính toán ra L(a,p) là :

L(a,p) = a ^(p-1)/2 mod p

Ký hiệu Jacobi được viết J(a,n), nó là sự khái quát hoá của ký hiệu Lagrăng, nó định nghĩa cho bất kỳ cặp số nguyên a và n. Ký hiệu Jacobi là một chức năng trên tập hợp số thặng dư thấp của ước số n và có thể tính toán theo công thức sau:

• Nếu n là số nguyên tố, thì J(a,n) = 1 với điều kiện a là thặng dư bậc hai modulo n .
• Nếu n là số nguyên tố, thì J(a,n) = -1 với điều kiện a không là thặng dư bậc hai modulo n .
• Nếu n không phải là số nguyên tố thì Jacobi

J(a,n)=J(h,p₁) × J(h,p₂) ×. . . × J(h,p_m)

với p₁,p₂. . .,p_m là các thừa số lớn nhất của n.

Thuật toán này tính ra số Jacobi tuần hoàn theo công thức sau :

1. J(1,k) = 1

2. J(a×b,k) = J(a,k) × J(b,k)

1. J(2,k) =1 Nếu (k²-1)/8 là chia hết

J(2,k) =-1 trong các trường hợp khác.

4. J(b,a) = J((b mod a),a)

5. Nếu GCD(a,b)=1 :

a. J(a,b) × J(b,a) = 1 nếu (a-1)(b-1)/4 là chia hết.

b. J(a,b) × J(b,a) = -1 nếu (a-1)(b-1)/4 là còn dư.

Sau đây là thuật toán trong ngôn ngữ C :

int jacobi(int a,int b)
{
    int a1,a2;
    if(a>=b)
        a%=b;
    if(a==0)
        return 0;
    if(a==1)
        return 1;
    if(a==2)
        if(((b*b-1)/8)%2==0)
           return 1;
        else
           return -1;
    if(a&b&1) (cả a và b đều là số dư)
        if(((a-1)*(b-1)/4)%2==0)
           return +jacobi(b,a);
        else
           return -jacobi(b,a);
    if(gcd(a,b)==1)
        if(((a-1)*(b-1)/4)%2==0)
           return +jacobi(b,a);
        else
           return -jacobi(b,a);
    factor2(a,&a1,&a2);
    return jacobi(a1,b) * jacobi(a2,b);
}
    

Nếu p là số nguyên tố có cách tốt hơn để tính số Jacobi như dưới đây :

1. Nếu a=1 thì J(a/p)=1

2. Nếu a là số chai hết, thì J(a,p)=J(a/2,p) × (-1)^{(p^2 –1)/8}

3. Nếu a là số dư khác 1 thì J(a,p)=J(p mod a, a) × (-1)^{(a-1)×(p-1)/4}

Nếu bạn biết cách tìm thừa số nguyên tố của một số n, thì bạn có thể đã sử dụng, một số điều gọi là định lý phần dư trung hoa để giải quyết trong suốt hệ phương trình. Bản dịch cơ bản của đinh lý này được khám phá bởi toán học Trung Hoa vào thế kỷ thứ nhất.

Giả sử, sự phân tích thừa số của n=p₁×p₂×. . .×p_t thì hệ phương trình

(X mod p_i) = a_i , với i=1,2,. . .t

có duy nhất một cách giải, tại đó x nhỏ hơn n.

Bởi vậy, với a,b tuỳ ý sao cho a < p và b < q (p,q là số nguyên tố) thì tồn tại duy nhất a,x ,khi x nhỏ hơn p×q thì

x ≡ a (mod p), và x ≡ b (mod q)

Để tìm ra x đầu tiên sử dụng thuật toán Euclid để tìm u, ví dụ :

Dưới đây là đoạn mã định lý phần dư trung hoa trong ngôn ngữ C :

Int chinese remainder(size t r, int *m, int *u)
{
    size t i;
    int modulus;
    int n;
    modulus = 1;
    for ( i=0; i<r:++i ) 
        modulus *=m[i];
        n=0;
    for ( i=0; i<r:++i ) 
{
    n+=u[i]*modexp(modulus/m[i],totient(m[i]),m[i]);
        n%=modulus;
    }
    return n;
}
    

Nếu m là số nguyên tố, và a không phải là bội số của m thì định lý Fermat phát biểu :

a^m-1 ≡ 1(mod m)