Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
**************** VŨ THỊ THANH HẬU

MỘT SỐ ỨNG DỤNG CỦA SỐ HỌC
TRONG LÝ THUYẾT MẬT MÃ
LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học : GS.TSKH. Hà Huy Khoái

Thái Nguyên, năm 2009 ụ ụ
ờ ó
ột số ế tứ
t t ộ ứ t ủ tt t
ệ
ộ ứ t ủ tt t
Pé tí ồ ề q
ố tố ị ý ủ số ọ
t t ở rộ
P r
Pé tí ồ trì ồ
ị ý rt ở rộ
í t ớ ồ ủ ỹ từ ớ
ì ý ệ r
P số tụ
ệ
í t
ột số ứ ụ ủ số ọ tr ý tết t
t ột số ệ
ệ sr
ệ ố
ột số ệ ũ t ụ

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn
ờ ó
rớ ữ 70 ủ tế ỷ ố ọ tờ ợ ột
tr ữ t ọ t tý ỉ ó ý ĩ ý tết ố tợ
ứ ủ ố ọ q t tr t ợ số tết ớ tồ t
tr ố ọ tết số tố í ó ữ t
ọ r ẹ ủ ố ọ ó ợ ờ sự rờ tự tễ ủ ó t
ó ủ r tts
tt ó ồ ý ớ r ẹ ủ ố ọ
ỉ tể ệ tr ý ĩ t tý ủ ó tr ữ ứ ụ
t ờ tự tễ ó ó tể ì ợ
r ột số ết q ý tết số tr ố ọ ột ộ
tr t t t sở ủ ữ ứ ụ ó í ố
ọ tt t ĩ ự ứ tt t tr ố ọ
ó tể ó t ó từ tờ ổ ờ t ụ t
ột ó ệ tố ể í t t t q sự q sự
t t ủ ờ ổ s sr ệ ổ t ệ
sr t q é t tế ỗ ý tự t ở ý tự ứ s
ó ị trí ị trí
ữ tế ỷ ệ ớ ó tí t ợ
t ệ ớ sự r ờ ủ ệ rts Pr ó ố
t q é t tế t ì s ớ q trì t trể ủ
ị sử ề t t t tr ề ĩ ự tú
ệ ớ r ờ ó tí t ệ ũ ủ P
tế t tứ tr ổ ì ủ
s ữ ệ ột ét ủ ệ tr

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn
❝❤♦ ♣❤Ð♣ ❝➠♥❣ ❜è ❝➠♥❣ ❦❤❛✐ ♠ét ♣❤➬♥ t❤➠♥❣ t✐♥ ❝❤♦ ✈✐Ö❝ ❧❐♣ ♠➲ ❣ä✐ ❧➭ ♠➲
❤♦➳ ✈í✐ ❦❤♦➳ ❝➠♥❣ ❦❤❛✐✱ ♠ét ♠➠ ❤×♥❤ ❤♦➭♥ ❤➯♦ ❝❤♦ ❤Ö ♠➲ ❦✐Ó✉ ♥➭② ➤➢î❝

