algorytm.org

Naiwne potęgowanie modularne

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Naiwne potęgowanie modularne
Ocena użytkowników:***** / 5
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 14 listopada 2006 00:02

Powiedzmy, że chcemy obliczyć wartość ab mod n. Jak to zrobić, gdy wartość ab przekracza wartość mogącą pomieścić się w zmiennej całkowitoliczbowej?
Po pierwsze jeżeli a ≥ n to wówczas najpierw obliczymy wartość a mod n a następnie dopiero ją będziemy podnosić do potęgi b. Jeżeli a jest bardzo duże możemy posłużyć się operacją modulo na dużych liczbach.
Dalej zakładamy, że wynik jest równy 1, a następnie mnożymy go b razy przez a, przy czym po każdym mnożeniu wynik dzielimy modulo n.
W pseudo kodzie całą operację potęgowania modulo można zapisać następująco:

result = 1;
a = a mod n;
for i=1 to b do
  begin
    result = result * a;
    result = result mod n;
  end;

Schemat blokowy przedstawionego algorytmu wygląda następująco:
schemat blokowy - naiwne potęgowanie modularne


Matematycznie wygląda to tak:
ab mod n = (...(((a mod n) * a mod n) * a mod n) ...* a mod n)

Przykład:

Obliczmy 124 mod 7
A więc najpierw obliczymy 12 mod 7 = 5
Teraz wykonamy pierwsze mnożenie 1 * 5 = 5, wynik podzielimy modulo: 5 mod 7 = 5
Wynik z poprzedniego działania znów pomnożymy razy pięć. 5 * 5 = 25, wynik podzielimy modulo: 25 mod 7 = 4
Teraz wykonamy trzecie mnożenie 4 * 5 = 20, wynik podzielimy modulo: 20 mod 7 = 6
I w końcu czwarte mnożenie 6 * 5 = 30, wynik podzielimy modulo: 30 mod 7 = 2
Zatem ostateczny wynik to: 124 mod 7 = 2


Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 1
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 1
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 1
MarianC/C++C++
.cpp
.cpp
***** / 2
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 1
_marass_Php
.php
.php
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 maja 2010 22:31
Dodaj komentarz