Необходимо вычислить мультипликативно обратное к некому числу e по модулю ph. e - простое число, ph - результат функции Эйлера от некого числа. В примере e = 65537; ph = 3616319324. Заранее вычисленное верное значение - 2373062985. Своими силами и с помощью интернета я написал несколько функций для получения этого числа. Функции, использующие расширенный алгоритм Эйлера выдают одинаковый неверный результат, близкий к максимально возможному типа переменной. Функция, основанная на теореме Эйлера также выдает неверный результат, но отличный от предыдущих. В чем здесь может быть проблема?
#include <iostream>
#include <tuple>
#include <vector>
uint32_t xgcd1(uint32_t a, uint32_t b, uint64_t& x, uint64_t& y) {
x = 1, y = 0;
uint64_t x1 = 0, y1 = 1;
uint32_t a1 = a, b1 = b;
while (b1) {
int q = a1 / b1;
std::tie(x, x1) = std::make_tuple(x1, x - q * x1);
std::tie(y, y1) = std::make_tuple(y1, y - q * y1);
std::tie(a1, b1) = std::make_tuple(b1, a1 - q * b1);
}
return a1;
}
uint32_t xgcd2(uint32_t a, uint32_t b, uint64_t& x, uint64_t& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
uint64_t x1{}, y1{};
uint32_t gcd = xgcd2(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return gcd;
}
std::vector<int64_t> euler(uint32_t x, uint32_t y) {
std::vector<int64_t> modInverse(x + 1, 0);
modInverse[1] = 1;
for (int64_t i = 2; i <= x; i++) {
modInverse[i] = (-(y / i) * modInverse[y % i]) % y + y;
}
return modInverse;
}
int main() {
unsigned long ph = 3616319324;
unsigned long e = 65537;
uint64_t res1{}, y{};
xgcd1(e, ph, res1, y);
uint64_t res2{};
xgcd2(e, ph, res2, y);
uint64_t res3 = euler(e, ph)[e];
std::cout << "e: " << e << '\n';
std::cout << "ph: " << ph << '\n';
std::cout << "right result: 2373062985\n";
std::cout << "res1 xgcd iterative: " << res1 << '\n';
std::cout << "res2 xgcd: " << res2 << '\n';
std::cout << "res3 euler: " << res3 << '\n';
return 0;
}
int q = a1 / b1;
???y - q * y1
могут быть отрицательными. А вы их вычисляете в беззнаковой арифметике.