117 (mod 562).Datu aizsardzība un kriptogrāfija.
Mārtiņš Rūsiņš Freivalds
5. Lekcija (konspekts).
Tālākais mērķis - prast risināt šāda veida uzdevumus :
X2 117 (mod 562).
| mod\x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 3 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | ||||||||||
| 4 | 0 | 1 | 0 | 1 | 0 | 1 | |||||||||||
| 5 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | ||||||||||
| 6 | 0 | 1 | 4 | 3 | 4 | 1 | 0 | ||||||||||
| 7 | 0 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | |||||||||
| 8 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | ||||||||
| 9 | 0 | 1 | 4 | 0 | 7 | 7 | 0 | 4 | 1 | 0 | |||||||
| 10 | 0 | 1 | 4 | 9 | 6 | 5 | 6 | 9 | 4 | 1 | 0 | ||||||
| 11 | 0 | 1 | 4 | 9 | 5 | 3 | 3 | 5 | 9 | 4 | 1 | 0 | |||||
| 12 | 0 | 1 | 4 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 4 | 1 | 0 | ||||
| ... | |||||||||||||||||
| 16 | 0 | 1 | 4 | 9 | 0 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 0 | 9 | 4 | 1 | 0 |
| - periods |
Ja modulis p ir pirmsskaitlis, tad perioda garums ir (p - 1).
Apūkosim tās tabulas rindiņas, kur moduļi nav salikti skaitļi.
| mod\x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 3 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | ||||||||||
| 5 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | ||||||||||
| 7 | 0 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | |||||||||
| 11 | 0 | 1 | 4 | 9 | 5 | 3 | 3 | 5 | 9 | 4 | 1 | 0 | |||||
| 13 | 0 | 1 | 4 | 9 | 3 | 12 | 10 | 10 | 12 | 3 | 9 | 4 | 1 | 0 |
Lai kāds arī būtu modulis, periodā vērojama simetrija un garums līdz (p - 1).
a (mod 13). a = 0 tikai tad, ja X2 dalās ar 13 => X dalās ar 13.
9 (mod 13). X = 3 vai X = 10.
1 (mod p). X 1 (mod p) vai X - 1 (mod p).
X2 a (mod p). Mūs interesē kādiem a eksistē saknes.
T. Lai kongruencei X2 a (mod p) pie p (p - pirmsskaitlis, p
> 2) eksistētu atrisinājumi, nepieciešami un pietiekami, ka
a(p-1)/2 1 (mod p).
Hipotēze: Lai kongruencei X2 a (mod p) pie p (p -
pirmsskaitlis, p > 2) neeksistētu atrisinājumi,
nepieciešami un
pietiekami, ka a(p-1)/2 -1 (mod p).
Ko var teikt par skaitļa a(p-1)/2 (mod p) atlikumu?
Fermā mazā teorēma saka, ka a(p-1) 1 (mod p). Tātad a((p-1)/2)*2
1 (mod p),
tātad (a(p-1)/2)2 1 (mod p).
Bet kvadrātsakne no 1 ir ± 1, tātad a(p-1)/2
±1 (mod p).
Definīcija: Ja kongruencei X2 a (mod p) eksistē
atrisinājums (p - pirmsskaitlis, p > 2), tad saka, ka a ir kvadrātisks
rezīdijs (angl. residue) pēc moduļa p. Ja neeksistē
- kvadrātisks nerezīdijs.
Teorēma: Pie katra p (p - pirmsskaitlis, p > 2) kvadrātisku rezīdiju skaits sakrīt ar kvadrātisku nerezīdiju skaitu. (t.i. tieši puse no atlikumiem ir tādi ka var izvilkt kvadrātsakni, bet no otras puses nevar).
Teorēma: Skaitļi 12, 22, 32, ..., ((p-1)/2)2 veido pilnu kvadrātisko rezīdiju ssitēmu pie moduļa p (p - pirmsskaitlis, p > 2).
Piemērs: ja p = 13, tad pilna kvadrātisko rezīdijusistēma ir (1, 4, 9, 3, 12, 10).
Citiem vārdiem, ja X2 a (mod p), tad ir atrisinājumi.
Izvēlamies pirmsskaitli, piemēram p = 97. Vai var noskaidrot
jautājumu, vai kongruencei X2 2 (mod 97) ir atrisinājums?
Pēc teorēmas X2 a (mod p) eksistē atrisinājums tutt.,
ja a(p-1)/2 1 (mod p).
X2 2 (mod 97) (a = 2, p = 97)
Vai 2(97 -1)/2 1 (mod 97) ?
248 1 (mod 97)
20 1 (mod 97)
21 2 (mod 97)
22 4 (mod 97)
24 16 (mod 97)
28 62 (mod 97)
216 61 (mod 97)
232 35 (mod 97)
248 = 232+16 61 * 35 1(mod 97)
Tātad pēc teorēmas eksistē atrisinājums.Mēs uzzinājām atrisinājuma eksistenci, bet ne pašu atrisinājumu.
Ležandra simboli ļauj atvieglot šādu uzdevumu atrisināšanu.
Ležandra simbolu īpašības:
Piemērs:
6*1 6
6 * 2 -7
6 * 3 -1
6 * 4 5
6 * 5 -8
6 * 6 -2
6 * 7 4
6 * 8 -9
6 * 9 -3
l = 6
