CHƯƠNG 2
GIỚI THIỆU VỀ LÝ THUYẾT SỐ
Hầu hết các thuật toán mật mã khóa công khai được xây dựng dựa trên các khái niệm của lý thuyết
số. Trong chương này sẽ trình bày ngắn gọn những kiến thức cơ bản về lý thuyết số, nó là công cụ hữu
ích để hiểu sâu một thuật toán mật mã nào đó.
2.1 Các số nguyên tố và các số nguyên tố cùng nhau
2.1.1 Các ước số
Nói rằng, b (một số khác 0) là ước số của a nếu a = mb, với một giá trị m nào đó, ở đây a, b, m là các
số nguyên. Như vậy, b là ước số của a, nếu như chia a cho b không còn lại số dư. Để kí hiệu b là ước số
của a thường sử dụng cách viết ba.
Có các quan hệ sau:
o Nếu a1, thì a = ± 1.
o Nếu ba và ab, thì a = ± b.
o Số b bất kỳ khác 0 là ước số của 0.
o Nếu bg và bh, thì b(mg + nh) đối với bất kì số nguyên m, n.
Để chứng minh khẳng định cuối cùng, cần chú ý như sau:
nếu bg thì g có dạng g = b * g
1
, đối với số nguyên g
1
nào đó,
nếu bh thì h có dạng h = b * h
1
, đối với giá trị nguyên h
1
nào đó,
Vì vậy: mg + nh = mbg
1
+ nbh
1
= b * (mg

> 0.
Ví dụ 2.3: 91 = 7 * 13; 11011 = 7 * 11
2
* 13.
Nếu P là kí hiệu tập hợp tất cả các số nguyên tố, thì đối với một số nguyên dương bất kì được viết
duy nhất dưới dạng:
,
∏
=
P
a
p
pa
ở đây tất cả các a
p
≥ 0
1

Trong công thức này, biểu thức ở vế phải sau dấu bằng, ký hiệu tích theo tất cả khả năng của các số
nguyên tố p. Đối với mỗi giá trị cụ thể của a thì giá trị lớn nhất của chỉ số a
p
sẽ bằng 0.
Ví dụ 2.4: 3600 = 2
4
* 3
2
* 5
2
.
Các giá trị của một số nguyên dương bất kỳ có thể liệt kê dưới một dạng đơn giản của tất cả các chỉ

Bổ đề: Một số nguyên dương bất kì dạng p
k
chỉ có thể chia hết cho một số nguyên, khi số bị chia có
bậc của số nguyên tố p với chỉ số không vượt hơn k, nghĩa là số p
j
với j ≤ k. Như vậy:
ab → a
p
≤ b
p
, đối với tất cả p.
Ví dụ 2.7: a = 12 , b = 36 , 1236, 12 = 2
2
* 3, 36 = 2
2
* 3
2
a
2
= 2 = b
2
,
a
3
= 1 ≤ 2 = b
3
.
2.1.3 Các số nguyên tố cùng nhau
Chúng ta sẽ sử dụng ký hiệu gcd( a, b) để chỉ ước số chung lớn nhất (UCLN) của số a và b. Nói rằng,
một số nguyên dương c là UCLN của a và b, nếu:

Trong trường hợp chung:
2
k = gcd(a, b) → k
p
= min (a
p
, b
p
), đối với tất cả các p.
Việc xác định các thừa số nguyên tố của các số lớn là bài toán không đơn giản, bởi vì rằng các trình
bày ở trên không cho một khả năng thực tiễn để tính UCLN của hai số.
Các số nguyên a và b là nguyên tố cùng nhau, nếu chúng không có ước số nguyên tố chung, hay ước
số chung duy nhất của chúng là 1. Nói một cách khác a và b là hai số nguyên tố cùng nhau nếu gcd(a, b)
= 1.
Ví dụ 2.10: Số 8 và số 15 là các số nguyên tố cùng nhau, bởi vì ước số của 8 là 1, 2, 4 và 8, còn các
ước số của 15 là 1, 3, 5 và 15. Như vậy, 1 là ước số chung duy nhất của hai số này.
2.1.4 Số học trong lớp số dư
Đối với bất kỳ một số nguyên dương n và một số nguyên a bất kỳ, khi chia a cho n, ta nhận được một
số nguyên q nào đó và số dư r, phù hợp với quan hệ sau:
a = qn + r, 0 ≤ r < n, q = a / n.
ở đây x ký hiệu số nguyên lớn nhất, không lớn hơn x.
Đối với một số dương a và một số nguyên dương n, luôn luôn có thể tìm được q và r, phù hợp với
quan hệ tính toán trên.
Ví dụ 2.11: a = 11; n = 7; 11 = 1 * 7 + 4; r = 4.
Nếu a là một số nguyên, còn n là một số nguyên dương, thì a mod n, được xác định như phần dư của
phép chia a cho n. Như vậy, đối với một số nguyên a bất kỳ có thể viết :
a = a / n * n + (a mod n)
Ví dụ 2.12: 11 mod 7 = 4 ; –11 mod 7 = 3.
2.2 Lý thuyết về đồng dư
Định nghĩa 2.1 (Đồng dư)

nba mod≡
khi và chỉ khi
nbna modmod =
.
Chúng ta đi tìm hiểu một số tính chất quan trọng của đồng dư.
Tính chất 2.1: Nếu
nba mod
11
≡
và
nba mod
22
≡
thì
nbbaa mod
2121
+≡+

Chứng minh: Từ giả thuyết ta có
111
bnta +=
và
222
bnta
+=
, suy ra
nttbbaa )(
212121
+++=+
,

2121
≡
Tính chất 2.3: Nếu như
dbbdaanband
11
,,mod,1),gcd( ==≡=
, thì
nba mod
11
≡
Chứng minh: Từ giả thuyết ta có
ndba |)(
11
−
, mà
1),gcd( =nd
, nên suy ra
nba |)(
11
−
, hay
nba mod
11
≡
.
Ví dụ 2.13: Chứng minh rằng 37
n+2
+16
n+1
+23

n
≡
, và từ tính chất 2.3 suy ra điều phải chứng minh.
2.3 Các số nguyên modulo n
Các số nguyên modulo n (ký hiệu
n
Z
) là tập hợp các số nguyên
{ }
1 ,,1,0 −n
bao gồm 2 phép toán
cộng và nhân. Việc cộng và nhân trong
n
Z
được thực hiện giống như cộng và nhân các số nguyên, ngoại
trừ một điểm là các kết quả sẽ được rút gọn theo modulo n.
Ví dụ 2.14: Tính
13*11
trong
16
Z
. Tương tự như với các số nguyên ta có
14313*11 =
. Để rút gọn
143 theo modulo 16, ta thực hiện phép chia bình thường:
15168143 +×=
, bởi vậy
1516mod143 =
. Do
đó

Za ∈
là m – a, nghĩa là a + (m – a) =
(m – a) + a = 0 với bất kì
n
Za ∈
.
o Phép nhân là đóng, tức với bất kì
n
Zba ∈,
,
n
Zba ∈*
.
o Phép nhân là giao hoán, nghĩa là với bất kì
n
Zba ∈,
,
abba ** =
.
o Phép nhân là kết hợp, nghĩa là với
n
Zcba ∈,,
,
)*(**)*( cbacba =
.
o 1 là phần tử đơn vị của phép nhân, tức là với bất kì
n
Za ∈
:
aaa == *11*

3. Nếu như p và q là hai số nguyên tố cùng nhau thì
)(*)()( qppq
φφφ
=
4.
)1()(
1
−=
−
ppp
ss
φ
5. Nếu như
k
e
k
ee
pppn
21
21
=
, ở đây
1
p
,
2
p
, …,
k
p

pp
nn
1
1
1
1
1
1)(
21
φ
Trên bảng 2.1 trình bày 30 giá trị đầu tiên của
)(n
φ
. Giá trị
φ
(1) là không xác định, nhưng coi rằng
nó bằng 1.
Bảng 2.1: Một số giá trị của hàm Euler
)(n
φ
n
φ
(n)
n
φ
(n)
n
φ
(n)
1 1 11 10 21 12

= 1024 ≡ 1 mod 11.
Chứng minh: Giả sử
)(1
,,
n
xx
φ
– là các số tự nhiên khác nhau, nhỏ hơn n và nguyên tố cùng nhau
với n.
Hãy xét tất cả các khả năng của tích
ax
i
, với
)(,1 ni
φ
∈
. Bởi vì a nguyên tố cùng nhau với n và
i
x
nguyên tố cùng nhau với n, nên tích
ax
i
cũng nguyên tố cùng nhau với n, do đó có
nxax
ji
mod≡
.
5
Chú ý rằng các phần dư của phép chia
ax

φ
là các cặp khác nhau theo modulo n.
Hãy nhân tất cả đẳng thức
nxax
ji
mod≡
, thì thu được:
nxxaxx
n
n
n
mod
)(1
)(
)(1
φ
φ
φ
≡
Hay
naxx
n
n
mod0)1(
)(
)(1
≡−
φ
φ
Bởi vì số

.
Chứng minh: Ta có
1)( −= pp
φ
, áp dụng định lý Euler ta có điều phải chứng minh.
Từ định lý Fermat chúng ta có các hệ quả quan trọng sau:
1. Cho
Za ∈
, p là số nguyên tố, thì ta có:
paa
p
mod≡
2. Cho
Zba ∈,
, p là số nguyên tố
pbaba
nnn
mod)( +≡+
Ví dụ 2.16: Chứng mình rằng 1
18
+2
18
+3
18
+4
18
+5
18
+6
18

18
+3
18
+4
18
+5
18
+6
18
7mod17mod6 −=≡
2.5 Thuật toán Euclide và thuật toán Euclide mở rộng
2.5.1 Thuật toán Euclide
Định lý Euclide: Cho
0,, ≠∈ bZba
, tồn tại duy nhất cặp giá trị (q, r) với
Zq∈
và
Nr ∈
thỏa mãn:
rbqa +=
,
br <≤0
.
ở đây r gọi là số dư.
Có một số ký hiệu cho số dư như sau:
)(aRr
b
=
,
ar =

ZiaRibaR
bb
∈∀=+ ),()(
, bởi vì
rbiqiba ++=+ )(
.
Nếu như r = 0 thì ta nói a chia hết cho b, ký hiệu là
ba
.
Định lý 2.1: Đối với bất kỳ các số
Ziba ∈,,
:
),gcd(),gcd( bibaba +=
.
Chứng minh: Nếu như
da
và
db
, thì
dqbdqa
21
, ==
. Lúc này
)(
21
iqqdiba +=+
⇒
diba )( +
.
Có nghĩa là:

Bởi vì
)(aRbqa
b
+=
,
)),(gcd(),gcd(),gcd( baRbqbaba
b
=−=
.
Từ định lý 2.2 ta có thuật toán Euclide. Đây là thuật toán giúp tìm UCLN của hai số nguyên dương a
0
và a
1
với a
0
> a
1
.
Thuật toán được miêu tả bằng dãy các phép chia như sau:
,
2110
aqaa +=
0 < a
2
< a
1
,
3221
aqaa +=
0 < a

.
Ví dụ 2.17 (Thuật toán Euclide): Tìm gcd(814, 187).
Giải: Khai triển dãy phép tính theo thuật toán Euclide:
814 = 4 * 187 + 66
187 = 2 * 66 + 55
66 = 1 * 55 + 11
7
55 = 5 * 11 + 0
Vậy gcd(814, 187) = 11.
Thuật toán có thể viết như sau:
Vào: Hai số nguyên dương a và b với a > b
Ra: UCLN của a và b
(1) While b # 0 do
r ← a mod b, a ← b, b ← r
(2) Return (a).
2.5.2 Thuật toán Euclide mở rộng
Định nghĩa 2.3 (Phần tử nghịch đảo)
Cho
n
Za∈
. Phần tử nghịch đảo của a là phần tử
n
Zb ∈
sao cho
nabba mod1** ≡≡
. Kí hiệu
phần tử nghịch đảo của a là a
-1
.
Định lý 2.2: Cho số nguyên a > 0 nguyên tố cùng nhau với n, thì luôn tồn tại phần tử nghịch đảo của

,
3221
aqaa +=
0 < a
3
< a
2
…
,
112 kkkk
aqaa +=
−−−
0 < a
k
< a
k-1
Ta dễ dàng rút ra dãy sau:
112 −−−
−=
kkkk
aqaa
mà
2231 −−−−
−=
kkkk
aqaa
nên suy ra
)(
22312 −−−−−
−−=

66 = 1 * 55 + 11
55 = 5 * 11 + 0
Suy ra: 11 = 66 – 1 * 55 = 66 – 1 * (187 – 2 * 66) = 3 * 66 – 1 * 187 = 3 * (814 – 4 * 187) –187 = 3 *
814 – 13 * 187. Vậy x = 3 và y = –13.
2. Tìm phần tử nghịch đảo của 17 theo modulo 74.
Giải: Theo ví dụ trên ta có được 3 * 74 – 13 * 17 = 1. Nên phần tử nghich đảo của 17 là –13,
nhưng chỉ lấy số dương, nên phần tử nghịch đảo của 17 là 74 – 13 = 61.
2.6 Giải phương trình đồng dư trong nhóm thương
n
Z
Có nhiều phương pháp giải phương trình đồng dư, nhưng chúng tôi muốn trình bày với bạn đọc một
phương pháp khá hay dựa vào định lý sau:
Định lý 2.3: Cho n > 1, gcd(a, n) = 1. Khi đó phương trình đồng dư
nbax mod≡
có nghiệm duy
nhất, và nghiệm đó là:
nbax
n
mod
1)( −
=
φ
Chứng minh: Theo định lý Euler, ta có
na
n
mod1
)(
≡
φ
, suy ra

Chúng ta đã biết định lý về phần tử nghịch đảo, nếu như gcd(a, n) = 1, thì luôn tồn tại phần tử nghịch
đảo a
-1
. Nên từ phương trình
nbax mod≡
, suy ra
.mod
1
nbax
−
≡
Ví dụ 2.20: Giải phương trình
10mod37 ≡x
.
Chúng ta thấy
310mod7
1
=
−
. Nên nghiệm của phương trình x = 3 * 3 mod 10 = 9.
Định lý 2.4: Cho n >1, để phương trình
nbax mod≡
có nghiệm thì điều kiện cần và đủ là gcd(a, n)|
b.
Chứng minh: Phương trình
nbax mod≡
có thể viết dưới dạng phương trình tuyến tính sau
ax + kn = b, (2.2),
k là số nguyên.
Ta chứng minh điều kiện cần. Giả sử hoàn thành điều kiện (2.2). Bời vì số gcd(a, n) là ước của vế

này là không thể.
2. Giải phương trình
36mod186 ≡x
. Vì gcd(6, 36)|18. Nên phương trình này có 6 nghiệm: 3, 9,
15, 21, 27 và 33.
2.7 Định lý phần dư Trung Hoa.
Định lý này nhằm giúp chúng ta giải hệ phương trình đồng dư thức, định lý phát biểu như sau:
Giả sử cho các số n
1
, n
2
, …, n
k
là các số nguyên dương nguyên tố cùng nhau từng đôi một và c
1
, c
2
,
…, c
k
là các số nguyên khi đó hệ phương trình đồng dư:
11
mod ncx ≡
22
mod ncx ≡
…
kk
ncx mod≡
Có nghiệm duy nhất theo modulo n và nghiệm đó là:
∑

=
=
−
k
i
iiii
nNNcx
1
1
0
)mod(
thì coi như chúng ta đã chứng minh được định lý trên.
Ta có N
i
chia hết cho n
s
, khi s
≠
i. Điều này dẫn đến
)(mod)mod(
1
0 iiiii
ncnNNx
−
≡
, từ đó
)(mod
0 ii
ncx ≡
. Điều này có nghĩa hệ trên tương đương với hệ sau:

Ta đi tính phần tử nghịch đảo của N
i
theo modulo n
i

143
-1
mod 7 = 5; 91
-1
mod 11 = 4 và 77
-1
mod 13 = 12.
Áp dụng công thức (2.4) ta có được nghiệm của hệ phương trình là:
x = (5.143.5 + 3.91.4 + 10.77.12) mod 1001 = 894.
2.8 Bậc và căn nguyên thủy
Định nghĩa 2.4 (Bậc)
Cho gcd(a, n) = 1. Bậc a mod n là số nguyên dương nhỏ nhất
γ
thỏa mãn phương trình đồng dư
thức:
na mod1≡
γ
,
Kí hiệu bậc là Ord
n
(a).
Ví dụ 2.23: Tìm bậc của 2 mod 5
Giải: 2
1
mod 5 = 2; 2

Z
tồn tại số x, thỏa mãn điều kiện
nax mod
2
≡
, trường hợp ngược lại gọi là không thặng dư bậc hai.
Tập hợp các số thặng dư bậc hai theo modulo n ký hiệu QR
n
, tập hợp không thặng dư bậc hai ký hiệu là
QNR
n
.
Ví dụ 2.25: Tính QR
11
là tập tất thặng dư bậc hai theo modulo 11.
11
Chúng ta có
{ }
{ }
9,5,4,3,111mod10,9,8,7,6,5,4,3,2,1
2222222222
11
==QR
, trong ví dụ, chúng ta
tính QR
11
bằng cách lựa chọn các phần tử của nhóm
*
11
Z

p
QRpxpxS ⊆−≤<= 2/)1(0|)(mod
2
. Để chứng minh
SQR
p
=
, điều này sẽ đúng nếu như chúng ta
chứng minh được rằng
SQR
p
⊆
.
Chọn một số a bất kỳ
p
QRa ∈
. Tồn tại số x < p, thỏa mãn điều kiện
)(mod
2
pax ≡
. Nếu như
2/)1( −≤ px
, thì
Sa∈
. Giả sử rằng x > (p – 1)/2. Như thế
2/)1( −≤−= pxpy
và
)(mod2)(
22222
paxxpxpxpy ≡≡+−≡−≡

, nên điều khẳng định thứ hai hoàn toàn đúng.
Thường xuất hiện bài toán, xác định xem số n có phải là thặng dư bậc hai theo modulo đã cho hay
không. Vấn đề này gọi là bài toán về thặng dư bậc hai. Bài toán này được giải quyết thông qua định lý
sau:
Định lý 2.6 (Tiêu chuẩn Euler): Cho p là số nguyên tố. Đối với bất kỳ số
*
p
Zx∈
, x là thặng dư bậc
hai khi và chi khi thỏa mãn điều kiện sau:
px
p
mod1
2/)1(
≡
−
.
Chứng minh: Đối với
p
QRx ∈
thì tồn tại số
*
p
Zy ∈
sao cho
)(mod
2
pxy ≡
. Theo định lý Fermat
chúng ta có,

. Hay nói cách khác, mỗi phần tử khác không của trường là nghiệm của đa thức:
12
.mod0)1)(1(1
2/)1(2/)1(1
pyyy
ppp
≡+−≡−
−−−
Mà tất cả các nghiệm này phải khác nhau, bởi vì đa thức có bậc p – 1. Điều này dẫn đến (p – 1)/2
nghiệm của đa thức
py
p
mod01
2/)1(
≡−
−
phải khác nhau. Mà theo định lý về số phần tử của tập thặng
dư bậc hai ta có tập QR
p
có (p – 1)/2 phần tử, mỗi phần tử là nghiệm của phương trình
py
p
mod01
2/)1(
≡−
−
. Và bất kỳ phần tử nào khác của nhóm
*
p
Z








p
a
được xác định như sau:
o 0 nếu a|p;
o 1 nếu
p
QRa ∈
;
o −1 nếu
p
QNRa ∈
Các tính chất của ký hiệu Legendre:
Cho p là một số nguyên tố lẻ và a, b ∈ Z. Khi đó ký hiệu Legendre có các tính chất sau:
1.











=








p
b
p
a

3.
1
1
=








p
4.


≡
=−=








−
8mod5,31
8mod7,11
)1(
2
8
1
2
pkhi
pkhi
p
p
6.



≡−
≡
=−=


≡
=−=














−
5mod3,21
5mod4,11
)1(
5
5
2
pkhi
pkhi
p
p
8.



2
1
2
1
)1(
−−
−








=








pq
q
p
p
q


3
1
23
3
7
2
5
1
3
1
23
9
7
2
5
1
3
1
23
331
1
7
331
1
5
331
1
3
331
1



















−=




















−=






−






−






−


=


















=










k
k
p
a
p
a
p
a
n
a
α
αα



















a

14
3.
( )
1,gcd0 ≠=






nakhi
n
a
4.












≡



n
b
m
a
mn
a
, điều này dẫn tới






2
n
a
là 0 hoặc 1.
6. Nếu
nba mod≡
, thì






=






−
−
4mod31
4mod11
)1(
1
2
1
nkhi
nkhi
n
n
9.



≡−
≡
=−=






−
8mod5,31

1
9
1
9
37
37
9
37
2
37
36
37
147
147
37
147
331
331
147
331
147
331
2
.1
331
294
331
37035
2
=




=






=






=






=






+ Khác với ký hiệu Legendre, ký hiệu Jacobi không cho biết liệu a có phải là một thặng dư bậc hai
theo modulo n hay không. Sự thực nếu a ∈ QR
n
thì
1=






n
a
. Tuy nhiên
1=






n
a
thì không có nghĩa là a ∈
QR
n
.
+ Tính chất thứ hai không thể mở rộng gắn với đồng dư thức Euler
pa
p

với ít nhất một nửa của các a mod n khi n là hợp số.
2.10.3 Bổ đề Gauss
Nếu như p và q là 2 số nguyên tố khác 2 thì:
15
2
1
2
1
)1(
−−
−








=








pq
q

. Bây giờ xác định tổng Gauss:
∑








=
∈
q
Zx
x
w
q
x
y
Chúng ta sẽ chứng minh 2 điều khẳng định sau:
Điều khẳng định 1: Ta có đẳng thức sau
qy
q
2
1
2
)1(
−
−=
.

q
xz
y
,
2
)(
Từ tổng cuối cùng x lấy giá trị trong tập
{ }
0\
q
Z
. Khi
0≠x
, có:








−
−=







x
q
xux
q
1
2
1
12
1
)1(
1)(
.
Từ đây
∑
=−
∈
−
q
Zu
u
u
q
wCy
2
2
1
)1(
,
với
{ }






=
∈ 0\
0
1
1
q
Zx
q
q
C
.
Nếu như
0≠u
, thì
1
1
−
−= uxs
nhận các giá trị trong tập
{ }
1\
q
Z
, cho nên:


C
q
Zs
u
11
,
16
Bởi vì
0
0
=








p
, còn trong
{ }
0\
q
Z
số lượng phần tử là bình phương và số lượng phần tử không là
chính phương là như nhau. Từ đây:
{ }
qwqwC
qq

∑ ∑








=








=








=










−=








−==








−−
−
−
−
p

4
1+
=
,
Bởi vì theo tiêu chuẩn Euler,
pa
p
mod1
2/)1(
≡
−
, nên
paaaax
pp
mod
2/)1(2/)1(2
≡≡≡
−+
. Như vậy số
x là căn bậc hai của a theo modulo p.
Phương án 2:
8mod5≡p
Trường hợp này thì p + 3 chia hết cho 8. Bởi vì số (p – 1)/2 là số chẵn, số –1 thỏa mãn tiêu chuẩn
Euler và là thặng dư bậc hai. Cho
p
QRa ∈
, ta định nghĩa x như sau:
)(mod
8
3

giải quyết xong, nếu số âm thì:
)(mod)1(
22
paxx ≡−≡−
Dẫn đến
)(mod1
8
3
pax
p+
−=
là số cần tìm. Như vậy bài toán dẫn đến tìm
pmod1−
.
17
Cho số b là số không thặng dư bậc hai theo modulo p. Như vậy theo tiêu chuẩn Euler ta có
pbb
pp
mod1)(
2/)1(24/)1(
−≡≡
−−
, như vậy có thể thay
pmod1−
bằng
pb
b
mod
4/)1( −
. Bởi vì

2
1
−≡
−
.
Giả sử
lp
s
21 =−
, l là số lẻ. Chúng ta sẽ tìm dãy số
01
,, bb
s−
sao cho:
pba
i
i
l
mod1)(
22
≡
.
Có thể đặt
1
1
=
−s
b
. Nếu như
i

. Cuối cùng ta có
pba
l
mod1
2
0
≡
, từ đây
paba
l
mod)(
2
0
2
1
≡
+
, có nghĩa là:
pbax
l
mod
0
2
1+
±≡
.
2.11.2 Tính căn bậc hai theo modulo là hợp số
Chúng ta biết rằng
pqn =
, p và q là số nguyên tố, nhóm

1−
=
qqpv
q
).(mod
1−
=

18
2.12 Thuật toán bình phương và nhân
Thuật toán “bình phương và nhân” để tính
nxz
b
mod=
. Đây là thuật toán tính hàm mũ hiệu quả,
mà trong các chương tiếp theo chúng ta sẽ áp dụng nó để tính giá trị hàm mũ đối với trường hợp số mũ
lớn.
Trong thuật toán này, ta coi rằng số mũ b được biểu thị ở dạng nhị phân như sau:
∑
=
=
l
i
i
i
bb
0
2
Trong đó b
i

6
+2
3
+2
2
+1 = 110111001101
z = 1
i b
i
z mod 11413
11 1 1
2
* 9726 = 9726
10 1 9726
2
* 9726 = 2659
9 0 2659
2
= 5634
8 1 5634
2
* 9726 = 9167
7 1 9167
2
* 9726 = 4958
6 1 4958
2
* 9726 = 7783
5 0 7783
2