Wysokie potęgi Benny: Da się jakoś szybko policzyć 32¹³(mod 119)?

Benny: Dobra jednak mam

jc: Tak, a=32 a², a⁴, a⁸, (a⁸)*(a⁴)*a, 5 mnożeń, każde modulo 119. Poniżej masz funkcję w Pythonie, która liczy x^t mod n. W Pythonie można używać dowolnie długich liczb całkowitych, więc n może mieć kilkaset cyfr. def pot(x, t, n): y = 1 while t > 0: if t&1: y = (x*y) % n x = (x*x) % n t = t>>1 return y

Adamm: 32¹³≡32*1024⁶≡32*72⁶≡32*5184³≡32*67³≡32*67*67²≡32*67*86≡15*67≡53 (mod 119)

Benny: Funkcje sam pisałem w C++, ale zastanawiam się jak to będzie się liczyło na egzaminie

Adamm: na kalkulatorze

Benny: Właśnie nie jestem pewny czy będzie można używać

Benny: Ok, gdzie mam błąd? 53³⁷(mod 119) 53² (mod 119)=72 53⁵ (mod 119)=100 (53⁵)⁷*53²=100⁷*72 100⁷=18 18*72 (mod 119)=106

Adamm: 100⁷≡₁₁₉ 93 93*72 ≡₁₁₉ 32

Benny: Ok, znalazłem błąd

Mariusz: a suwak daje gorsze przybliżenie , inaczej nie przegrałby z kalkulatorem bo do kalkulatora potrzebne jest zasilanie Poza tym nie wiem czy pozwoliliby na suwak