, , , . . . .
.
m1, m2, , m t ( , 1), , .. (mi, mj,) = 1 i ¹ j.
1, 2, , t , , 0 ≤ i ≤ m i.
= m1 m2 m t m i.
i = M / m i.
N i i (mod m i), i = 1, 2, , t, ..
i N i º 1 (mod m i).
( i , m i) = 1, N i
i N i + m i n i = 1, i = 1, 2, , t.
º i (mod m i), i = 1, 2, , t,
[0, M 1]
= a i N i i (mod M).
. = m1 m2 , m1 m2 . 1 < m 1
2 < m 2 , < , ,
º 1 (mod m 1) º 2 (mod m 2).
, N 1 N 2 , ,
1 N 1 º 1 (mod m 1) 2 N 2 º 1 (mod m 2).
M m 1 m 2 M
M 1 = = = m 2 ; M 2 = = m 1.
m 1 m 1 m 2
= (a 1 N 1 1 + a 2 N 2 2 ) (mod M).
1.6.1 ,
{ Î [0, M 1], mod m i = a i (1 ≤ i ≤ t)}
Begin
for i: = 1 to t do
N i : = inv (M i mod m i, m j);
x: = 0;
for i: = 1 to t do
x: = [x + M i N i a i ] mod n;
crt: = x {crt - }
End
.
º 1 (mod 5),
º 10 (mod 11)
55.
: m 1 = 5; m 2 = 11; M = m 1 m 2 = 5 11 = 55;
1 = 1; 2 = 10; M 1 = / m 1 = m 2 = 11; M 2 = / m 2 = m 2 = 5.
N 1 N 2, M 1 M 2 mod m 1 mod m 2 :
1 N 1 º 1 (mod m 1), 11 N 1 º 1 (mod 5) Þ N 1 = 1,
2 N 2 º 1 (mod m 2), 5 N 2 º 1 (mod 11) Þ N 2 = 9.
= (a 1 N 1 1 + a 2 N 2 2 ) (mod M) =
= (1 11 1 + 10 5 9) (mod 55) = (11 + 450) (mod 55) =
= 461 (mod 55) = 21 (mod 55).
, = 21 (mod 55).
|
|
p < q a < p. p, .. 2 º (mod p), p. p.
, 2 º (mod p) : + , .. .
1, 2, 3, , ( 1) /2.
< .
. = 7 1, 2, 4:
12 = 1 º 1 (mod 7),
22 = 4 º 4 (mod 7),
32 = 9 º 2 (mod 7),
42 = 16 º 2 (mod 7),
52 = 25 º 4 (mod 7),
62 = 36 º 1 (mod 7).
.
, :
2 º 3 (mod 7),
2 º 5 (mod 7),
2 º 6 (mod 7).
3, 5 6 7.
, ( 1) / 2 ( 1) / 2 .
, : 0 ( 1) / 2, ( 1) / 2 ( 1).
. .
= 7 1.7.1.
1.7.1 = 7
2 º (mod 7) | ||
1 | 2 | |
12 º 1 (mod 7) 22 º 4 (mod 7) 32 º 2 (mod 7) | +1 +2 +3 | -1 = -1 + 7 = 6 -2 = -2 + 7 = 5 -3 = -3 + 7 = 4 |
n q, .. n = p q,
(p 1) (q 1) / 4
n, n.
. 35 ( = 5, q = 7, n = 5 7 = 35)
(5 1) (7 1) 4 6
= = 6
4 4
: 1, 4, 9, 11, 16, 29, 35.