Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
C
I
C
II
C
I
C
II
n n 10
16
C
I
C
II
C
I
C
II
C
I
C
II
n
n−1 10
16
R = (C
I
, C
II
)
C
I
x n x = x
1
. . . x
n
C
II
y n y = y
1
. . . y
n
x = y
C
I
p
[2, n
2
]
Prim
n
2
∼ n
2
/ ln n
2
dlog
2
n
2
e ≤
2 · dlo g
2
ne
9
C
I
C
II
10
C
I
s = Number(x) mod p
s p C
II
s p dlog
2
n
2
e
s ≤ p < n
2
4 · dlog
2
ne
s p C
II
q = Number(y) mod p.
q 6= s C
II
x 6= y
q = s C
II
x = y
R = (C
I
, C
II
)
R
s p s ≤ p < n
2
2 · dlog
2
n
2
e ≤ 4 · dlog
2
ne.
n = 10
16
4 · 16 ·dlog
2
10e = 256
x y
• x = y
Number(x) mod p = Number (y) mod p
p C
II
0
• x 6= y
C
I
p
z = Number (x) mod p = Number(y) mod p.
x
0
y
0
Number(x) = x
0
·p + z
Number(y) = y
0
· p + z.
Number(x) − Number (y) = x
0
· p − y
0
· p = (x
0
− y
0
) · p
p
w = |Number (x) − Number (y)|.
R = (C
I
, C
II
)
p w p Prim
n
2
{2, 3, . . . , n
2
}
Prim
n
2
∼ n
2
/ ln n
2
w x y
n
w = |Number(x) − Number (y)| < 2
n
.
w
w = p
i
1
1
p
i
2
2
. . . p
i
k
k
,
p
1
< p
2
< ··· < p
k
i
1
, i
2
, . . . , i
k
k ≤ n − 1;
k ≥ n
w = p
i
1
1
p
i
2
2
. . . p
i
k
k
≥ p
1
p
2
. . . p
n
> 1 · 2 · 3 · ··· · n = n! > 2
n
,
w < 2
n
w n − 1
{2, 3, . . . , n
2
} n
p w
n − 1
Prim (n
2
)
≤
n − 1
n
2
/ ln n
2
≤
ln n
2
n
.
R
x y
ln n
2
n
,
n = 10
16
0.36892 · 10
−14
R = (C
I
, C
II
)
10
R
10
11
C
I
x n x = x
1
. . . x
n
C
II
y n y = y
1
. . . y
n
x = y
C
I
10
p
1
, p
2
, . . . , p
10
{2, 3, . . . , n
2
}
C
I
s
i
= Number(x) mod p
i
i = 1, 2, . . . , 10
p
1
, p
2
, . . . , p
10
, s
1
, s
2
, . . . , s
10
C
II
C
II
q
i
= Number (y) mod p
i
i = 1, 2, . . . , 10 i ∈ {1, 2, . . . , 10} q
i
6= s
i
C
II
x 6= y q
j
= s
j
j ∈ {1, 2, . . . , 10} C
II
x = y
R
10
10 R
n = 10
16
2560
x = y R
10
1 x = y
0
x 6= y R
10
x = y
10 n −1
w = |Number(x) −Number(y)|.
10 10
n − 1
Prim (n
2
)
10
≤
ln n
2
n
10
=
2
10
· (ln n)
10
n
10
.
n = 10
16
0.4717 · 10
−141
.
24
79 10
−141
10
16
R
10
R
k R
k
k k
R R
k
k
R
Q
r
r ∈ IN − {1, 2} Q
r
R p
{2, 3, . . . , n
r
} {2, 3, . . . , n
2
}
Q
r
r ≥ 2
δ > 1
n
1/δ
R
R
R x 6= y
p
12
Number(x) mod p 6= Number(y) mod p.
p
x
y
x 6= y
R
Prim
n
2
∼ n
2
/ ln n
2
[2, n
2
] Prim
n
2
Prim
n
2
−(n −1) x 6= y x
y
n
2
ln n
2
− (n − 1)
n
2
ln n
2
≥ 1 −
ln n
2
n
.
1
1/2
C
I
C
II
(x, y)
n
13
n − 1 n
n · 4 · log
2
n C
I
C
II
(x, y)
Number(x) − Number (y) = p
1
·p
2
· ··· · p
k
,
k =
n
2(log n)
2
p
1
< p
2
··· < p
k
k
k+1
n−1
2
n n dlog
2
ne
log
2
n
log
10
n ≈ 500
{2, 3, . . . , b
√
nc} n
log
2
n
√
n = 2
log
2
n
2
p
m > 1 p n
n = p ·q
p q
n p q
Ω(
√
n)
p
a (a, p) = 1
a
p−1
mod p = 1 .
14
15
p
c d
c · d mod p = 0 ⇔ c mod p = 0
d mod p = 0.
a (a, p) = 1
m
1
= 1 · a, m
2
= 2 · a, . . . , m
p−1
= (p − 1) · a.
u, v ∈ {1, . . . , p − 1} u 6= v
m
u
mod p 6= m
v
mod p
m
u
mod p = m
v
mod p
u, v ∈ {1, . . . , p − 1} u > v p
m
u
− m
v
= u · a − v ·a = (u − v) · a.
• u − v < p p u − v
• (a, p) = 1 p a
|{m
1
mod p , m
2
mod p, . . . , m
p−1
mod p }| = p − 1.
m
i
mod p 0 m
i
p u
m
u
mod p = (u · a) mod p = 0.
u mo d p = 0 a mod p = 0.
p u a u < p
(a, p) = 1
{m
1
mod p , m
2
mod p, . . . , m
p−1
mod p } = {1, 2 , . . . , p − 1}.
m = m
1
· m
2
· ··· · m
p−1
.
m
i
m = 1 · a · 2 · a · ··· · (p − 1) · a = 1 ·2 · ··· · (p − 1 ) · a
p−1
.
m mod p = 1 · 2 · ··· ·(p − 1) mod p.
1 · 2 · ··· · (p − 1) · a
p−1
mod p = 1 · 2 · ··· · (p − 1) mod p,
a
p−1
mod p = 1.
ut
p ⇐⇒ a ∈ {1, . . . , p − 1}
a
p−1
2
mod p ∈ {1, p −1}.
a ∈ { 1, . . . , n − 1} n
a
n−1
2
mod n /∈ {1, n − 1}.
n
n−1
2
n
n
n−1
2
(
n mod 4 = 3)
n
a
n−1
2
mod n ∈ {1, n − 1}
a ∈ {1, . . . , n −1};
n
a
n−1
2
mod n /∈ {1, n − 1}
a {1, . . . , n − 1}
∗
m m mod 4 = 3
m 1/2
a
n−1
2
mod n
n−1
2
a
dlog
2
ne
b = 2
k
a
b
mod p k
a
2
mod p = a · a mod p,
a
4
mod p = (a
2
mod p ) ·(a
2
mod p ) mod p,
a
8
mod p = (a
4
mod p ) ·(a
4
mod p ) mod p,
a
2
k
mod p = (a
2
k−1
mod p )
2
mod p .
k ∈ IN b
i
∈ {0, 1} i =
1, . . . , k
b
b =
k
X
i=1
b
i
·2
i−1
b = Number (b
k
b
k−1
. . . b
1
) a
b
a
b
= a
b
1
·2
0
· a
b
2
·2
1
·a
b
3
·2
2
. . . · a
b
k
·2
k−1
.
a
b
mod p
a
i
= a
2
i
mod p
p a
i
b
i
= 1
a
n−1
2
mod n a ∈ {1, . . . , n−1}
{0, 1, . . . , n −1}
dlog
2
ne a
n−1
2
mod n
2 · dlo g
2
n − 1
2
e ∈ O (log
2
n).
O((log
2
n)
2
)
n
n−1
2
.
a ∈ {1, 2, . . . , n − 1}
x := a
n−1
2
(mod n)
x ∈ {1, n − 1 }
n a ∈ {1, . . . , n − 1}