Джумадильдаев А.С. Элементы дискретной математики (часть 1)
Подождите немного. Документ загружается.
p
5
=2
13
− 1 = 8191,p
6
=2
17
− 1 = 131071,p
7
=2
19
− 1 = 524287.
2
3021377
− 1.
2
24036583
− 1.
2
293
− 1 = 159 ...791
2
971
− 1.
n ⇒ a
n
≡ a(mod n), ∀a ∈ Z.
a n
a n
10
100
.
a
n
a =3,n ≈ 10
100
a
n
n.
n.
n a ∈ Z
a
n
≡ a(mod n).
n.
n
⇒ ⇐
1729 = 7 · 13 · 19
a
1729
≡ a(mod 1729), ∀a ∈ Z.
561 3 · 11 · 17
1105 5 · 13 · 17
1729 7 · 13 · 19
2465 5 · 17 · 29
2821 7 · 13 · 31
6601 7 · 32 · 41
8911 7 · 19 · 67
41041 7 · 11 · 13 · 41
825265 5 · 7 · 17 · 19 · 73
413631505 5 · 7 · 17 · 73 · 89 · 107
a
n
−
a ≡ 0(mod n)
a(mod n) n
n ⇒ (a + b)
n
= a
n
+ b
n
(mod n), ∀a, b ∈ Z.
n
a
n
∈{1, −1}
a ∈ Z, (a, n)=1
a
n
≡ a
n−1
2
(mod n), n ,
a
n
≡
a
p
1
···
a
p
r
,
n = p
1
···p
r
, p
i
,
a
b
=0,
(a, b) =1,
a
1
=1,
a ∈ Z.
a
b
,
n
n ⇒ a
n−1
2
≡
a
n
(mod n)
a ∈ Z (a, n)=1.
a n
a
n−1
2
≡
a
n
(mod n).
n a
n−1
2
≡
a
n
(mod n),
a ∈{1, 2,...,n− 1}, n.
a(mod n).
{1, 2,...,n− 1}
a
n−1
2
≡
a
n
= ±1(mod n).
a n
a n
n
a ≤ 1/2,
100
≤ (1/2)
100
< 0. 000000000000000000000000000001
30
.
n.
a,
a<70(log n)
2
,a .
a a
n−1
2
≡
a
n
(mod n),
n
n
a
n
n
a
n
.
k ≤ 1200
k =2, 19, 23, 317, 1031.
n, 10
n n
n a
1
,a
2
,...,a
n
n
a
1
,a
2
,...,a
n
n (n −1)
{1, 2,...,n− 1},
a
k
a
s
s<k,
a
k
−a
s
= a
k−s
· 10
s
n. 10 n a
k−s
n.
a
n
.
a
N
m.
a
a =
k
i=0
a
i
n
i
,
0 ≤ a
i
<n, i≥ 0,
(a
k
···a
1
a
0
)
n
a
k
···a
1
a
0
n a.
a = 3602. a =3· 10
3
+6· 10
2
+0· 10
1
+2· 10
0
.
3602 a.
a = 3602. a =1· 5
5
+3· 5
3
+4·5
2
+2 103402 5
a.
a = 3602. a =1· 2
11
+1· 2
10
+1· 2
9
+1· 2
4
+1· 2
1
111000010010 a.
n a
a = nq
0
+ r
0
, 0 ≤ r
0
<n,
q
0
= nq
1
+ r
1
, 0 ≤ r
1
<n,
q
1
= nq
2
+ r
2
, 0 ≤ r
2
<n,
q
k−2
= nq
k−1
+ r
k−1
, 0 ≤ r
k−1
<n,
q
k−1
= nq
k
.
r
k−1
r
k−2
···r
1
r
0
n a.
3602 = 2 · 1801 + 0,r
0
=0,
1801 = 2 · 900 + 1,r
1
=1,
900 = 2 · 450 + 0,r
2
=0,
450 = 2 · 225 + 0,r
3
=0,
225 = 2 · 112 + 1,r
4
=1,
112 = 2 · 56 + 0,r
5
=0,
56 = 2 · 28 + 0,r
6
=0,
28 = 2 · 14 + 0,r
7
=0,
14 = 2 · 7+0,r
8
=0,
7=2·3+1,r
9
=1,
3=2· 1+1,r
10
=1,
1=2· 0+1,r
11
=1.
3602 111000010010.
N N =
k
i=0
N
i
2
i
.
N
k
···N
1
N
0
1 SM
a
0
S SM
a
a
k
, S
2 m M
a
a
m.
165
5
N = 221.
SM
165
SSM
165
. SM
165
,
SSM
165
.
165
5
= ((165)
2
)
2
· 165.
Z
221
165
2
=42, 42
2
= 217, 217 · 165 = 3.
165
5
≡ 3(mod 221).
x
0 <X<N
N e
• N = pq, p q B
• e ∈ N φ(N)=(p − 1)(q − 1).
x E(x)=x
e
(mod N).
• d ∈ N 1 ≤ d ≤ N − 1 ed ≡ 1(mod φ(N)).
e φ(N)).
ed ≡ 1(mod φ(N)) φ(N),
φ(N)=φ(pq)=φ(p)φ(q)=(p −1)(q −
1).
•
y = E(x), D(y)=
y
d
(mod N),
y
d
≡ x
ed
≡ x
φ(N)k+1
≡ (x
φ(N)
)
k
x ≡ x(mod N).
p q,
p q,
f : X → Y f(x)
x ∈ X, f
−1
(y)
y ∈ Y.
f
f f
x
i
q
a
H
H
H
A
A
A
A
A
y
i
qq
@
@
N,e
&%
'$
x = y
d
d
N e
p, q, d
N = pq, (e, φ(N)) = 1,ed ≡ 1(mod φ(N))
p, q
y ≡ x
e
(mod N).
x ≡ y
d
(mod N).
N = 4294967297 e =19.
y =2. x.
N e φ(N) e
N =2
2
5
+ 1 = 4294967297
4294967297 = 641 · 6700417.
φ(2
2
5
+ 1) = (641 − 1)(6700417 − 1) = 4288266240.
φ(N) 2
14
.
φ(N)/2
14
φ(N)/2
14
=3· 5 · 17449.
φ(N) = 4288266240 = 2
14
· 3 · 5 · 17449
φ(N) e
φ(N)/e
4288266240
19
= 225698223 +
1
6+
1
3
.
δ
0
= 225698223,
δ
1
= 225698223 +
1
6
=
1354189339
6
,
k =2,P
1
= 1354189339,Q
1
=6.
19 · 1354189339 − 6 · 4288266240 = 1.
d 19 φ(N)
d = 1354189339.
d = d
1
· d
2
,
d
1
= 8689,d
2
= 155851.
2
d
2
≡ 2048(mod N),
2048
d
1
≡ 134217728(mod N).
x =2
d
= 134217728(mod N).
x = 134217728.
y =3
N = 221,e=5.
N = 221 = 13 · 17.
φ(221) = (13 − 1)(17 − 1) = 192.
192 = 2
6
· 3.
M = m
1
···m
n
,
M
i
= m
1
···m
i−1
m
i+1
···m
n
,
x
i
x
i
M
i
≡ 1(mod m
i
),
x =
n
i=1
x
i
b
i
x ≡ b
i
(mod m
i
),i=1,...,n.
d = e
−1
e φ(N).
5
−1
≡ 2(mod 3),
5
−1
≡ 13(mod 64),
ed ≡ 1(mod 64),
ed ≡ 1(mod 3).
d ≡ 13(mod 64),
d ≡ 2(mod 3).
m
1
=64,m
2
=3,M=64· 3 = 192,M
1
=3,M
2
=64,
3x
1
≡ 1(mod 64), 64x
2
≡ 1(mod 3).
x
1
≡−21(mod 64).
64 ≡ 1(mod 3),
x
2
≡ 1(mod 3).
x = −21 · 13 · 3+1· 2 · 64 = −691 ≡ 77(mod 192),
d =77.
77=64+8+4+1=1· 2
6
+0· 2
5
+0· 2
4
+1· 2
3
+1·2
2
+1·2
0
.
SM
3
SSSM
3
SM
3
SSM
3
.
SM
3
, SSSM
3
SM
3
SSM
3
.
3
77
= ((((((3
2
)
2
)
2
· 3)
2
· 3)
2
)
2
) · 3.
Z
221
3
2
=9, 9
2
=81, 81
2
= 152, 152 · 3=14, 14
2
= 196, 196 · 3 = 146,
146
2
= 100, 100
2
=55, 55 · 3 = 165.
3
77
≡ 165(mod 221),
x = 165.
165
5
≡ 3(mod 221).
x = 165.