Chương 2. Cơ s ở toán h ọc
c ủa lý thuy ết m ật mã


2.1 Số học các số nguyên và
thuật toán Euclide
Tính chia h ết c ủa s ố nguyên








Cho a, b≠0 là các số nguyên. Ta nói a chia hết
cho b nếu tồn tại 1 số c sao cho:
a=b.c
Ký hiệu b|a
a là bội số của b (divisor), b là ước số của a
( mutiple)
Ví dụ: 2| 6


Tính chia h ết c ủa các s ố nguyên











Cho hai số a, b ∈Z\{0}, c∈Z được gọi là ước chung
của a và b nếu c|a và c|b
C được gọi là ước chung lớn nhất, ký hiệu gcd(a,
b), nếu nó là số nguyên lớn nhất a, b chia hết.


B ội chung nh ỏ nh ất(Least common
multiple)




Cho hai số a, b ∈Z\{0}, c∈Z được gọi là bộichung
của a và b nếu a|c và b|c
C được gọi là bộichung nhỏ nhất, ký hiệu lcm(a,
b), nếu nó là số nguyên nhỏ nhất chia hết cho a,
b.


Thuật toán Euclide tìm UCLN
 Input:

hai số không âm a, b, a>=b
 Output: gcd(a, b).
Trong khi b>=0 thực hiện:
r a mod b








Số tự nhiên 11đều có thể viết dưới dạng:
n=p1a1 .p2a2 …pkak
Lưu ý: số 1 không pải là ngto cũng không phải là hợp
số.


Hàm đ ếm các s ố nguyên t ố


Hàm đếm các số nguyên tố(prime counting
function) ∏(n) cho kết quả là các số nguyên tố
nhỏ hơn hay bằng n∈N
∏(n)=|{p∈P| p≤n}|


Phân tích h ợp s ố thành th ừa s ố
nguyên tố



Dùng để đếm các số
Quan hệ đồng dư theo modular n là quan hệ tương
đương


Các phép toán đ ồng dư


Có thể thực hiện các phép cộng và nhân phần dư
tương tự như cộng nhân các số nguyên.

Rn (a + b) = Rn ( Rn (a ) + Rn (b))
Rn (a.b) = Rn ( Rn (a ).Rn (b))


Ví dụ:

R 7 (12 + 18) = R7 ( R7 (12) + R7 (18)) = 2
R7 (12.18) = R7 ( R7 (12).R7 (18)) = R7 (4.5) = 6


Ngh ịch đ ảo nhân


Nếu tồn tại một số b∈Zn sao cho ab≡1(mod n) thì
b được gọi là nghịch đảo nhân của a modulo n.
−1

b = a (mod n)




au + pu = 1
−1

u = a mod p


C2: dùng giải thuật tính số mũ nhanh

a

−1

≡a

p −2

mod p


Cách tìm ngh ịch đ ảo nhân(tt)





Để tìm nghịch đảo nhân modulo n , áp dụng
Euclid mở rộng:
xa + yn = gcd(a, n) = 1