In the function xsqrmodpow I pass the values ​​str [i], e, m. str - string. It works well with small numbers, the larger the numbers, the greater the likelihood of a module malfunctioning (e is generated randomly, but checked for mutual simplicity with phi (m)). It seems that the function is designed for long arithmetic and there should be no failures. For example, I enter 'L' (76), 121, 10515066833 at the input. 61470791 is returned.

Wolframlpha

Tungsten gives another value. Please tell me what could be the error?

uint64_t xsqrmodpow(uint64_t b, uint64_t X, uint64_t M) uint64_t B = b; uint64_t P = 1; while (X != 0) { if ((X & 1) == 1) { P = (P * B) % M; } B = (B * B) % M; X >>= 1; } return (uint64_t)P;
  • And what in the name of your function means "sqr", by the way? - Vladimir Martyanov
  • @ VladimirMartyanov exponentiation by squaring - Awethon
  • "It seems that the function is intended for long arithmetic and there should be no failures." - I do not see you even a hint of long arithmetic. uint64_t is a short number, not a long one. - Pavel Mayorov

1 answer 1

I think that, since you have about 10 10 M , then at some point, for example, B turns out to be about the same size. And its squaring leads to overflow . Or multiplication of P by B , since P can also be large and m at the same time as B Those. it will work correctly as long as M fits into uint32_t . What you noticed - the wrong job for large numbers.