Giáo trình Số học thuật toán - Bài tập kiểm tra kiến thức

n thiết để thực hiện thuật toán. 
 d) Số phép tính bit cần thiết, xét nh− một hàm của độ lớn đầu vào. 
Điểm: a b c d 
 3 5 7 10 
2. Một thuật toán đ−ợc gọi là có độ phức tạp đa thức nếu đầu vào có độ lớn n thì thời gian 
thực hiện thuật toán không v−ợt quá: 
 a) O(nd) với d là một số nguyên d−ơng nào đó. 
 b) O(logdn) với d là một số nguyên d−ơng nào đó. 
 c) O(1). 
 d) O(f(n)) với f(n) là một đa thức của n. 
Điểm: a b c d 
 0 10 0 0 
3. Thuật toán khai triển số nguyên ra thừa số nguyên tố có độ phức tạp: 
 a) mũ 
 b) đa thức 
 c) d−ới mũ 
 d) ch−a đánh giá đ−ợc 
Điểm: a b c d 
 0 0 10 0 
Ch−ơng 2. 
1. Giả sử b là số nguyên lớn hơn 1 và n là số đ−ợc biểu diễn d−ới dạng: 
 113
n=akb
k+ak-1b
k-1+...+a1b+a0, 
trong đó aj nguyên, 0≤aj≤b-1, j=0, 1,..., k; ak≠ 0. Khi đó số chữ số của n trong cơ sở b là 
 a) n/b 
 b) log2n 
 c) [logbn]+1 
 d) [logbn] 
Điểm: a b c d 
 0 0 10 8 
2. a) Để cọng trừ hai số nguyên k-bit, ta cần O(k2) phép tính bit. 
b) Để cọng trừ hai số nguyên k-bit, ta cần O(k) phép tính bit. 
c) Giả sử n, m là các số trong cơ số 2, có k chữ số. Để nhân m với n (theo quy tắc thông 
th−ờng) ta cần O(k) phép tính bit. 
d) Nh− câu c), cần O(k2) phép tính bit. 
Điểm: a b c d 
 0 10 0 10 
3. a) Mọi −ớc nguyên tố của hợp số n đều nhỏ hơn n . 
b) Để kiểm tra xem n có phải là số nguyên tố hay không, cần làm n phép chia. 
c) Để kiểm tra xem n có phải là số nguyên tố hay không, cần làm ít nhất là n phép tính 
bit. 
d) Để kiểm tra xem n có phải là số nguyên tố hay không, cần làm O( n ) phép tính bit. 
Điểm; a b c d 
 0 0 3 10 
4. Cho 2 số nguyên d−ơng a, b. Khi đó số phép tính bit cần thiết để thực hiện thuật toán 
Euclid tìm ƯCLN của a và b là: 
 a) O(ab) 
 b) O(log2a.log2b) 
 c) O((log2a)
2) nếu a<b 
 d) O((log2a)
3) nếu a<b 
 114
Điểm; a b c d 
 0 2 4 10 
