algorytm na x^a mod n

Matma / algorytm na x^a mod n

Autor	Wiadomość
Filip	Posted: 16 Gru 2000 21:40:58 No wlasnie jak w temacie. Matematycy powinni cos wiedziec na ten temat. Teraz stosuje wielokrotne podnoszenie do kwadratu i za kazdym razem redukuje mod n, dziala nawet calkiem szybko, ale podobno istnieje algorytm ktory jest o wiele szybszy. Wymaga podobno konwersji reprezentacji liczby na cos dziwnego, a wtedy bardzo szybko oblicza reszte z potegowania modulo. Jesli ktos o tym slyszal to bede dziweczny... Fil
PiotrCF	Posted: 17 Gru 2000 16:54:11 Filip napisał: No wlasnie jak w temacie. Matematycy powinni cos wiedziec na ten temat. Teraz stosuje wielokrotne podnoszenie do kwadratu i za kazdym razem redukuje mod n, dziala nawet calkiem szybko, ale podobno istnieje algorytm ktory jest o wiele szybszy. Wymaga podobno konwersji reprezentacji liczby na cos dziwnego, a wtedy bardzo szybko oblicza reszte z potegowania modulo. Jesli ktos o tym slyszal to bede dziweczny... Poczytaj o tzw. kongruencjach i relacji "przystawania do" modulo <liczba. Mówimy, że dwie liczby a, b przystają do siebie modulo m, jeśli a mod m = b mod m. Własności (wszystkie modulo m): Jeśli (a przystaje do b) i (c przystaje do d) to (a+c przystaje do b+d) Jeśli (a przystaje do b) i (c przystaje do d) to (ac przystaje do bd) Wynika stąd, że aby policzyć np. 7^1024 mod 13, można zacząć od 7 mod 13 ("p.d." oznacza "przystaje do") 7 p.d. 7 7^2 p.d. 7^2 = 49 p.d. 10 7^4 p.d. (7^2)^2 p.d. 10^2 = 100 p.d. 9 7^8 p.d. (7^4)^2 p.d. 9^2 = 81 p.d. 3 ...itd. aż do 7^1024 p.d. 9 Czyli 7^1024 mod 13 = 9. A jak policzyć 7^1025 mod 13? Skoro mamy już 7^1024 mod 13 oraz 7^1 mod 13, to możemy skorzystać z własności o mnożeniu: 7^1025 p.d. (7^1024 * 7^1 ) p.d. 7*9 = 63 p.d. 11 Czyli 7^1025 mod 13 = 11 I już widać: trzeba zamienić 1025 na postać dwójkową, znaleźć 7^1 mod 13, ..., 7^1024 mod 13 i wymnożyć te wartości (reszty), które odpowiadają "jedynkom" w reprezentacji binarnej 1025. Piotr -- Zabezpieczenie antyspamowe: w moim adresie nie ma cyfr
PiotrCF	Posted: 17 Gru 2000 16:56:02 Filip napisał: No wlasnie jak w temacie. Matematycy powinni cos wiedziec na ten temat. Teraz stosuje wielokrotne podnoszenie do kwadratu i za kazdym razem redukuje mod n, dziala nawet calkiem szybko, ale podobno istnieje algorytm ktory jest o wiele szybszy. Wymaga podobno konwersji reprezentacji liczby na cos dziwnego, a wtedy bardzo szybko oblicza reszte z potegowania modulo. Jesli ktos o tym slyszal to bede dziweczny... Poczytaj o tzw. kongruencjach i relacji "przystawania do" modulo <liczba. Mówimy, że dwie liczby a, b przystają do siebie modulo m, jeśli a mod m = b mod m. Własności (wszystkie modulo m): Jeśli (a przystaje do b) i (c przystaje do d) to (a+c przystaje do b+d) Jeśli (a przystaje do b) i (c przystaje do d) to (ac przystaje do bd) Wynika stąd, że aby policzyć np. 7^1024 mod 13, można zacząć od 7 mod 13 ("p.d." oznacza "przystaje do") 7 p.d. 7 7^2 p.d. 7^2 = 49 p.d. 10 7^4 p.d. (7^2)^2 p.d. 10^2 = 100 p.d. 9 7^8 p.d. (7^4)^2 p.d. 9^2 = 81 p.d. 3 ...itd. aż do 7^1024 p.d. 9 Czyli 7^1024 mod 13 = 9. A jak policzyć 7^1025 mod 13? Skoro mamy już 7^1024 mod 13 oraz 7^1 mod 13, to możemy skorzystać z własności o mnożeniu: 7^1025 = (7^1024 * 7^1 ) p.d. 7*9 = 63 p.d. 11 Czyli 7^1025 mod 13 = 11 I już widać: trzeba zamienić 1025 na postać dwójkową, znaleźć 7^1 mod 13, ..., 7^1024 mod 13 i wymnożyć te wartości (reszty), które odpowiadają "jedynkom" w reprezentacji binarnej 1025. Piotr -- Zabezpieczenie antyspamowe: w moim adresie nie ma cyfr
Leszek Rybicki	Posted: 17 Gru 2000 21:41:47 Kolega wlasnie ta metode stosuje... Swoja droga - sam jestem ciekawy... moze ktos sie spotkal... Nie bez szacunku Leszek Rybicki
Marek Szyjewski	Posted: 29 Gru 2000 19:53:13 No wlasnie jak w temacie. Matematycy powinni cos wiedziec na ten temat. Teraz stosuje wielokrotne podnoszenie do kwadratu i za kazdym razem redukuje mod n, dziala nawet calkiem szybko, ale podobno istnieje algorytm ktory jest o wiele szybszy. Wymaga podobno konwersji reprezentacji liczby na cos dziwnego, a wtedy bardzo szybko oblicza reszte z potegowania modulo. Jesli ktos o tym slyszal to bede dziweczny... Fil W. Sierpinski "Arytmetyka teoretyczna", Rozdzial IV, paragraf 13. Pierwiastki pierwotne i wskazniki. Z powazaniem Marek Szyjewski My, samotnicy, powinnismy trzymac sie razem!


° Forum ° Odpowiedz ° Rejestracja ° Szukaj °