How to calculate the value of such a “big” expression as 308 ^ 611 (mod 899).
Just doing the RSA algorithm in C ++. Perhaps a solution in mod n , but I do not understand? how to do it.

    1 answer 1

    You simply perform multiplications modulo, and for exponentiation you use fast exponentiation.

    Consider your case.

    689 = 1010110001

    Hence, 308 to the 689 degree is considered so (all actions modulo 899).

    308 ^ 2 = 469
    308 ^ 4 = 469 ^ 2 = 605
    308 ^ 8 = 605 * 605 = 132
    308 ^ 16 = 132 * 132 = 343

    The 16th degree corresponds to the second from the right unit in the binary representation, so now multiply 343 by 308 and we get 461 - this is 308 to the 17th degree modulo 899.

    Then we get 308 ^ 32, multiplying 343 * 343, multiply by our 461 ... Well, and so on. Is the idea clear?

    It looks like this in C ++:

     unsigned long long iqpow(unsigned long long x, unsigned long long e, unsigned long long p) { unsigned long long res = 1; for(x %= p;e;e>>=1) { if (e&1) res = (res*x)%p; x = (x*x)%p; } return res; } int main() { cout << iqpow(308,611,899) << endl; }
    • please explain - OneOrigiN
    • Well, I roughly painted. More or less clear? Once again - ALL multiplications are performed modulo 899, i.e., for example, 308 * 308 = 94864 = 899 * 105 + 469, so that 308 squared modulo 899 is 469. And quick exponentiation - see, for example here . - Harry
    • You gave me a tip, and I figured out with the help of you, Wikipedia and a piece of pencil ... You are smart but sometimes not attentive :) - OneOrigiN
    • better to connect the gmp library, created specifically for the "long" arithmetic - magrif