Поиск обратного в Z/p где p - простое (большое простое)

Про современные процессоры ничего не знаю, но сильно сомневаюсь, есть ли принципиально более быстрый алгоритм. Помнится, когда методом Евклида ищут НОД(n,p), то заодно на халяву находят такие a и b, что an+bp=1. Но это то же самое (при не малых n) - там порядка log p умножений, здесь - делений, один чёрт.

Выведена формула получения простых чисел
http://www.laplas.narod.ru/moiform.htm

пункт №4

где k целое число от 1 до бесконечности. Выражение в скобках ограниченных снизу обозначает целую часть дроби k/6, либо само значение этой дроби если k кратно 6, ну а функция n=[(k-1)mod(6)] и n=[(k)mod(6)] вам я надеюсь знакома - сравнимость чисел n и k-1, k по модулю 6.
Эта формула даёт все простые числа по порядку начиная с 5. Так же по этой формуле получаются составные числа. Общая доля отсева равна 11/15=0.73333(3).