Нужно реализовать поиск обратного элемента для простого числа по операции mod N

Обратный это такой элемент Y для числа X по mod N 
при котором X*Y mod N =1

так вот я собственно перебором их искал начиная с 1 и проверял на выполнимость  X*Y mod N =1

- но при больших числах - например 2305843009213693951 или 618970019642690137449562111
такой метод не очень прокатывает - комп начинает задуууумываться ))

Кто что может подсказать по этому поводу? как быстренько найти обратный элемент простому числу?

хм... непомню, вроде где-то описывал, но не нашёл...

есть такая теорема, что для любых целых q и w есть два числа a,b: a*q+b*w=НОД(q,w)
идея в том, чтобы выбрать в качестве q выбрать X, а в качестве w - N
тогда a*X+b*N=НОД(X,N)
если НОД(X,N)=1, получаем:
a*X+b*N=1
если это всять по модулю N:
(a*X)mod N=1

т.е. здача нахождения обратного свелась к нахождению коэффециента a
тут смысл такой - использовать идею алгоритма Евклида для нахождения НОД, но "встроить" туда вычисление нужных коэффициентов:

есть у нас два числа q и w
будем считать, что q<w (иначе - поменять местами)
нам известно, что есть a и b:

a*q+b*w=1
дальше делаем преобразование:
a*q+b*(w-q+q)=1
a*q+b*(w-q)+b*q=1
(a+b)*q+b*(w-q)=1
мы получили другую задачу:
q1=q
w1=(w-q)
a1=a+b
b1=b
т.е. стоит нам решить задачу для q и (w-q), и мы найдём a1,b1, по которым можно найти a,b

в остальном алгоритм не отличается от исходного алгоритма Евклида: просто продолжаем, а аргументы постепенно уменьшаются, пока один из них не станет равен 1, для этого случая задача тривиальна:
a*qn+b*1=1 =>a=0, b=1

И в более "программном" виде, тот же расширенный алгоритм Евклида: