ұқ: қ ғ ә ң қ
ғ қ ә ң қ ққ.
1. ә ғ .
ққ
315mod7=(3*314)mod7=(3*36*38)mod7=3*(32*3)2*((32)2)2mod7=(((32*3)2)2*32*3)mod7= 6.
315≡6(mod 7)
ң ң:
(1) mod 17 ( 10)
(2) 230 mod 5 ( 4)
(3) 516 mod 13 ( 1)
(4) 535 mod 33 ( 23)
(5) 723 mod 13 ( 2)
(6) 437 mod 26 ( 4)
2. ә .
(1), .
ұ a, n- . : - қ, ұғ - ң ғ. - ү ғ .
ә.
қ.
қ.
:
: . ү .
ә ққ.
: 10
:
қ . - , ң ғ n- ғ ң, қ n- ң.
n
, ұғ p,q- , .
, .
ң (1) қ қ.
ғ ү
ә 10 .
Ү . (1) ү ң . Ү ң ғ .
1. .
2. , ң қ, ә 3 қ .
3.
2 ққ .
- | ||||||
-3 | ||||||
-3 |
:
3. ax ≡ b mod n ңң .
ax ≡ mod n, ≠ 1 (2) ү ңң 2 ң ө.
- ax1 ≡ 1 mod n
- x = x1* mod n
1: 3x ≡ 6 mod 17
- 3x1 ≡ 1 mod 17
x1 = 6
- x = 6*6 mod 17 = 2
: 3*2 ≡ 6 mod 17 = 6
2: 2x ≡ 7 mod 9
- 2x1 ≡ 1 mod 9
x1 = 5
- x = 5*7 mod 9 = 8
: 2*8 ≡ 7 mod 9 = 5
3: 4x ≡ 11 mod 33
|
|
- 4x1 ≡ 1 mod 17
x1 = 4φ(33)-1mod 33 = 420-1mod 33 = (43)6 * 4 mod 33 = (31)6 * mod 33 = (312)3 * 4 mod 33 = 43 * 4 mod 33 = 31 * 4 mod 33 = 25
x1 = 25
- x = 25*11 mod 33 = 275 mod 33
x = 11
: 25*11 ≡ 11 mod 33 = 25
4. ү .
(3) ү .. 1 ғ Қ - .
Ққ Қ : ң - , қ . ұ ң қ ғ ә Ққ Қ . ұ 1 ғ Қ - ұғ. Ққ Қ қ қ құ .
:
1) N = n1* n2 ,
N1 = N/n1 = n2
N2 = N/n2 = n1
2) ң :
ң ү ү :
,
3) (3) ү :
x ≡ (a1N1y1 + a2N2y2) mod n1 n2
1:
1) N = 91
N1 = 13
N2 = 7
2) ң :
3) :
x ≡ (3*13*6 + 8*7*2) mod 91 = (234+112) mod 91 = 346 mod 91 = 73
x = 73
:
73 mod 7 = 3
73 mod 13 = 8
2:
1) N = 91
N1 = 13
N2 = 7
2) ң :
3) :
x ≡ (5*13*6 + 8*7*2) mod 91 = (390+112) mod 91 = 502 mod 91 = 47
x = 47
:
47 mod 7 = 5
47 mod 13 = 8
3:
1) N = 66
N1 = 11
N2 = 6
2) ң :
3) :
x ≡ (4*11*5 + 3*6*2) mod 66 = (220+36) mod 66 = 256 mod 66 = 58
x = 58
:
58 mod 6 = 4
58 mod 11 = 3