Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
a
n−1
2
(mod n) ∈ {1, n − 1}
0
n
a ∈ { 1, 2 , . . . , n − 1} n
1/2 1/2
{1, . . . , n − 1}
20 a
1
, . . . , a
20
i ∈ { 1, . . . , 20}
a
n−1
2
i
mod n ∈ {1, n − 1}.
1
2
20
< 10
−6
.
k ≥ 2
Number (x) Number (y)
O
1
O
2
M
h M
h(O
1
) h(O
2
)
h(O) O
h(O
1
) = h(O
2
)
O
1
O
2
O
1
O
2
O
1
O
2
n n = 10
16
M
M = {h
p
| p p ≤ n
2
, h
p
(m) = m mod p m ∈ IN
0
}.
p
h
p
(O
1
) = O
1
mod p h
p
(O
2
) = O
2
mod p
O
1
O
2
h
p
(O)
O h
p
(O
1
) h
p
(O
2
)
O
1
O
2
h
p
(O
i
)
O
i
M
O
1
O
2
M
O
1
6= O
2
M
O h(O)
0
O h(O)
p
ZZ
p
P
1
P
2
P
1
P
2
16
|M|
17
18
P
1
(x
1
, . . . , x
n
) P
2
(x
1
, . . . , x
n
) ZZ
p
(α
1
, . . . , α
n
) ∈ (ZZ
p
)
n
P
1
(α
1
, . . . , α
n
) ≡ P
2
(α
1
, . . . , α
n
) (mod p).
n x
1
, x
2
, . . . , x
n
d
d
X
i
1
=0
d
X
i
2
=0
. . .
d
X
i
n
=0
c
i
1
,i
2
,...,i
n
· x
i
1
1
·x
i
2
2
· . . . · x
i
n
n
.
P (x
1
, x
2
, x
3
, x
4
, x
5
, x
6
) = (x
1
+ x
2
)
10
·(x
3
− x
4
)
7
· (x
5
+ x
6
)
20
.
(x
1
+ x
2
)
n
=
n
X
k=0
n
k
·x
k
1
· x
n−k
2
,
P (x
1
, x
2
, x
3
, x
4
, x
5
, x
6
) (10 + 1) · (7 + 1) · (20 + 1) =
1848
P
1
(x
1
, . . . , x
n
) P
2
(x
1
, . . . , x
n
)
ZZ
p
p
α = (α
1
, . . . , α
n
) ∈ (ZZ
p
)
n
P
1
(x
1
, . . . , x
n
) 6≡ P
2
(x
1
, . . . , x
n
),
P
1
(α
1
, . . . , α
n
) mod p 6= P
2
(α
1
, . . . , α
n
) mod p.
h
α
(P
1
) = P
1
(α
1
, . . . , α
n
) mod p
P
1
19
AQP
p n d P
1
P
2
n
x
1
, . . . , x
n
d
α = (α
1
, . . . , α
n
) ∈
(ZZ
p
)
n
h
α
(P
1
) = P
1
(α
1
, . . . , α
n
) mod p h
α
(P
2
) = P
2
(α
1
, . . . , α
n
) mod p
h
α
(P
1
) = h
α
(P
2
)
P
1
≡ P
2
P
1
6≡ P
2
AQP P
1
P
2
ZZ
p
(α
1
, α
2
, . . . , α
n
) ∈ (ZZ
p
)
n
P
1
(α
1
, . . . , α
n
) = P
2
(α
1
, . . . , α
n
) (mod p).
P
1
P
2
P
1
≡ P
2
P
1
P
2
ZZ
p
p > 2nd AQP 1/2
P
1
(x
1
, . . . , x
n
) ≡ P
2
(x
1
, . . . , x
n
),
Q(x
1
, . . . , x
n
) = P
1
(x
1
, . . . , x
n
) − P
2
(x
1
, . . . , x
n
) ≡ 0.
P
1
P
2
Q
Q n
d
Q(α) 6≡ 0 (mod p) P
1
(α) 6≡ P
2
(α) (mod p)
α ∈
(ZZ
p
)
n
P (x)
x d P d
0
d
20
(ZZ
p
)
n
α
• d = 0 P (x) = c c c 6= 0
P P
• d − 1 d ≥ 1
d
P (x) 6≡ 0 a P
P (x) = (x − a ) · P
0
(x),
P
0
(x) =
P (x)
(x−a)
d − 1
P
0
(x) d − 1 P (x)
d ut
p
P
1
P
2
ZZ
p
d n p
Q(x
1
, . . . , x
n
) 6≡ 0 ZZ
p
n
x
1
, . . . , x
n
Q d
Q
n · d · p
n−1
.
n
• n = 1 Q(x
1
)
d n = 1 d = n · d · p
n−1
• n−1
n n
Q
Q(x
1
, x
2
, . . . , x
n
) = Q
0
(x
2
, . . . x
n
) + x
1
· Q
1
(x
2
, . . . , x
n
) + . . .
+ x
d
1
· Q
d
(x
2
, . . . , x
n
)
=
d
X
i=0
x
i
1
·Q
i
(x
2
, . . . , x
n
)
Q
0
(x
2
, . . . x
n
), Q
1
(x
2
, . . . , x
n
), . . . , Q
d
(x
2
, . . . , x
n
).
Q(α
1
, α
2
, . . . , α
n
) ≡ 0 (mod p) α = (α
1
, . . . , α
n
) ∈ (ZZ
p
)
n
Q
i
(α
2
, . . . , α
n
) ≡ 0 (mod p) i = 0, 1, . . . , d
j ∈ {0, 1, . . . , d} Q
i
(α
2
, . . . , α
n
) 6= 0 (mod p)
α
1
Q(x
1
) = Q
0
(α
2
, . . . α
n
) + x
1
·Q
1
(α
2
, . . . , α
n
) + . . .
+ x
d
1
·Q
d
(α
2
, . . . , α
n
).
21
Q d
Q(x
1
, . . . , x
n
) 6≡ 0 k ∈ {0, 1, . . . , d}
Q
k
(x
2
, . . . , x
n
) 6≡ 0.
Q
k
(n − 1) · d ·p
n−2
.
(n−1)·d·p
n−2
α = (α
2
, . . . , α
n
) ∈
(ZZ
p
)
n−1
i ∈ { 0, 1, 2, . . . , d}
Q
i
(
α) ≡ 0 (mod p).
α
1
x
1
{0, 1, . . . , p −1 }
p · (n − 1) · d · p
n−2
= (n − 1) · d ·p
n−1
α = (α
1
, α
2
, . . . , α
n
) ∈ (ZZ
p
)
n
Q(x
1
) 6≡ 0 Q
d d α
1
∈ ZZ
p
Q(α
1
) ≡ 0 (mod p)
d · p
n−1
α = (α
1
, α
2
, . . . , α
n
) ∈ (ZZ
p
)
n
Q(x
1
, . . . , x
n
)
(n − 1) · d · p
n−1
+ d · p
n−1
= n · d · p
n−1
.
ut
d n p
Q(x
1
, . . . , x
n
) 6≡ 0 ZZ
p
n
x
1
, . . . , x
n
Q d
Q 6≡ 0
1 −
n · d
p
· p
n
.
(ZZ
p
)
n
p
n
n · d ·p
n−1
p
n
− n · d ·p
n−1
=
1 −
n · d
p
· p
n
.
ut
22
p
n
(ZZ
p
)
n
1 −
n · d
p
.
p > 2nd 1/2
(ZZ
p
)
n
1
AQP p
•
•
23
Q 6≡ 0 P
1
(x
1
, . . . , x
n
) 6≡ P
2
(x
1
, . . . , x
n
)
24
n
(n−1)
2
•
•
O((log
2
n)
12
) n
25
26
27
n dlog
2
(n + 1)e
28
O((log
2
n)
3
)
•
•
RSA
1