Подскажите, пожалуйста, есть ли в классе CBigNumber средства для выполнения нахождения обратного элемента в кольце вычетов? Или его можно найти только используя стандартный алгоритм?
Raul 12.11.2005 13:25
Если я правильно понял задачу, то она решается в лоб возведением числа в степень n-1 по модулю n (для простого n). Такая операция в классе есть, но вот насколько она эффективна по сравнению алгоритмом Евклида? Можно запрограммировать и сравнить.
Анонимно 14.11.2005 16:37
В общем случае решается возведением числа в степень y(n) (где y(n) - функция Эйлера, y(n)=n-1 для простого числа, для сложных чисел свои правила вычисления y(n)) по модулю n. Вот и хотелось узнать, есть ли в классе метод для любых чисел (не только простых). Наверно, запрограммирую Евклида.
