Lekcija Nr.7 kursā “Datu aizsardzība un kriptogrāfija”

 

Šajā lekcijā tiks apskatītas metodes, kā atrisināt kongruences ar tipu .
Piemēram, kā atrisināt kongruenci ?
 

Vispirms apskatīsim t.s. Ķīniešu teorēmu par atlikumiem:

Teorēma:

Ja ir pirmskaitļi, tad lineāru kongruenču sistēmai

eksistē atrisinājums.


Piemērs:

Vai kongruenču sistēmai

eksistē atrisinājums?

Šāds atrisinājums patiešām eksistē, jo ir iespējams sastādīt sekojošu tabulu:
 

 

Pēc moduļa 11

Pēc moduļa 5

0

1

2

3

4

5

6

7

8

9

10

0

55

45

35

25

15

5

50

40

30

20

10

1

11

1

46

36

26

16

6

51

41

31

21

2

22

12

2

47

37

27

17

7

52

42

32

3

33

23

13

3

48

38

28

18

8

53

43

4

44

34

24

14

4

49

39

29

19

9

54

 
Pēc šīs tabulas iespējams atrast atrisinājumu pie jebkurām a un b vērtībām.

Piemēram, kongruenču sistēmai

eksistē viens konkrēts atrisinājums: x=47.


Apskatīsim vēl vienu piemēru:

Vai kongruenču sistēmai

eksistē atrisinājums?

Šai sistēmai atrisinājums neeksistē, jo nav tādu pāra skaitļu, kurus dalot ar 4 atlikumā iegūst 1.

Šāds pretpiemērs tikai parāda, ka Ķīniešu teorēma par atlikumiem nav spēkā, ja kāds no skaitļiem ir salikts skaitlis.


Kā lai risina šādu kongruenci: ?

Ja skaitlis a dalās bez atlikuma ar reizinājumu bc, tad a dalās bez atlikuma gan ar b, gan ar c.

Apskatāmajā piemērā dalās bez atlikuma ar (53*1997), tātad dalās bez atlikuma arī ar 53 un 1997 atsevišķi. Citiem vārdiem, tas nozīmē:

jeb

Šai kongruenču sistēmai eksistē atrisinājums saskaņā ar Ķīniešu teorēmu par atlikumiem (jo skaitļi 53 un 1997 ir pirmskaitļi); viegli ieraudzīt, ka par atrisinājumu der .

Vispārīgā gadījumā y tiek meklēts sekojošā formā: 

Lai atrastu šādu y, jāatrisina kongruenču sistēma:

Iepriekš minētās sakarības ir spēkā arī aizvietojot ar , t.i. kongruenci

(A) 

var reducēt uz kongruenču sistēmu:

(B) 

(A) un (B) ir identiski uzdevumi, tāpēc (A) vietā var risināt (B), jo tas ir vieglāk.
Kā risināt kongruences ar tipu , skat. iepriekšējās lekcijas izklāstā.

Mēģināsim atrisināt kongruenču sistēmu (B).

Pirmais solis ir - atsevišķi atrisināt kongruences un .





Noskaidro, cik ir pēc moduļa 53:


















Noskaidro, cik ir pēc moduļa 1997:
















;

Esam ieguvuši 4 dažādas x vērtības:

Vēl jāpārbauda, kuras no tām apmierina kongruenču sistēmu:

Kā to pārbaudīt - skat. nākošajā lekcijā :-)