Є два шляхи для вирішення цього завдання.
Шлях перший - використання розширеного алгоритму Евкліда.
Алгоритм Евкліда шукає НСД двох чисел. Розширений алгоритм Евкліда одночасно з цим становить НСД як целочисленную лінійну комбінацію вихідних чисел:
Як легко помітити, якщо A і C не є взаємно простими, то рішення немає, а якщо є - то коефіцієнт при A і буде шуканим зворотним елементом (для доказу можна замінити у формулі вище b на C і взяти обидві частини рівності по модулю C) .
Рекурсивний алгоритм досить простий. На черговому кроці більше з двох чисел (для визначеності, a) представляється як c + k ∙ b. після чого алгоритм викликається рекурсивно для (b, c):
Звідси маємо Ka = Kc1 і Kb = Kb1 - Kc1 ∙ k
Отримуємо приблизно такий алгоритм:
Ітеративний алгоритм настільки ж простий в реалізації, але складніше в розумінні. Найпростіше використовувати матриці. Для початку, слід записати перетворення коефіцієнтів в матричному вигляді:
Ці матричні множники можна буде накопичити:
Виходить наступний алгоритм:
Тепер, коли у нас є НОД, залишилося знайти НСД (A, C), перевірити що він дорівнює 1 і взяти (Ka% C) в якості шуканого зворотного числа.
Час роботи - близько log A по підставі φ ітерацій (це пов'язано з тим, що найгірший випадок для алгоритму Евкліда - сусідні числа Фібоначчі).
Шлях другий - використання формули Ейлера
Якщо число C заздалегідь відомо, чи є достатньо часу на підготовку, то можна скористатися формулою Ейлера:
Оскільки для мають нетривіальні загальні дільники A і C завдання рішення все одно не має - обмеження нам не завадить.
Відповідно до формули, відповіддю буде A ^ (φ (C) - 1)% C. Швидко знайти його можна за допомогою алгоритму швидкого зведення в ступінь:
Коректність цього алгоритму легко доводиться якщо зауважити що a ^ x * b - його інваріант.
Зрозуміло, після отримання відповіді треба буде перевірити що він правильний, якщо він буде невірним - значить, відповіді зовсім не існує (A і C мають загальні дільники).
Цей алгоритм буде працювати швидше ніж алгоритм Евкліда, тому що тут підстава логарифма більше, а самі ітерації - простіше. Але для застосування цього алгоритму потрібно заздалегідь знати φ (C)