X[1], X[2], ..., X[n]✳ ❚×♠ m ✈➭ j s❛♦ ❝❤♦ j ❧➭ sè ❧í♥ ♥❤✃t t❤♦➯ ♠➲♥✿
m = X[j] = max
1≤k≤n
X[k]✳
❇➭✐ t♦➳♥ ♥➭② ❝ò♥❣ ❝ã ♥❣❤Ü❛ ❧➭ t×♠ ❝ù❝ ➤➵✐ ❝ñ❛ ❝➳❝ sè ➤➲ ❝❤♦ ✈➭ t×♠ ❝❤Ø sè
❧í♥ ♥❤✃t tr♦♥❣ ❝➳❝ sè ➤➵t ❝ù❝ ➤➵✐✳ ❱× ❝➬♥ t×♠ ❝❤Ø sè ❧í♥ ♥❤✃t tr♦♥❣ ❝➳❝ sè
✺
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
t ự t t t từ trị X[n] r ớ tứ t t t tờ
m = X[n] j = n ế t t s s X[n] X[n 1] r
trờ ợ n 1 = 0 tứ n = 1 tt t ết tú ế X[n 1] X[n]
t ể s s s X[n] ớ X[n 2] r trờ ợ ợ
X[n 1] í số ự tr số ét số X[n] X[n 1]
ó t t ổ m = X[n 1] j = n 1 ớ tr
t ợ số ự tr ữ số ét ũ ợ ỉ
số ớ t j tr ỉ số ủ số t ự ó ớ tế t ó
s s ó ớ số ứ trớ ữ số ét ết tú tt t
tr trờ ợ ò số ứ trớ ó
ờ t ó tể tt t tr s
t t tì ự
ớ t t t j n, k n 1, m X[n]
ể tr ế k = 0 tt t ết tú
s ế X[k] m ể s
ổ m t j k, m X[k] t ể m t tờ
ự
k t k k 1 q ề
r tr ù ể ỉ ột é t q trọ
ó é t ỗ r t ột tt t ữ t
tờ r trờ ợ tt t ợ ết ữ ệ ủ
tí t ó ột trì

t tế ù ột tt t số é tí tự
ệ ò ụ tộ ỡ ủ t tứ ụ tộ ộ ớ ủ
ì tế ộ ứ t ủ tt t sẽ ột số ủ ộ ớ ủ
r ữ ứ ụ tự tễ ú t ết í
ỉ ết ỡ ủ ú tứ ó ột ớ ợ ủ tốt
ủ ú

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn
ệ tí tờ ữ số ữ ó s
tt ó s ỉ số 1 ó tt ỉ số 0 ì tế t tệ t
ù ệ ế số 2 tr ó ể ể ễ ột số t ỉ ù í
ệ 1 ột í ệ 0 1 ợ ọ ột ít ột số n ể
ễ ở k ữ số 1 ữ số 0 ợ ọ số kít r ụ
ụ tế t t sẽ t r số tự n sẽ ột số kít ớ k = [log
2
n]
í ệ ủ ột số
ộ ứ t ủ tt t ợ số é tí ít
Pé tí ít ột é tí số ọ tự ệ tr số ột ít
0 1
ể ớ ợ ộ ứ t ủ tt t t ù ệ ớ
ị ĩ
sử f(n) g(n) ị tr t ợ số
ó f(n) ó ớ ủ g(n) ết f(n) = O(g(n))
f = O(g) ế tồ t ột số C > 0 s n ủ ớ f(n)
g(n) ề ồ tờ f(n) < C.g(n)
í ụ
f(n) = a
i
n

(n) = O(g
1
(n)) tì (f
1
f
2
)(n) = O(g
1
g
1
(n))
ữ ế tồ t ớ ữ
lim
n
f(n)
g(n)
tì
ị ĩ
ột tt t ợ ọ ó ộ ứ t tứ ó tờ
tứ ế số é tí tết tự ệ tt t ợt q
O(log
d
n) tr ó n ộ ớ ủ d số

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn
ó
ó ế số kít tì tờ tự ệ tt
t O(k
d
) tứ t ớ ột tứ ủ k


