tech. informacyjna potęga dyskretna

[kamilzielinski]

Witam,
Proszę o jakąkolwiek pomoc w rozwiązaniu zadania:

Aby móc obliczać wartości potęgi dyskretnej dla wysokich wykładników bez ryzyka przekroczenia zakresu liczb całkowitych można skorzystać z zależności:

a · b mod m = (a mod m) · (b mod m) mod m

Napisać program, który wypisze wyrazy \(2^n\) mod 13 dla n od 169 do 195.

[gpl1260]

Idea jest bardzo prosta. Zamiast obliczać wysoką potęgę i brać resztę z dzielenia wyniku przez coś, bierze się reszty już w trakcie mnożenia (a podana równość pokazuje, że da to ten sam efekt). Dzięki temu, jeśli liczysz a^n mod(m), nie pojawią się podczas obliczeń liczby większe od max(a^2,2m-2). W Twoim przypadku nie będzie liczb większych od 24, więc daleko nawet do podstawowego zakresu zmiennej całkowitej (32767, zdaje się).

Po prostu, zamiast pętli w której liczysz 2^n (x:=1, po czym x:=2x przebiega n razy) dajesz w kolejnych przebiegach działanie x:=(2x)mod(13).

[kamilzielinski]

A czy mógłbyś mi napisać ten program, jak to będzie wyglądało?