Potęgowanie modularne

Witam, poszukuje algorytmu który byłby wstanie policzyć wyniki działań typu
(6 454 353)^ 23 454 645 mod 111 113 346
Przeszukałem kilkanaście stron i niestety nie działają one poprawnie dla tak dużych liczb

Gotowca Ci nie dam, ale algorytm do przepisania na bigintach jest tu:
https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

Ten też nie daje rady ;)

python -> pow(6454353, 23454645,111113346) == 91026129L
I zapewniam że square and multiply działa dla tych danych.

def to_binary(x): return [int(c) for c in bin(x)[2:]]

def square_and_multiply_always(base, exponent, modulus):
    binary_exponent = to_binary(exponent)
    result = 1
    for di in binary_exponent:
        tmp = result * result
        t = [tmp, tmp * base]
        result = t[di] % modulus
    return result

aolo23 napisał(a):

Ten też nie daje rady ;)

Co nie Dajesz rady, Przepisz to, Dodaj typy i powinno hulać. Jak nie to Wrzuc na forum, zobaczymy. Nie mówiąc, że Jakbyś wybrał Pythonga, to jest w standarcie, jak pisze @Shalom :)

W Javie też śmiga:

System.out.println(new BigInteger("6454353").modPow(new BigInteger("23454645"), new BigInteger("111113346")));
>>91026129