S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn
r➺♥❣✱ ➤è✐ ✈í✐ ❝➳❝ t❤✉❐t t♦➳♥ ①➳❝ s✉✃t✱ ❦❤➠♥❣ t❤Ó ♥ã✐ ➤Õ♥ t❤ê✐ ❣✐❛♥ t✉②Öt ➤è✐
♠➭ ❝❤Ø ❝ã t❤Ó ♥ã✐ ➤Õ♥ t❤ê✐ ❣✐❛♥ ❤② ✈ä♥❣✳
➜Ó ❤×♥❤ ❞✉♥❣ ➤➢î❝ ♣❤➬♥ ♥➭♦ ✧➤é ♣❤ø❝ t➵♣✧ ❝ñ❛ ❝➳❝ t❤✉❐t t♦➳♥ ✭t✃t ➤Þ♥❤ ✈➭
①➳❝ s✉✃t✮ ❦❤✐ ❧➭♠ ✈✐Ö❝ ✈í✐ ♥❤÷♥❣ sè ❧í♥✱ t❛ ①❡♠ ❜➯♥❣ ❞➢í✐ ➤➞② ❝❤♦ ❦❤♦➯♥❣
t❤ê✐ ❣✐❛♥ ❝➬♥ t❤✐Õt ➤Ó ♣❤➞♥ tÝ❝❤ ♠ét sè ♥❣✉②➟♥ n r❛ t❤õ❛ sè ❜➺♥❣ t❤✉❐t t♦➳♥
♥❤❛♥❤ ♥❤✃t ➤➢î❝ ❜✐Õt ❤✐Ö♥ ♥❛② ✭t❛ ①❡♠ ♠➳② tÝ♥❤ sö ❞ô♥❣ ✈➭♦ ✈✐Ö❝ ♥➭② ❝ã tè❝
➤é ♠ét tr✐Ö✉ ♣❤Ð♣ tÝ♥❤ tr♦♥❣ ✶ ❣✐➞②✮✳
❙è ❝❤÷ sè t❤❐♣ ♣❤➞♥ ❙è ♣❤Ð♣ tÝ♥❤ ❜✐t ❚❤ê✐ ❣✐❛♥
✺✵ ✶✱✹✳10
10
✸✱✾ ❣✐ê
✼✺ ✾✱✵✳10
12
✶✵✹ ♥❣➭②
✶✵✵ ✷✱✸✳10
15
✼✹ ♥➝♠
✷✵✵ ✶✱✷✳10
23
✸✱✽✳10
9
♥➝♠
✸✵✵ ✶✱✺✳10
29
✹✱✾✳10
15
♥➝♠
✺✵✵ ✶✱✸✳10

. . . p
s
= q
1
q
2
. . . q
r
✱
tr♦♥❣ ➤ã p
1
, p
2
, . . . , p
s
❀ q
1
, q
2
, . . . , q
r
❧➭ ❝➳❝ sè ♥❣✉②➟♥ tè✳ ●✐➯♥ ➢í❝ ♥❤÷♥❣
sè ♥❣✉②➟♥ tè ❜➺♥❣ ♥❤❛✉ ❝ã ♠➷t tr♦♥❣ ❤❛✐ ✈Õ✱ t❛ ➤➢î❝ ➤➻♥❣ t❤ø❝
p
i
1
p
i
2
. . . p

❂ ✭✾✷✱✸✹✺✮ ❂ ✭✻✾✱✾✷✮ ❂ ✭✻✾✱✷✸✮ ❂✭✵✱✷✸✮ ❂ ✷✸✳ ◆❤➢ ✈❐②✱ ❣❝❞✭✸✹✺✱✶✶✷✼✮ ❂ ✷✸
❚❤✉❐t t♦➳♥ ❊✉❝❧✐❞ ♠ë ré♥❣
❈❤♦ ❤❛✐ sè ♥❣✉②➟♥ ❦❤➠♥❣ ➞♠ u, v t×♠ (u
1
, u
2
, u
3
) s❛♦ ❝❤♦
✶✶
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
(u, v) = u
3
= uu
1
+ vu
2
❚r♦♥❣ tÝ♥❤ t♦➳♥✱ t❛ t❤➟♠ ✈➭♦ ❝➳❝ ➮♥ ♣❤ô (v
1
, v
2
, v
3
)✱ (t
1
, t
2
, t
3
) ✈➭ ❧✉➠♥ ❝ã

