Lời cảm ơn
Trước tiên, em xin gửi lời cảm ơn sâu sắc nhất đến hai thầy Phạm Bảo Sơn, thầy
Nguyễn Phương Thái đã không quản vất vả hướng dẫn em trong suốt thời gian làm
khóa luận tốt nghiệp vừa qua.Em cũng chân thành cảm ơn mọi người ở phòng HMI lab
đặc biệt là hai anh Nguyễn Quốc Đại và Nguyễn Quốc Đạt đã luôn chỉ bảo mỗi khi em
có những vấn đề vướng mắc.
Em xin bày tỏ lời cảm ơn sâu sắc đến các thầy cô giáo trong Trường Đại Học Công
Nghệ đã tận tình dạy dỗ em suốt bốn năm học qua.
Con xin cảm ơn bố, mẹ và gia đình đã luôn bên con, cho con động lực để làm việc tốt
hơn. Cảm ơn tất cả bạn bè đã luôn sát cánh cùng tôi.
Hà Nội, ngày 20 tháng 5 năm 2011
Ma Trọng Khôi
ĐẠI HỌC CÔNG NGHỆ
ĐẠI HỌC QUỐC GIA HÀ NỘI

TÍNH LŨY THỪA VỚI SỐ MŨ LỚN THEO MODULO
BÁO CÁO MÔN HỌC MẬT MÃ VÀ AN TOÀN DỮ LIỆU
Giảng viên : PGS.TS. Trịnh Nhật Tiến
Học viên : Ma Trọng Khôi

Hà Nội – 2014
Mục lục
2
Chương 1
Giới Thiệu
Yêu cầu của bài toán tính lũy thừa với số mũ lớn theo phép tính modulo là làm sao
tính được phần dư của phép chia a
d
cho N một cách nhanh nhất, với a, d, N là các số tự
nhiên lớn, có thể có hàng trăm chữ số.
a

sẽ bằng:
Ta thấy để tính a
d

thì chỉ cần quan tâm đến các trường hợp β
i
= 1, 0 ≤ i ≤ log
2
(d).
Ví dụ: tính c = a
169
Ta có thể tính được kết quả theo bảng trên, c sẽ bằng a
1
* a
8
* a
32
* a
128
. Số phép nhân
cần thực hiện là 7 (tính a
128
) + 3 (các phép nhân a
1
, a
8
, a
32
, a
128

Cũng tương tự phương pháp nhị phân, nhưng ta biểu diễn số d ở dạng cơ số khác:
Phương pháp này sẽ hiệu quả và tối ưu khi ta chọn m = 2
k
(k є N, k > 0)
Ví dụ: với d = 250, và ta chọn k = 2, m = 4. Khi đó:
d = 250 = 11 11 10 10
Giá trị k = 2 có ý nghĩa khi biểu diễn d ở dạng nhị phân thuật toán sẽ quét lần lượt 2 số
trên mỗi vòng lặp (với phương pháp nhị phân là quét 1 số với mỗi vòng lặp).
Đầu tiên thuật toán sẽ phải tính trước các phần dư của a
0
, a
1
,…, a
m-1
cho N. Như
ví dụ trên ta cần tính a
0
, a
1
, a
2
, a
3
.
5
Sau đấy ta thực hiện vòng lặp quét qua chuỗi nhị phân của d từ trái qua phải (ta
cũng có thể quét theo chiều ngược lại nhưng sẽ cần thêm một biến nhớ nữa khi viết
chương trình), mỗi vòng lặp ta lấy ra hai bit của d. Với ví dụ này ta sẽ cần 4 vòng lặp
và các phép tính cần thực hiện được mô tả như bảng sau
Số phép nhân cần thực hiện là: 2 (tính a

3.2 Cửa sổ trượt có kích thước không cố định
Phương pháp này cũng có hai loại cửa sổ, loại 1 là cửa sổ chỉ có bit 0, và cửa sổ có
chứa bit khác 0. Hai loại cửa sổ này sẽ được nhận biết theo quy tắc sau:
Cho trước hai số tự nhiên w và q > 0
• Các cửa sổ chỉ chứa bit 0 phải có độ dài tối thiểu lớn hơn q
• Các cửa sổ có chứa bit 1 phải có độ dài không vượt quá w
Ví dụ: với w = 5 và q = 2, d = 11173. Các cửa sổ xác định được: 101 0 11101 00 101
Để đoán nhận được các cửa sổ ta có thể dụng Automat được thiết kế như sau:
7
4. Thuật toán cây lũy thừa
Trước khi trình bày vào thuật toán ta sẽ tìm hiểu về chuỗi cộng trước, các tính chất của
chuỗi cộng là cơ sở cho thuật toán cây lũy thừa
4.1 Chuỗi cộng
Chuỗi cộng là một chuỗi số tự nhiên a
0
, a
1
,…, a
n
. Chuỗi số này có hai tính chất:
• a
0
= 1
• Với một số tự nhiên k ≤ n bất kỳ, ta luôn tìm được hai số tự nhiên i, j: 0 ≤ i,j ≤ n
sao cho a
k
= a
i
+ a
j

23
= a
7
* a
16
. Ta có thể thấy
các lũy thừa của chuỗi số này chính là một chuỗi cộng: 1, 2, 3, 4, 7, 8, 16, 23, 32, 55.
Các phương pháp m-ary, cửa sổ trượt về cơ bản cũng là tìm một chuỗi cộng
tương ứng với a
n
= d. Và người ta đã chứng minh được rằng bài toán tìm một chuỗi
cộng ngắn nhất sao cho a
n
= d là một bài toán NP.
4.2 Cây lũy thừa
Phương pháp cây lũy thừa [4] sẽ xây dựng chuỗi cộng trước bằng cách xây dựng
một cây lũy thừa có tính chất của chuỗi cộng. Sau đó thứ tự các phép nhân sẽ được
thực hiện giựa theo cây này. Cây lũy thừa được xây dựng theo quy tắc sau:
• Giả sử đã xây dựng được cây có độ cao là k (ta luôn có thể dựng được cây có
độ cao là 1 với nút gốc bằng 1)
8
• Ta sẽ xây dựng các nút có độ cao là k+1. Bằng cách ta xét các nút ở độ cao k,
giả sử ta có nút e
i
có độ cao k. thực hiện phép cộng e
i
với các nút e
j
(j ≤ i) đang
có trên cây. Nếu tổng của chúng chưa có trên cây thì ta tạo nút con mới của e

= a
5
* a
5
, a
13
= a
10
* a
3
, a
26
=
a
13
* a
13
9
Chương 3
Thực Nghiệm
Nội dung chương sẽ trình bày về chương trình tính lũy thừa với số mũ lớn theo
modulo.
Mã nguồn của chương trình được viết bằng Java sử dụng thuật toán nhị phân và
đã được đóng gói vào file ExponentialModulo.jar. Để thực thi được chương trình này
thì có các yêu cầu sau.
Yêu cầu:
• Máy tính đã phải được cài đặt JRE
(http://www.oracle.com/technetwork/java/javase/downloads/jre7-downloads-
1880261.html).
Input:

14
Tài Liệu Tham Khảo
[1] http://en.wikipedia.org/wiki/RSA_(cryptosystem)
[2] Hans Riesel, “Prime Numbers and Computer Methods for Factorization”, P83-
94, ISBN 978-0-8176-8297-2, Springer New York Dordrecht Heidelberg London.
[3] http://en.wikipedia.org/wiki/Exponentiation_by_squaring
[4] Donald E. Knuth. “The Art Of Computer Programming Vol. 3”.
15