Mam problem.
Jak możemy znaleźć najmniejszą wartość \(\displaystyle{ x}\) spełniającą równanie \(\displaystyle{ x^2 = a \pmod c}\)?
\(\displaystyle{ a}\) i \(\displaystyle{ c}\) są dane. \(\displaystyle{ c}\) jest liczbą złożoną.
Korzystałem z algorytmu Tonelli-Shanks i Chińskiego Twierdzenia o Resztach ale tam niestety potrafi się przytrafić, że obliczone \(\displaystyle{ x}\) nie jest najmniejsze.
Ma ktoś może jakąś koncepcję jak można to dość szybko zrobić?
Proszę ewentualnie o przeniesienie wątku do odpowiedniego działu - nie miałem pewności gdzie jego dodać.
Jak znaleźć najmniejszą wartość x spełniającą równanie...
-
Morfeo
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Re: Jak znaleźć najmniejszą wartość x spełniającą równanie..
Już piszę.
Przyjmujmy, że szukamy rozwiązania: \(\displaystyle{ x^2 \equiv 1024 \pmod{1302}}\).
Musimy znać rozkład na czynniki pierwsze \(\displaystyle{ 1302}\), a więc \(\displaystyle{ 1302 = 2 \cdot 3 \cdot 7 \cdot 31}\).
Teraz za pomocą algorytmu Tonelli-Shanks obliczamy sobie dla wszystkich dzielników:
Dla 2:
\(\displaystyle{ 1024 \equiv k_1 \pmod 2}\).
\(\displaystyle{ k_1 = 0}\)
\(\displaystyle{ x_1^2 \equiv k_1 \pmod{2}}\).
\(\displaystyle{ x_1^2 \equiv 0 \pmod{2}}\)
\(\displaystyle{ x_1 = 0}\)
Dla 3:
\(\displaystyle{ 1024 \equiv k_2 \pmod 3}\).
\(\displaystyle{ k_2 = 1}\)
\(\displaystyle{ x_2^2 \equiv k_1 \pmod{3}}\).
\(\displaystyle{ x_2^2 \equiv 1 \pmod{3}}\)
\(\displaystyle{ x_2 = 1}\)
Dla 7:
\(\displaystyle{ 1024 \equiv k_3 \pmod 7}\).
\(\displaystyle{ k_3 = 2}\)
\(\displaystyle{ x_3^2 \equiv k_3 \pmod{7}}\).
\(\displaystyle{ x_3^2 \equiv 2 \pmod{7}}\)
\(\displaystyle{ x_3 = 4}\)
Dla 31:
\(\displaystyle{ 1024 \equiv k_4 \pmod 31}\).
\(\displaystyle{ k_4 = 1}\)
\(\displaystyle{ x_4^2 \equiv k_4 \pmod{31}}\).
\(\displaystyle{ x_4^2 \equiv 1 \pmod{31}}\)
\(\displaystyle{ x_4 = 1}\)
Następnie rozwiązujemy układ równań z Chińskiego Twierdzenia o Resztach.
Znamy czynniki pierwsze i także już wartości \(\displaystyle{ x}\) z formuły: \(\displaystyle{ x^2 \equiv c \pmod{p}}\), gdzie \(\displaystyle{ p}\) i \(\displaystyle{ c}\) są znane.
Rozwiązujemy układ równań.
\(\displaystyle{ x \equiv 0 \pmod{2}}\)
\(\displaystyle{ x \equiv 1 \pmod{3}}\)
\(\displaystyle{ x \equiv 4 \pmod{7}}\)
\(\displaystyle{ x \equiv 1 \pmod{31}}\)
Z Chińskiego Twierdzenia o Resztach wychodzi \(\displaystyle{ x = 32}\) i to się niby w tym przypadku zgadza, ponieważ \(\displaystyle{ 32^2 \equiv 1024 \pmod{1302}}\) - dość trywialny przypadek.
Problem jednak polega na tym, że nie zawsze się to zgodzi.
A otóż już piszę dlaczego.
W powyższym przypadku przykładowo dla czynnika pierwszego \(\displaystyle{ 31}\) przyjąłem, że znalazłem wynik, równy \(\displaystyle{ 1}\). Nie koniecznie jednak muszę znaleźć dokładnie \(\displaystyle{ 1}\), ponieważ także:
\(\displaystyle{ (31-1)^2 \equiv k_4 \pmod{31}}\)
\(\displaystyle{ (31-1)^2 \equiv 1 \pmod{31}}\)
\(\displaystyle{ 30^2 \equiv 1 \pmod{31}}\)
Powyżej widać, że dla \(\displaystyle{ 30}\) także będzie \(\displaystyle{ 1}\).
Natomiast dla takiego układu równań (nowa wartość przy \(\displaystyle{ 31}\)):
\(\displaystyle{ x \equiv 0 \pmod{2}}\)
\(\displaystyle{ x \equiv 1 \pmod{3}}\)
\(\displaystyle{ x \equiv 4 \pmod{7}}\)
\(\displaystyle{ x \equiv 30 \pmod{31}}\)
Z Chińskiego Twierdzenia o Resztach otrzymujemy już \(\displaystyle{ x = 2944}\). To także się zgadza, ponieważ \(\displaystyle{ 2944^2 \equiv 1024 \pmod{1302}}\) ale to już nie jest najmniejsza wartość.
Znając pierwszą wartość, drugą która pasuje można już prosto obliczyć tak jak tutaj to zrobiłem.
Co jednak z tego skoro wszystkich kombinacji wartości będzie \(\displaystyle{ 2^k}\) (gdzie \(\displaystyle{ k}\) to ilość czynników pierwszych (w przykładzie różnych)). Nie znalazłem metody aby zrobić jakiś przesiew tych kombinacji lepszym sposobem niż brutal-force.
Jakieś pomysłu na to więc poszukuję.
Ktoś może coś podpowie?
Przyjmujmy, że szukamy rozwiązania: \(\displaystyle{ x^2 \equiv 1024 \pmod{1302}}\).
Musimy znać rozkład na czynniki pierwsze \(\displaystyle{ 1302}\), a więc \(\displaystyle{ 1302 = 2 \cdot 3 \cdot 7 \cdot 31}\).
Teraz za pomocą algorytmu Tonelli-Shanks obliczamy sobie dla wszystkich dzielników:
Dla 2:
\(\displaystyle{ 1024 \equiv k_1 \pmod 2}\).
\(\displaystyle{ k_1 = 0}\)
\(\displaystyle{ x_1^2 \equiv k_1 \pmod{2}}\).
\(\displaystyle{ x_1^2 \equiv 0 \pmod{2}}\)
\(\displaystyle{ x_1 = 0}\)
Dla 3:
\(\displaystyle{ 1024 \equiv k_2 \pmod 3}\).
\(\displaystyle{ k_2 = 1}\)
\(\displaystyle{ x_2^2 \equiv k_1 \pmod{3}}\).
\(\displaystyle{ x_2^2 \equiv 1 \pmod{3}}\)
\(\displaystyle{ x_2 = 1}\)
Dla 7:
\(\displaystyle{ 1024 \equiv k_3 \pmod 7}\).
\(\displaystyle{ k_3 = 2}\)
\(\displaystyle{ x_3^2 \equiv k_3 \pmod{7}}\).
\(\displaystyle{ x_3^2 \equiv 2 \pmod{7}}\)
\(\displaystyle{ x_3 = 4}\)
Dla 31:
\(\displaystyle{ 1024 \equiv k_4 \pmod 31}\).
\(\displaystyle{ k_4 = 1}\)
\(\displaystyle{ x_4^2 \equiv k_4 \pmod{31}}\).
\(\displaystyle{ x_4^2 \equiv 1 \pmod{31}}\)
\(\displaystyle{ x_4 = 1}\)
Następnie rozwiązujemy układ równań z Chińskiego Twierdzenia o Resztach.
Znamy czynniki pierwsze i także już wartości \(\displaystyle{ x}\) z formuły: \(\displaystyle{ x^2 \equiv c \pmod{p}}\), gdzie \(\displaystyle{ p}\) i \(\displaystyle{ c}\) są znane.
Rozwiązujemy układ równań.
\(\displaystyle{ x \equiv 0 \pmod{2}}\)
\(\displaystyle{ x \equiv 1 \pmod{3}}\)
\(\displaystyle{ x \equiv 4 \pmod{7}}\)
\(\displaystyle{ x \equiv 1 \pmod{31}}\)
Z Chińskiego Twierdzenia o Resztach wychodzi \(\displaystyle{ x = 32}\) i to się niby w tym przypadku zgadza, ponieważ \(\displaystyle{ 32^2 \equiv 1024 \pmod{1302}}\) - dość trywialny przypadek.
Problem jednak polega na tym, że nie zawsze się to zgodzi.
A otóż już piszę dlaczego.
W powyższym przypadku przykładowo dla czynnika pierwszego \(\displaystyle{ 31}\) przyjąłem, że znalazłem wynik, równy \(\displaystyle{ 1}\). Nie koniecznie jednak muszę znaleźć dokładnie \(\displaystyle{ 1}\), ponieważ także:
\(\displaystyle{ (31-1)^2 \equiv k_4 \pmod{31}}\)
\(\displaystyle{ (31-1)^2 \equiv 1 \pmod{31}}\)
\(\displaystyle{ 30^2 \equiv 1 \pmod{31}}\)
Powyżej widać, że dla \(\displaystyle{ 30}\) także będzie \(\displaystyle{ 1}\).
Natomiast dla takiego układu równań (nowa wartość przy \(\displaystyle{ 31}\)):
\(\displaystyle{ x \equiv 0 \pmod{2}}\)
\(\displaystyle{ x \equiv 1 \pmod{3}}\)
\(\displaystyle{ x \equiv 4 \pmod{7}}\)
\(\displaystyle{ x \equiv 30 \pmod{31}}\)
Z Chińskiego Twierdzenia o Resztach otrzymujemy już \(\displaystyle{ x = 2944}\). To także się zgadza, ponieważ \(\displaystyle{ 2944^2 \equiv 1024 \pmod{1302}}\) ale to już nie jest najmniejsza wartość.
Znając pierwszą wartość, drugą która pasuje można już prosto obliczyć tak jak tutaj to zrobiłem.
Co jednak z tego skoro wszystkich kombinacji wartości będzie \(\displaystyle{ 2^k}\) (gdzie \(\displaystyle{ k}\) to ilość czynników pierwszych (w przykładzie różnych)). Nie znalazłem metody aby zrobić jakiś przesiew tych kombinacji lepszym sposobem niż brutal-force.
Jakieś pomysłu na to więc poszukuję.
Ktoś może coś podpowie?