Witam
Mam pytanie jakie zastosowanie ma prawo wzajemności reszt kwadratowych? Czy służy tylko do obliczania czy liczba jest czy nie resztą kwadratową czy ma jeszcze jakieś inne ciekawe zastosowania?
Prawo wzajemności reszt kwadratowych
-
jadziaaa_123
- Użytkownik
- Posty: 11
- Rejestracja: 12 kwie 2012, o 14:35
- Płeć: Kobieta
- Lokalizacja: Wrocław
-
eMaerthin
- Użytkownik
- Posty: 40
- Rejestracja: 12 paź 2011, o 19:03
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 10 razy
Prawo wzajemności reszt kwadratowych
Cześć jadziaaa_123,
prawo wzajemności reszt kwadratowych ma zastosowanie do szybkiego obliczania czy liczba jest resztą kwadratową. A po co? Dlatego chociażby, że niektóre algorytmy wymagają do prawidłowego działania podania jakiejś reszty kwadratowej mod n, np. w kryptografii do generowania kluczy
Algorytm Williamsa (H. C. Williams 1985 rok) potrzebuje niereszty kwadratowej, zaś probabilistyczny algorytm Bluma-Goldwassera podczas szyfrowania szuka reszt kwadratowych
Z innej strony, gdy szukamy generatora grupy \(\displaystyle{ \mathbb{Z}_p, p\in\mathbb{P}}\), no to generator taki na pewno jest nieresztą kwadratową mod n, bo prawdziwe jest stwierdzenie:
\(\displaystyle{ a^{\frac{p-1}{2}}\equiv\left( \frac{a}{p}\right) \pmod{p}}\) (a generator \(\displaystyle{ g}\) musi spełniać \(\displaystyle{ g^{k}\not\equiv1\pmod{n}}\) dla każdego \(\displaystyle{ k<}\)rząd\(\displaystyle{ (n)}\))
prawo wzajemności reszt kwadratowych ma zastosowanie do szybkiego obliczania czy liczba jest resztą kwadratową. A po co? Dlatego chociażby, że niektóre algorytmy wymagają do prawidłowego działania podania jakiejś reszty kwadratowej mod n, np. w kryptografii do generowania kluczy
Algorytm Williamsa (H. C. Williams 1985 rok) potrzebuje niereszty kwadratowej, zaś probabilistyczny algorytm Bluma-Goldwassera podczas szyfrowania szuka reszt kwadratowych
Z innej strony, gdy szukamy generatora grupy \(\displaystyle{ \mathbb{Z}_p, p\in\mathbb{P}}\), no to generator taki na pewno jest nieresztą kwadratową mod n, bo prawdziwe jest stwierdzenie:
\(\displaystyle{ a^{\frac{p-1}{2}}\equiv\left( \frac{a}{p}\right) \pmod{p}}\) (a generator \(\displaystyle{ g}\) musi spełniać \(\displaystyle{ g^{k}\not\equiv1\pmod{n}}\) dla każdego \(\displaystyle{ k<}\)rząd\(\displaystyle{ (n)}\))