Поиск обратного элемента в простом поле
 

Есть поле вычетов по модулю простого числа. И есть число из этого поля. Надо найти обратный ему элемент. Я знаю, что для этого используется расширенный алгоритм Евклида. Может кто-нибудь знает что-нибудь побыстрее?

можно сделать поиск за константу :p (насколько я понимаю). Просто создаешь таблицу элементов поля, т.е. у тебя получается (1, a, a^2, a^3, a^4 и т.д.), затем дается элемент a^i, где i - любое, обратное к нему будет сообветственно a^(p-i), где p - размерность поля. Вроде так, или я чего-то не понял...

The_naked
Все правильно, но только расширенный алгоритм Евклида все равно быстрее (в случае одиночного поиска).

ну только в этом случае, частенько задача состоит в каком-то вычислении, а поле задано одно, и если оно (поле) не очень большое, то гораздо удобнее построить таблицу, потратив память, зато выигрываем в скорости очень сильно (аналог хэш таблиц, как я понимаю). Так а быстрее Евклида в общем случае что-нибудь существует? Кстати, есть усовершенствованные алгоритмы Евклида...

На практике часто приходилось находить (вручную) обратные для пятизначных и шестизначных чисел. Это в среднем 10-15 операций деления и соответственно обратный ход.
Чтобы составить таблицу, нужно гораздо больше операций. Разумеется, если постоянно использовать одно и тоже поле, и находить неоднократно в нем обратные, тогда соглашусь, что эффективнее провести некоторую подготовительную работу, составить таблицу и брать значения из нее.
Надо смотреть на конкретную задачу.
Насчет более усовершеннственных алгоритмов я не в курсе.

Наверное, мне не подойдет таблица: размерность поля - число в 256 бит, а обратные приходится находить для чисел бит в 100-150. В принципе, скорость алгоритма Евклида меня уже устраивает. Спасибо за ответы.