Mennyit ad maradekul 17-tel osztva a 43^11?

a^b mod c = (a^b1 mod c) * (a^b2 mod c) mod c, ha b=b1+b2

43^11 mod 17 = ((43 mod 17)*(43^5 mod 17)*(43^5 mod 17))mod 17

(43 mod 17)=9

43^5 mod 17=9*(43^2 mod 17)*(43^2 mod 17) mod 17

(43^2 mod 17)=(43 mod 17)^2 mod 17=81 mod 17 = 13

43^5 mod 17 = 9*13*13 mod 17 =16*9 mod 17 = 8

43^11 mod 17 = 9*8*8 mod 17 = (72 mod 17 * 8) mod 17 = 15

Szívesen.

Egyébként az RSA titkosító algoritmusbanak is része egy szám magas kitevőre emelni és ennek valamilyen osztási maradékát venni. Ezt gyakorlatba a gyors hatványozással implementálják, vagyis gyors hatványozást számol a gép adott maradékosztályon.Amire a fenti összefüggés teljesül.

A megoldás másképp:

43 = 9 (mod 17)

9^2 = -4 (mod 17)

9^3 = (-4)*9 = -2 (mod 17)

9^4 = (-2)*9 = -1 (mod 17)

Ebből látszik, hogy a 9 (azaz a 43) rendje 8 moduló 17, tehát:

9^11 = 9^3 = -2 (mod 17)

Gondolom, azt érted, miért nem baj, hogy nekem -2 jött ki, a kollégának meg 15. :)