3
) ←− (0, 1, v)✳
▼✷✳ ✭❑✐Ó♠ tr❛ v
3
= 0 ❄✮✳ ◆Õ✉ v
3
= 0✱ t❤✉❐t t♦➳♥ ❦Õt t❤ó❝✳
▼✸✳ ✭❈❤✐❛✱ trõ✮✳ ➜➷t q ←− [
u
3
v
3
]✱ ✈➭ s❛✉ ➤ã ➤➷t
(t
1
, t
2
, t
3
) ←− (u
1
, u
2
, u
3
) − q(v
1
, v
2
, v

❱í✐ ♥ ∈ N✱ sè ❧➢î♥❣ ❝➳❝ sè tù ♥❤✐➟♥ ❜Ð ❤➡♥ n ✈➭ ♥❣✉②➟♥ tè ❝ï♥❣ ♥❤❛✉
✈í✐ n ➤➢î❝ ❦ý ❤✐Ö✉ ❧➭ ϕ(n)
❱Ý ❞ô✿
ϕ(4) ❂ ✷ ❀ ϕ(5) ❂ ✹ ❀ ϕ(6) ❂ ✷ ❀ ϕ(7) ❂ ✻ ❀ ϕ(8) ❂ ✹
➜Þ♥❤ ❧ý
◆Õ✉ m, n ❧➭ ❝➳❝ sè ♥❣✉②➟♥ ❞➢➡♥❣ ♥❣✉②➟♥ tè ❝ï♥❣ ♥❤❛✉✱ t❤×
ϕ(m, n) = ϕ(m)✳ϕ(n)
❈❤ø♥❣ ♠✐♥❤✿
❚❛ ✈✐Õt ❝➳❝ sè ♥❣✉②➟♥ ❞➢➡♥❣ ❦❤➠♥❣ ✈➢ît q✉➳ m, n t❤➭♥❤ ❜➯♥❣ s❛✉✿
✶ ♠✰✶ ✷♠✰✶ ✳✳✳ ✭♥ ✲ ✶✮♠✰✶
✷ ♠✰✷ ✷♠✰✷ ✳✳✳ ✭♥ ✲ ✶✮♠✰✷
✸ ♠✰✸ ✷♠✰✸ ✳✳✳ ✭♥ ✲ ✶✮♠✰✸
✳✳✳ ✳✳✳ ✳✳✳ ✳✳✳ ✳✳✳
♠ ♠✰♠ ✸♠ ✳✳✳ ♠✳♥
✶✷
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ờ sử r ột số ợt q m
sử (m, r) = d > 1 ó số tr ò tứ r
tố ù ớ m.n ỗ tử ủ ò ó ề ó km + r
1 k n 1, d|(km + r) ì d|m, d|r.
ể tì số tr tố ù ớ m.n t ỉ
ò tứ r ớ (m, r) = 1 ét ột ò ó ứ
số r, m + r, ..., (n 1)m + r ì (r, m) = 1 ỗ số tr ò
ề tố ù ớ n
n số tr ò t ệ t ủ modulo m
số ó ũ tố ù ớ m ú tố ù
ớ m.n t s r (m, n) = (m)(n)
Pé tí ồ trì ồ
ị ĩ é tí ồ
sử m ột số ó số a b ồ

◆Õ✉ p ❦❤➠♥❣ ❝❤✐❛ ❤Õt a t❤× a
p−1
≡ 1 (mod p)
❱Ý ❞ô✿
6
5
≡ 6 (mod 5)❀ 6
5−1
≡ 1 (mod 5)❀ 10
5−1
≡ 0 (mod 5)
➜Þ♥❤ ❧ý ♠ë ré♥❣ ✭❊✉❧❡r✮
◆Õ✉ gcd(a, m) = 1 t❤× a
ϕ(m)
≡ 1 (mod m)
❈❤ø♥❣ ♠✐♥❤✿
●✐➯ sö {r
1
, r
2
, . . . , r
ϕ(m)
} ❧➭ ❤Ö t❤➷♥❣ ❞➢ t❤✉ ❣ä♥ ❦❤➠♥❣ ➞♠ ❜Ð ♥❤✃t
modulo m✳ ❑❤✐ ➤ã {ar
1
, ar
2
, . . . , ar
ϕ(m)
} ❝ò♥❣ ❧➭ ♠ét ❤Ö t❤➷♥❣ ❞➢ t❤✉ ❣ä♥✿

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ar
1
.ar
2
. . . ar
(m)
r
1
.r
2
. . . r
(m)
(mod m)

a
(m)
.r
1
.r
2
. . . r
(m)
r
1
.r
2
. . . r
(m)
(mod m)

ệ sử ụ ệ q ủ ị ý r ể tí t ờ t ò tờ
sử ụ t ì tế s ể ể rõ
ỉ í ụ s
í ụ í 709
23
mod 3137
ó 2
0
+ 2
1
+ 2
2
+ 2
4
709
1
(mod 3137) = 709
709
2
(mod 3137) = 761
709
4
(mod 3137) = 761
2
(mod 3137) = 1913
709
8
(mod 3137) = 1913
2
(mod 3137) = 1827

❱Ý ❞ô ▲✃② p = 11 t❛ ❝ã a = 4 ❧➭ ♠ét t❤➷♥❣ ❞➢ ❜×♥❤ ♣❤➢➡♥❣✳ ◆ã ❝ã ❤❛✐
♥❣❤✐Ö♠ ❧➭ ✷ ✈➭ ✾✱ tr♦♥❣ ➤ã ✾ ❧➭ ♠ét t❤➷♥❣ ❞➢ ❜×♥❤ ♣❤➢➡♥❣ ✭❉Ô ❞➭♥❣ ❦✐Ó♠ tr❛
3
2
≡ 9 (mod 11) ❤♦➷❝ 8
2
≡ 9 (mod 11)
❑ý ❤✐Ö✉ ▲❡❣❡♥❞r❡
❱í✐ sè ♥❣✉②➟♥ tè p > 2 ✈➭ sè ♥❣✉②➟♥ ❜✃t ❦ú a✱ ♥❣➢ê✐ t❛ ❦ý ❤✐Ö✉✿
L(a, p) := [
a
p
] = a
p−1
2
(mod p)
❱➭
L(a, p) := [
a
p
] =





0 ♥Õ✉ ❛ ❝❤✐❛ ❤Õt ❝❤♦ p
1 ♥Õ✉ ❛ ❧➭ ♠ét t❤➷♥❣ ❞➢ ❜×♥❤ ♣❤➢➡♥❣ ✭♠♦❞ p✮
−1 ❝➳❝ tr➢ê♥❣ ❤î♣ ❝ß♥ ❧➵✐
❚❛ ❝ã t❤Ó ♠ë ré♥❣ ❦❤➳✐ ♥✐Ö♠ ❦ý ❤✐Ö✉ tr➟♥ ❝❤♦ tr➢ê♥❣ ❤î♣ p ❦❤➠♥❣ ♣❤➯✐

0
< b)
b = r
0
a
1
+ r
1
, (0 r
1
< r
0
)
. . . . . . . . .
r
n3
= r
n2
a
n1
+ r
n1
, (0 r
n1
< r
n2
)
r
n2
= r

1
. . . + a
n1
+
1
a
n
ết tr ợ ọ ể ễ số ữ tỷ
a
b
ớ số
tụ
ể t ù ết
a
b
= [a
0
; a
1
, . . . , a
n
] P số tụ
[a
0
; a
1
, . . . , a
n
] ợ ọ số tụ ữ
ù tt t ó tể ể ễ ọ số ữ tỷ ớ số

], x
i
=
1
x
i1
a
i
ế ở ớ tứ
ó x
i
= 0 tì qú trì ết tú ề r ỉ x số
ữ tỷ ợ t ó x ể ễ ớ số tụ

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn

Trích đoạn Phân tích sử dụng liên phân số Phân tích dùng phương pháp của Pollard

---