algorytm.org

Implementacja w Delphi/Pascal

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?

Szybkie potęgowanie modularne - Implementacja w Delphi/Pascal
Ocena użytkownikóww: *****  / 4
SłabyŚwietny
Nadesłany przez Tomasz Lubiński, 13 listopada 2006 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

spm delphi/spm.dpr:
//
// Szybkie Potegowanie modulo
//
// www.algorytm.org
// (c)2006 Tomasz Lubinski
//

program spm;
{$APPTYPE CONSOLE}
uses
  SysUtils;

// calculates a^b mod m
function power_modulo_fast(a: Integer; b: Integer; m: Integer): Integer;
var
   i: Integer;
   x: Int64;
begin
   result := 1;
   x := a mod m;

   i := 1;
   while (i<=b) do
      begin
         x := x mod m;
         if ((b and i) <> 0) then
            begin
               result := (result * x) mod m;
            end;
         x := x * x;
         i := i shl 1;
      end;
end;

begin
   //9688563^45896 mod 71 = 30
   writeln('9688563^458926 mod 71 = ' + IntToStr(power_modulo_fast(9688563, 458926, 71)));

   //12^53 mod 7 = 3
   writeln('12^53 mod 7 = ' + IntToStr(power_modulo_fast(12, 53, 7)));
end.
Dodaj komentarz