1
Lecture 4: Giớithiệu Lý thuyếtsố
1.
1.
M
M
ộ
ộ
t s
t s
ố
ố
đ
đ
ị
ị
nh ngh
nh ngh
ĩ
ĩ
a
a
2.
2.
C
C
á
á
c s
c s
ố
ố
nguyên t
nguyên t
ố
ố
-
-
Prime Numbers
Prime Numbers
3. Phân tích ra thừa số nguyên tố - Prime Factorisation
4. Các số nguyên tố cùng nhau và greatest common divisor
(GCD)
5. Định lý Ferma nhỏ - Fermat's Little Theorem
6. Hàm Ơle ø(n)
7. Định lý Ole - Euler's Theorem
8. Kiểm tra tính nguyên tố -Thuật toán Miller - Rabin
9. Định lý phần dư Trung Hoa
2
Một số định nghĩa
•Tập số tự nhiên:
– N = {0, 1, 2, 3, 4, . . . }
•Tập số nguyên:
– Z = {0, ±1, ±2, ±3, . . . }
3
Các số nguyên tố - Prime Numbers
• Là các số nguyên dương chỉ có ướcsố là 1 và chính nó.
• Chúng không thểđượcviếtdướidạng tích của các số khác
•1 làsố nguyên tố, nhưng không quan tâm đếnnó
• 2, 3, 5, 7 là số nguyên tố; 4, 6, 8, 9, 10 không phảilàsố nguyên tố
•Cácsố nguyên tố là trung tâm của lý thuyếtsố
• Danh sách các số nguyên tố nhỏ hơn 200
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
59 61 67 71 73 79 83 89 97 101 103 107 109
113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199
4
Phân tích ra thừasố nguyên tố
• Phân tích ra thừasố nguyên tố số N tứclàviếtnó
dướidạng tích của các số nguyên tố: n=a x b x c
–Vídụ: 91=7x13 ; 3600=2
4
x3
2
x5
2
• Bài toán phân tích ra thừa số nguyên tố là bài toán
khó.
5
Các số nguyên tố cùng nhau và greatest
common divisor (GCD)
•Haisố a và b không có ước chung nào ngoài 1, đượcgọi là nguyên
tố cùng nhau
–Vídụ: 8 và 15 là nguyên tố cùng nhau, vì ướccủa 8 là 1, 2, 4, 8,
còn ướccủa 15 là 1, 3, 5, 15. Chỉ có 1 là ước chung
•Ngượclạicóthể xác định ước chung lớnnhất -GCD bằng cách
trong các phân tích ra thừasố của chúng, tìm các thừasố nguyên tố
chung và lấybậclũythừanhỏ nhất.
–Vídụ: 300=2
1
x3
1
x5
2
18=2
1
x3
2
,suy ra
GCD(18,300)=2
1
x3
1
x5
0
=6
6
Định lý Ferma nhỏ
Fermat's Little Theorem
•Giả sử p là số nguyên tố và a là số tự nhiên thì
a
p
=a (mod p)
•Nếu p là số nguyên tố và GCD(a, p) = 1
a
p-1
= 1 (mod p)
–Vídụ:
2
7-1
mod 7 = 2
6
mod 7 = 64 mod 7 = 1
3
5-1
mod 5 = 3
4
mod 5 = 81 mod 5 = 1
• Định lý Fermat nhỏ được dùng trong khoá công khai và kiểm
tra tính nguyên tố:
7
Hàm Ole - ø(n)
•Tập đầy đủ các phầndư theo n là: 0, 1, 2, …, n-1
•Xéttập rút gọncủatậpphầndư trên bao gồm các số nguyên tố cùng
nhau vớin.
•Vídụ với n = 10
–Tập đầy đủ các phầndư là {0,1,2,3,4,5,6,7,8,9}
•Tập rút gọn các phầndư nguyên tố cùng nhau với 10 là: {1,3,7,9}
•Số các phầntử củatập rút gọntrênlàgiátrị của hàm Ole ø(n)
8
Hàm Ơle ø(n)
•Muốn tính ø(n) việc đếmsố các số nguyên tố cùng nhau với n và có
giá trị nhỏ hơnnđượcloạibỏ vì đây là bài toán tốn nhiềucôngsức
• Nói chung cầnbiểuthứcphântíchrathừasố
–Nếu p là số nguyên tố ø(p) = p-1
–Nếu p và q là hai số nguyên tố khác nhau
ø(p.q) = (p-1)(q-1)
–Vídụ :
ø(37) = 36
ø(21) = ø( 3&7)=(3–1)×(7–1) = 2×6 = 12
9
Tính ø(n)
•Vídụ:
ø(72) = ø(8.9) = ø(8). ø(9) = ø(2
3
).ø(3
2
) =
= (2
3
-2
2
)(3
2
-3
1
) = 4.6 = 24
Công thức tính ø(n):
10
Định lý Ole - Euler's Theorem
•Tổng quát hoá của Định lý Ferma
a
ø(n)
= 1 (mod n) -
vớimọi a, n trong đó gcd(a,n)=1
•Vídụ:
– a=3; n=10; ø(10)=4;
Suy ra: 3
4
= 81 = 1 mod 10
– a=2; n=11; ø(11)=10;
Suy ra 2
10
= 1024 = 1 mod 11
11
Kiểm tra tính nguyên tố
Primality Testing
•Giả sử cầnphải tìm mộtsố nguyên tố rấtlớn
–Lấymộtsốđủlớn. Phương pháp truyềnthống là thử bằng phép
chia: chia cho tấtcả các số (chỉ cần nguyên tố) nhỏ hơnhoặc
bằng cănbậchaicủasốđó.
–Phương pháp chia chỉ hiệuquả khi cần kiểm tra các số nhỏ.
•Cóphương pháp khác sử dụng các phép kiểm tra tính nguyên tố dựa
trên các tính chất:
–Màmọisố nguyên tố phảithỏamãn
–Nhưng có mộtsố số không phải là số nguyên tố, gọilàgiả
nguyên tố cũng thoả mãn tính chất đó.
12
Thuật toán Miller - Rabin
13
Thuật toán Miller - Rabin
14
Thuật toán Miller - Rabin
Không có nhận xét nào:
Đăng nhận xét