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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
70
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
n
X[1], X[2], , X[n] m j j
m = X[j] = max
1≤k≤n
X[k]
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
X[n]
m = X[n] j = n X[n] X[n − 1]
n −1 = 0 n = 1 X[n −1] ≤ X[n]
X[n] X[n − 2]
X[n − 1] X[n] X[n − 1]
m = X[n −1] j = n −1
j
j ←− n, k ←− n − 1, m ←− X[n]
k = 0
X[k] ≤ m
m j ←− k, m ←− X[k] m
a
i
> 0
f(n) = O(n
i
)
f
1
(n) = O(g(n)), f
2
(n) = O(g(n)) f
1
(n) + f
2
(n) = O(g(n))
f
1
(n) = O(g
1
(n)), f
2
(n) = O(g
1
(n)) (f
1
f
2
)(n) = O(g
1
g
23
10
9
10
29
10
15
10
39
10
25
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
n n n = a.b
1 < a b < n n a b
n
n = p
1
p
2
. . . p
s
= q
1
q
2
. . . q
r
p
1
, p
q
j
1
q
j
1
b = 0 a
r ←− a mod b a ←− b b ←− r
u, v (u
1
, u
2
, u
3
)
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
(v
1
, v
2
, v
3
) (t
1
1
, v
2
, v
3
) ←− (0, 1, v)
v
3
= 0 v
3
= 0
q ←− [
u
3
v
3
]
(t
1
, t
2
, t
3
) ←− (u
1
, u
2
, u
3
) − q(v
)
∈ N n
n ϕ(n)
ϕ(4) ϕ(5) ϕ(6) ϕ(7) ϕ(8)
m, n
ϕ(m, n) = ϕ(m) ϕ(n)
m, n
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
r m
(m, r) = d > 1 r
m.n km + r
1 ≤ k ≤ n − 1, d|(km + r) d|m, d|r.
m.n
r (m, r ) = 1
r, m + r, , (n −1)m + r (r, m) = 1
n
n modulo m
m
m.n ϕ(m, n) = ϕ(m) ϕ(n)
m a b
modulo m m a − b
a modulo m
a ≡ b (mod m)
a ≡ b (mod m) k,
a = b + km
a ≡ a (mod m)
a ≡ b (mod m) b ≡ a (mod m)
a ≡ b (mod m)
b ≡ c (mod m)
, r
2
, . . . , r
ϕ(m)
}
modulo m {ar
1
, ar
2
, . . . , ar
ϕ(m)
}
(a, m) = 1
(r
i
, m) = 1, i = 1, . . . , ϕ(m)
.
⇒ (r
1
r
2
. . . r
ϕ(m)
, m) = 1
r
i
≡ r
j
(mod m) (i = j) → ar
ϕ(m)
≡ r
1
.r
2
. . . r
ϕ(m)
(mod m)
(r
i
, m) = 1 r
1
.r
2
. . . r
ϕ(m)
a
ϕ(m)
≡ 1 (mod m)
ϕ(m) = m − 1
gcd(c, m) = 1 a ≡ b (mod ϕ(m)) a, b
c
a
≡ c
b
(mod m)
e, d e.d ≡ 1 (mod ϕ(m))
c m (c
e
)
16
(mod 3137) = 1827
2
(mod 3137) = 161
2
4
, 2
2
, 2
1
, 2
0
modulo 3137
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
709
23
(mod 3137) = 709.761.1913.161. (mod 3137) = 907
p a ≤ p
(mod p) x x
2
≡ a (mod p)
p = 11 a = 4
3
2
≡ 9 (mod 11) 8
2
≡ 9 (mod 11)
p > 2 a
L(a, p) := [
a
1
)L(a, p
2
) . . . L(a, p
k
)
n J(a, n) = L(a, n)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
a b b > 0
a = ba
0
+ r
0
, (0 ≤ r
0
< b)
b = r
0
a
1
+ r
1
, (0 ≤ r
1
< r
0
)
. . . . . . . . .
r
n−3
1
b
r
0
= . . . = a
0
+
1
a
1
+
1
. . . + a
n−1
+
1
a
n
a
b
a
b
= [a
0
; a
1
, . . . , a
n
]
[a
1
x
i−1
], x
i
=
1
x
i−1
− a
i
x
i
= 0 x
x
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
x = a
0
+
1
a
1
+
1
. . . +
1
a
n
+ . . .
x = a
1
a
1
+
+
1
a
2
+
+ . . . +
1
a
n
x = [a
0
; a
1
, . . . , a
n
, . . .]
k x :
C
k
= [a
0
; a
1
, . . . , a
k
]
b
k−1
+ b
k−2
, q
k
= a
k
q
k−1
+ q
k−2
(i) C
k
= [a
0
; a
1
, . . . , a
k
] =
b
k
q
k
(ii) k ≥ 1 b
k
q
k+1
− b
a
k
= [α
k
]
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
P
k+1
= a
k
Q
k
− P
k
, Q
k+1
=
n − P
2
k+1
Q
k
b
2
k
− nq
2
k
= (−1)
k+1
n − a
0
=
a
0
+
√
n
(n − a
2
0
)
=
P
1
+
√
n
Q
1
= α
1
i ≥ 1
1
x
i
=
1
1
x
)
Q
i
=
1
(
√
n − P
i+1
)
Q
i
=
P
i+1
+
√
n
(n − P
2
i+1
)
Q
i
=
P
i+1
+
√
n
P
k+1
+
√
n
Q
k+1
√
n =
(P
k+1
+
√
n)b
k
+ Q
k+1
b
k−1
(P
k+1
+
√
n)q
k
+ Q
k+1
q
k−1
nq
k+1
b
k−1
,
b
k
= P
k+1
q
k
+ Q
k+1
q
k−1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
q
k
b
k
b
2
k
− nq
2
k
= (−1)
k+1
Q
k+1
b
n, Q
1
= n − a
2
0
> 0
P
k
<
√
n, Q
k
> 0 k ≥ 1
Q
k
=
n − P
2
k+1
Q
k+1
=
√
n + P
k+1
Q
k+1
(
√
n − P
n, Q
k
> 0, ∀k ∈ N
α
k
=
√
n + P
k
Q
k
Q
k
< α
k
.Q
k
=
√
n + P
k
<
√
n +
√
n = 2
√
n, ∀k ∈ N
b
2
a, b (1; 29) (a, 29) = 1
P ≡ a
−1
(C − b) (mod 29) C, a, b
[
[
[
[
[
[
[
[
[
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Copyright: Tài liệu đại học ©