Datu aizsardzība un kriptogrāfija

8.lekcija

Iepriekšējā lekcijā,meklējot saknes vienādojumam X² 17(mod 53*1997),

Atradām tādus x:

X21(mod 53) vai X32(mod 53)

X1289(mod 1997) vai X708(mod 1997)

Tātad ir 4 iespējas:

1. X21(mod 53) un X1289(mod 1997)

2. X21(mod 53) un X708(mod 1997)

3. X32(mod 53) un X1289(mod 1997)

4. X 32(mod 53) un X 708(mod 1997)

( Vienādojumam ir 4 saknes, kuras apzīmēsim ar S1., S2., S3. un S4.)

S1.:

X21(mod 53) un X1289(mod 1997)

X rēķināsim pēc formulas: XA*53+B*1997

21B*1997(mod 53)

21*CB*1997*C(mod 53)

meklē tādu C: C*21+1(mod 53)

21⁵²1(mod 53) , tad C21⁵¹

21⁵²21^32+16+2+1

21¹21 ;

21²17 ;

21⁴24 ;

21⁸46 ;

21¹⁶49 ;

21³²16

C16*49*17*2148(mod 53)

C=48

C*2148*B*1997(mod 53)

Tā kā C*211(mod 53), tad 148*B*1997(mod 53),tad 1B*32(mod 53)

32⁵²1(mod 53)

B32⁵¹

32⁵¹ 32^32+16+2+1

31¹ 32 ;

31² 17 ;

31⁴ 24 ;

31⁸46 ;

31¹⁶49 ;

31³²16

B16*49*17*325

Rēķināsim A

1289A*53(mod 1997)

D*1289A*53*(mod 1997)

Meklē tādu D : D*531(mod 1997)

53¹⁹⁹⁶1(mod 1997)

D53¹⁹⁹⁵(mod 1997);

D¹⁹⁹⁵ D^{1024+512+256+128+64+8+2+1}

53¹53;

53²812;

53⁴334;

53⁸1721;

53¹⁶290;

53³²226;

53⁶⁴1151;

53¹²⁸790;

53²⁵⁶1036;

53⁵¹²907;

53¹⁰²⁴1882

D1882*907*1036*796*1151*1721*812*53942(mod 1997)

D942

942*1289A(mod 1997)

A62

Tad X63*53+5*199713271

S113271

Tā kā S1 un S4 ir saistītas saknes (jo 32-21(mod 53)), tad S4 būs –13271

S453*1997-1327192570

Pārbaudot redzam, ka tiešām 13271² 17(mod 53*1997) un 92570² 17(mod 53*1997)

S2:

X21(mod 53)

un X708(mod 1997)

XA*53+B*1997

21B*1997(mod 53)

(jau iepriekš aprēķinājām, ka B5)

708A*53(mod 1997)

D*708A*53*D(mod 1997)

Meklē tādu D : D*531(mod 1997)

(jau iepriekš aprēķinājām, ka D942)

942*708A(mod 1997)

A1935

Tad S2: X1935*53+5*19971125406699(mod 53*1997)

Arī S2 un S3 ir saistītas saknes, jo 1289-708(mod 1997)

Tāpēc S353*1997-669999142(mod 53*1997)

Tiešām,var pārbaudīt, ka 6699² 17(mod 53) un 99142² 17(mod 53*1997)

1. X21(mod 53) un X1289(mod 1997)	2. X21(mod 53) un X708(mod 1997)
3. X32(mod 53) un X1289(mod 1997)	4. X 32(mod 53) un X 708(mod 1997)