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
0
0
Gotowca Ci nie dam, ale algorytm do przepisania na bigintach jest tu:
https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
0
Ten też nie daje rady ;)
0
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
0
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 :)
3
W Javie też śmiga:
System.out.println(new BigInteger("6454353").modPow(new BigInteger("23454645"), new BigInteger("111113346")));
>>91026129