2021-10-07 15:10:41 +02:00
# Kryptografia
2021-10-28 16:35:59 +02:00
## Zajęcia 3
q losujemy i sprawdzamy czy p to liczba pierwsza
```
p = 2q + 1
losujemy p-1 -> liczba pierwsza
znajdujemy pewne g : < g > = fi(p)
losujemy 1 < x < p-1
obliczamy y = q
KA = (p, q, y) -> klucz publiczny
ka = (p, x) -> klucz tajny
losujemy 1 < k < p
obliczamy c1 = q^k (mod p)
obliczamy c2 = m * y^k (mod p)
deszyfrowanie było na mini-projekcie 1
```
2021-10-21 15:03:24 +02:00
## Zajecia2
### Twierdzenie Fermata
Małe twierdzenie Fermata mówi, że jeśli p jest liczbą pierwszą i a nie dzieli się przez p, to:
```
a ^ (p-1) === 1 (mod p)
```
Przystawanie modulo [link ](http://www.ftj.agh.edu.pl/~lenda/number_theory/A31.pdf ) Przykład dla p = 13:
```
a^12 - 1 = k * 13
k - całkowite
(3^12 -1 / 13) = k
k = 40880
k jest całkowite więc spełnia twierdzenie Fermata.
```
### Test pierwszości Fermata
[Link ](https://pl.wikipedia.org/wiki/Test_pierwszo%C5%9Bci_Fermata ), ogólniej [link ](https://pl.wikipedia.org/wiki/Test_pierwszo%C5%9Bci )
< br / >
a losujemy z zakresu od 1 do p - jeśli a nie będzie względnie pierwsze z p to znaczy że p nie jest liczbą pierwszą.
### Reszta kwadratowa modulo
[Link ](https://pl.wikipedia.org/wiki/Reszta_kwadratowa_modulo ), [przykład ](https://matematyka.pl/viewtopic.php?t=354543 ) twierdzenie jest w materiałach na Teams.
