W niektórych przypadkach mamy potrzebę obliczenia wartości a mod n dla bardzo dużej liczby a. Tak dużej, że nie można jej przechowywać w zmiennej całkowitoliczbowej, a jedynie jako tekst. Nawet dla tak dużych liczb jesteśmy w stanie obliczyć wartość modulo. Tak wielką liczbę możemy podzielić na kilka mniejszych łańcuchów a następnie obliczać wartość modulo dla częsci od lewej do prawej strony, za każdym razem doklejając (łącząc łańcuchy) do kolejnej częsci wynik z poprzedniej. W ten sposób jesteśmy w stanie obliczyć wartość modulo dla praktycznie dowolnie dużej liczby wejściowej a. Algorytm zapisany w pseudokodzie wygląda następująco (założymy, że długość łańcuchów, na które dzielimy liczbę wejściową to 1), znak "+" oznacza tutaj łączenie łancuchów np: "1" + "2" = "12":

wynik = "";
for i=1 to length(a)
  begin
    wynik = wynik + a[i];
    wynik = wynik mod n;
  end;

Przykład
Obliczymy następującą wartość 1295302 mod 7
Bierzemy zatem pierwszą cyfrę z lewej i wykonujemy operacje modulo: 1 mod 7 = 1
Do wyniku z poprzedniego kroku dodajemy kolejną cyfrę (2) i dzielimy modulo: 12 mod 7 = 5
Dodajemy kolejną cyfrę (9) i znów dzielimy modulo: 59 mod 7 = 3
Do wyniku z poprzedniego kroku dodajemy kolejną cyfrę (5), wykonujemy kolejną operację modulo: 35 mod 7 = 0
Dodajemy kolejną cyfrę (3) i znów dzielimy modulo: 3 mod 7 = 3
Dodajemy kolejną cyfrę (0) i znów dzielimy modulo: 30 mod 7 = 2
Dodajemy kolejną cyfrę (2) i znów dzielimy modulo: 22 mod 7 = 1
Zatem ostateczny wynik to: 1295302 mod 7 = 1

Komentarze