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

rendal1 · 28.01.2006, 14:47

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

Naked · 28.01.2006, 16:04

можно сделать поиск за константу

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

Trotil · 28.01.2006, 17:24

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

Naked · 28.01.2006, 19:37

Цитата:

Trotil:
в случае одиночного поиска

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

Trotil · 28.01.2006, 20:06

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

rendal1 · 29.01.2006, 20:20

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

28.01.2006, 14:47	# 1
rendal1 Junior Member Регистрация: 14.12.2005 Адрес: Саратов Сообщения: 62	Поиск обратного элемента в простом поле Есть поле вычетов по модулю простого числа. И есть число из этого поля. Надо найти обратный ему элемент. Я знаю, что для этого используется расширенный алгоритм Евклида. Может кто-нибудь знает что-нибудь побыстрее?

28.01.2006, 16:04	# 2
Naked ::VIP:: Регистрация: 15.05.2005 Адрес: Питер Сообщения: 1 194	можно сделать поиск за константу (насколько я понимаю). Просто создаешь таблицу элементов поля, т.е. у тебя получается (1, a, a^2, a^3, a^4 и т.д.), затем дается элемент a^i, где i - любое, обратное к нему будет сообветственно a^(p-i), где p - размерность поля. Вроде так, или я чего-то не понял... __________________ Чтобы воля стала действующим началом, тело должно быть совершенным.

28.01.2006, 17:24	# 3
Trotil Advanced Member Регистрация: 21.04.2005 Адрес: град Москва Сообщения: 431	The_naked Все правильно, но только расширенный алгоритм Евклида все равно быстрее (в случае одиночного поиска).

28.01.2006, 20:06	# 5
Trotil Advanced Member Регистрация: 21.04.2005 Адрес: град Москва Сообщения: 431	На практике часто приходилось находить (вручную) обратные для пятизначных и шестизначных чисел. Это в среднем 10-15 операций деления и соответственно обратный ход. Чтобы составить таблицу, нужно гораздо больше операций. Разумеется, если постоянно использовать одно и тоже поле, и находить неоднократно в нем обратные, тогда соглашусь, что эффективнее провести некоторую подготовительную работу, составить таблицу и брать значения из нее. Надо смотреть на конкретную задачу. Насчет более усовершеннственных алгоритмов я не в курсе.

29.01.2006, 20:20	# 6
rendal1 Junior Member Регистрация: 14.12.2005 Адрес: Саратов Сообщения: 62	Наверное, мне не подойдет таблица: размерность поля - число в 256 бит, а обратные приходится находить для чисел бит в 100-150. В принципе, скорость алгоритма Евклида меня уже устраивает. Спасибо за ответы.