Algorytm potegowania modularnego

0

Czy ktos potrafi podac algorytm potegowania modularnego w c/c++??
[email protected]

0

Tak

0

johny_brawo to jak potrafisz to podaj!

0

jaki wujek?

0

Wujek, wujek google, wcisnij ten tekst podswietlony jako link (takie cos wykorzystywane czasem na stronach www), to Cie przeniesie do strony wyszukiwania google'a z odpowiedzia na Twoje pytanie... [glowa]

0

Już przy mnożeniu pojawia się problem, gdy korzystamy z 64 bitowych liczb.
Pośrednie obliczenia mają 128 bitów, mam tu ciekawą sztuczkę:

 //float64 to zmienny przecinek z 64 bitową mantysą, long double
        uint64 mul_mod(uint64 a, uint64 b, uint64 m) {
        uint64 y = (uint64)((float64)a*(float64)b/m+(float64)1/2); // floor(a*b/m)
        y = y * m;                // m*floor(a*b/m) mod z
        uint64 x = a * b;         // a*b mod z
        uint64 r = x - y;         // a*b mod z - m*floor(a*b/m) mod z
        if ( (int64)r < 0 ) {     // normalization needed ?
                r = r + m;
                y = y - 1;        // (a*b)/m quotient, omit line if not needed
        }
        return r;                 // (a*b)%m remnant
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1