5. a) Nếu p là số nguyên tố thì (p-1)!≡ 1(mod p) 
b) Nếu p là số nguyên tố và a là số nguyên d−ơng thì ap-1≡ 1(mod p) 
c) p là số nguyên tố khi và chỉ khi (p-1)! ≡ -1(mod p) 
d) Nếu p là số nguyên tố và a là số nguyên d−ơng thì ap-2 là nghịch đảo modulo p 
Điểm; a b c d 
` 0 5 10 5 
6. a) Nếu với mọi số a nguyên d−ơng, ap≡ a(mod p) thì p là số nguyên tố. 
b) Nếu với một số a nguyên d−ơng nào đó, ap≡ a(mod p) thì p là số nguyên tố. 
c) Có vô hạn hợp số p sao cho với mọi số a nguyên tố cùng nhau với p, ta có 
ap-1≡ 1(mod p). 
d) Tồn tại hữu hạn số có tính chất nói trong câu c). 
Điểm; a b c d 
 0 0 10 5 
7. Cho n là số nguyên d−ơng lẻ, n=2st+1, trong đó t lẻ, s≥0. Giả sử với 5 số ngẫu nhiên 
a1, a2, a3, a4, a5 <n ta có ai
t≡ 1(mod n). Có thể kết luận 
 a) n là hợp số 
 b) n là số nguyên tố 
 c) n là số nguyên tố với xác xuất lớn hơn 1-1/25 
 d) n là số nguyên tố với xác xuất lớn hơn 1-1/45 
Điểm; a b c d 
 0 2 5 10 
Ch−ơng 3 
1. Trong các hàm số học sau đây những hàm nào là hàm nhân tính mạnh 
 a) f(n)=tích các −ớc nguyên tố của n 
 115
 b) f(n)= tổng các −ớc nguyên tố của n 
 c) f(n)= tích các −ớc của n 
 d) f(n)=n2 
Điểm; a b c d 
 3 0 3 10 
(Nếu đánh dấu nhiều hơn 1 khả năng thì điểm bằng minimum của điểm các khả năng đó) 
2. Kí hiệu ϕ là Phi-hàm Euler. 
 a) m, a nguyên d−ơng thì a mϕ ( ) ≡ 1(mod m) 
 b) m, a nguyên d−ơng thì a mϕ ( ) ≡ a(mod m) 
 c) m, a nguyên d−ơng, nguyên tố cùng nhau thì a mϕ ( ) ≡ 1(mod m) 
 d) m, a nguyên d−ơng, nguyên tố cùng nhau thìa mϕ ( ) ≡ a(mod m) 
Điểm; a b c d 
 3 0 10 0 
3. Trong các hệ sau đây, những hệ nào thặng d− thu gọn modulo 24 
 a) 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 
 b)1, 2, 3, 5, 7, 9, 11, 13, 15, 17, 19 
 c) 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 
 d) 5, 25, 35, 55, 65, 85, 95, 115 
Điểm; a b c d 
 0 0 0 10 
(Nếu đánh dấu nhiều hơn 1 khả năng thì điểm bằng minimum của điểm các khả năng đó) 
4. Giả sử m là số nguyên d−ơng và Mm=2m-1 là số Mersenne thứ m. Khi đó 
 a) Mm là hợp số 
 116
 b) Mm là số nguyên tố 
 c) Các −ớc nguyên tố của Mm có dạng 2kp+1 với p nguyên tố lẻ 
 d) Có vô hạn m để Mm nguyên tố 
Điểm; a b c d 
 0 0 10 5 
5. Trong các số sau đây số nào có căn nguyên thuỷ 
 a) 1996 b) 1997 c) 1998 d) 1999 
Điểm; a b c d 
 -5 5 -5 5 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
6. Hỏi cũng nh− câu 5. 
 a) 1250 b)1251 c) 2401 d) 3993 
Điểm; a b c d 
 5 -5 5 -5 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
Ch−ơng 4 
1. Trong các số 1, 2, ..., 1996 số các số là thặng d− bình ph−ơng của 1997 là 
 a) 998 b)0 c) 1995 d) 999 
Điểm; a b c d 
 10 0 0 0 
2. Fm=2 1
2m + là số Fermat thứ m 
a) Fm là số nguyên tố với mọi m 
b) Fm là hợp số với mọi m 
c) Fm là số nguyên tố nếu 3
1 2( )/Fm− ≡ -1(mod Fm) 
 117
d) Fm là số nguyên tố thì 3
1 2( )/Fm− ≡ -1(mod Fm) 
Điểm; a b c d 
 -5 -5 5 5 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
3. Đánh dấu những câu đúng: 
 a) Số giả nguyên tố Euler cơ sở b là số giả nguyên tố cơ sở b 
 b) Số giả nguyên tố cơ sở b là số giả nguyên tố Euler cơ sở b 
 c) Số giả nguyên tố mạnh Euler cơ sở b là số giả nguyên tố Euler cơ sở b 
 d) Số giả nguyên tố Euler cơ sở b là số giả nguyên tố mạnh cơ sở b 
Điểm; a b c d 
 5 -3 5 -3 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
4. Giả sử k là số các số nguyên d−ơng b≤2000, nguyên tố cùng nhau với 2001 sao cho 
2001 là giả nguyên tố mạnh Euler cơ sở b. Khi đó 
 a) k≤650 b) 650≤k≤750 c) 750<k≤850 
 d)850<k 
Điểm; a b c d 
 10 0 0 0 
5. Giả sử n là hợp số lẻ, b là số nguyên chọn ngẫu nhiên trong các số từ 1 đến n-1. Gọi p 
là xác xuất để n giả nguyên tố Euler cơ sở b. Khi đó 
a) 1≥ p≥3/4 b) 3/4>p≥2/3 c) 2/3>p≥1/2 d)1/2>p≥0 
Điểm; a b c d 
 0 0 0 10 
Ch−ơng 5 
 118
1. Trong những tập hợp số sau đây, những tập nào lập thành một tr−ờng (với các phép 
toán thông th−ờng) 
 a) tập hợp các số dạng 
a
1007

 , trong đó a nguyên 
 b) tập hợp các số hữu tỷ 
 c) tập hợp các số thực 
 d) tập hợp các số dạng 
a
b

 trong đó a chẵn, b lẻ 
Điểm; a b c d 
 -10 5 5 -8 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
2. Tồn tại các tr−ờng có k phần tử, trong đó 
a) k=17 b) k=24 c) k=27 d) k=39 
Điểm; a b c d 
 5 -5 5 -5 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
3. Cho Fq là tr−ờng có q phần tử. Khi đó số phép tính bit cần thiết để nhân (hoặc chia) hai 
phần tử của tr−ờng Fq là: 
a) O(q) b) O(log q) c) O(log2 q) d) O(log3 q) 
Điểm; a b c d 
 0 2 4 10 
4. Cho a(t), b(t), c(t) là các đa thức hệ số phức, nguyên tố cùng nhau từng cặp và 
a(t)+b(t)=c(t). Khi đó 
 a) Bậc của a(t) lớn hơn số các nghiệm phân biệt của đa thức abc. 
 b) Bậc của mỗi đa thức a, b, c đều nhỏ hơn số nghiệm phân biệt của đa thức abc 
 c) Nói chung không thể so sánh bậc của các đa thức a, b, c với số nghiệm phân 
biệt của đa thức tích abc 
 d) Nếu đa thức a(t) có nghiệm bội đủ lớn thì bậc của nó lớn hơn số các nghiệm 
phân biệt của đa thức abc 
 119
Điểm; a b c d 
 0 10 0 0 
5. Cho ph−ơng trình xn+yn=zk. Hãy đánh dấu những tr−ờng hợp mà ph−ơng trình trên có 
thể có nghiệm x, y, z là các đa thức hệ số phức, nguyên tố cùng nhau từng đôi một 
 a) n=1997, m=1998, k=1999 
 b) n=1998, m=1999, k=2000 
 c) n=1, m=1998, k=1999 
 d) n=2, m=1997, k=1998 
Điểm; a b c d 
 -3 -3 5 5 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
Ch−ơng 6 
1. Trong các ma trận cấp 2 sau đây, ma trận nào có thể dùng làm khoá để lập mã khối hai 
chữ (với 24 chữ cái) 
a b
c d
) )
) )
19 12
2 9
24 11
5 6
19 5
22 10
20 10
16 2
















Điểm; a b c d 
 5 5 -5 -5 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
2. Đánh dấu những câu đúng 
 a) Thuật toán lập mã mũ có thời gian mũ 
 b) Thuật toán giải mã mũ có thời gian mũ 
 c) Thuật toán giải mã mũ có thời gian d−ới mũ 
 d) Thuật toán lập mã và giải mã mũ đều có thời gian đa thức 
Điểm; a b c d 
 120
 -10 -5 10 -5 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
3. Đánh dấu những câu đúng 
 a) Trong hệ mật mã khoá công khai, các khoá lập mã và giải mã đều đ−ợc thông 
báo công khai 
 b) Chỉ có khóa lập mã đ−ợc thông báo 
 c) Chỉ có khoá giải mã đ−ợc thông báo 
 d) Thuật toán lập mã th−ờng có thời gian đa thức, thuật toán giải mã th−ờng có 
thời gian mũ hoặc d−ới mũ 
Điểm; a b c d 
 -5 5 -10 5 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
4. Trong các cặp số (e,n) sau đây, những cặp số nào có thể dùng làm khoá lập mã của hệ 
mã mũ 
a) e=8, n=1996 b) e=4, n=3992 c) e=9, n=1996 d) e=5, n=3992 
Điểm; a b c d 
 -5 -5 5 5 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
5. Trong cặp số (e, n) sau đây, những cặp số nào có thể dùng làm khoá lập mã của hệ 
RSA 
a) (27, 1998) b) (27, 1961) c) 27, 2183) d) (31, 3599) 
Điểm; a b c d 
 -3 -3 -3 10 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
Ch−ơng 7 
1. Trong các ph−ơng trình sau đây, ph−ơng trình nào xác định đ−ờng cong elliptic trên 
tr−ờng thực 
 121
a) y2-x3=0 b) y2-x3+x=0 
c) y3-x3+1=0 d) y2-x2+1=0 
Điểm; a b c d 
 0 10 0 0 
2. Trong các ph−ơng trình sau đây, ph−ơng trình nào xác định đ−ờng cong elliptic trên 
tr−ờng F3 
a) y2-x3=0 b) y2-x3+1=0 
c) y2-x4+1=0 d) y2-x3+x+1=0 
Điểm; a b c d 
 0 0 0 10 
3. Cho P là điểm trên đ−ờng cong elliptic E trên tr−ờng hữu hạn Fq. Khi đó 
 a) Nếu k là một số nguyên d−ơng thì thuật toán tìm kP∈E có thời gian mũ 
 b) Nếu k là một số nguyên d−ơng thì thuật toán tìm điểm kP∈E có thời gian đa 
thức 
 c) Biết các điểm P và Q=kP, thuật toán tìm k có thời gian đa thức 
 d) Biết các điểm P và Q=kP, thuật toán tìm k có thời gian mũ 
Điểm; a b c d 
 -5 5 -5 5 
(Nếu đánh dấu nhiều khả năng thì điểm bằng tổng của điểm các khả năng đó) 
4. Để xây dựng mật mã khoá công khai sử dụng đ−ờng cong elliptic, ta cần: đ−ờng cong 
elliptic E t