[D.....i]

#programowanie #cpp
Jak obliczyć duża liczbę podniesioną do potęgi, a potem wyliczyć z niej modulo?
Chodzi o coś takiego: (2441 ^ 79) % 3337
Kalkulator Windows radzi sobie bez problemu i daje 668, a wrzucenie czegoś takiego w kompilator

fmod(powl(2441, 79),3337)

daje 3128(w qt w ogóle wyrzuca 0 lub nieskończoność). Jestem świadomy tego, że to podniesienie do potęgi generuje bardzo dużą liczbę, ale ostateczny wynik jest normalny, więc jakoś powinno się dać.

[that_ugly_dude]

@DJ_Luki: dwa triki by zrobić to efektywnie: kolejne kwadraty i złożenie potęg oraz modulo wyników pośrednich https://math.stackexchange.com/a/195641

[A.....t]

@DJ_Luki: (2441 ^ 79) % 3337 = (((2441^2)^39 % 3337) \* 2441) % 3337

[Minemaniak1]

@DJ_Luki: Albo musisz napisać jakieś BigNumy (ew. uzyć jakiejś gotowej biblioteki), albo, jeśli chcemy to trzymać w typach wbudowanych, to poczytaj o szybkim potęgowaniu modulo, też da radę.

[ponton]

@DJ_Luki: poczytaj o RSA, tam muszą właśnie robić wielkie potęgi modulo

[D.....i]

@ponton: Właśnie do tego robię :D Ale nie widziałem nigdzie takiej implementacji w C++ ;) Już ogarnąłem to za pomocą szybkiego potęgowania modulo ;)