Funkcja φ oraz algorytm szybkiego potęgowania. Michau: Oblicz φ(300) a następnie za pomocą algorytmu szybkiego potęgowania oblicz 311³⁵⁰ (mod 300)

jc: Policzyłeś φ(300)?

Michau:

	1		1		1
Tak φ(300) = 300(1−		)(1−		)(1−		) = 80
	2		3		5

jc: NWD(311,300) = NWD(11,300) = 1, dlatego 311⁸⁰ mod 300 = 1. Wykorzystaj ten fakt.

jc: 311³⁵⁰ ≡ 11³⁵⁰ = 11^4*80+30 ≡ 11³⁰ (mod 300) A teraz szybkie potęgowanie

Michau: Dzięki dalej już raczej sobie poradzę.