Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
  Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 11.3 Логарифмирование в GF(q)* Вверх: 11. Задача дискретного логарифмирования Назад: 11.1 Введение   Содержание   Предметный указатель


11.2 Постановка задачи

Пусть $ G$ -- некоторая мультипликативно записываемая группа, а $ a$ и $ b$ -- некоторые элементы группы $ G$, связанные равенством $ b=a^n$ при некотором целом $ n$. Любое целое $ x$, удовлетворяющее уравнению $ b=a^x$, называется дискретным логарифмом элемента $ b$ по основанию $ a$. Задача дискретного логарифмирования в группе $ G$ состоит в отыскании по данным $ a$ и $ b$ вышеуказанного вида (при этом $ a$ может быть или не быть фиксированным) некоторого дискретного логарифма $ b$ по основанию $ a$. Если $ a$ имеет бесконечный порядок, то дискретный логарифм любого элемента по основанию $ a$ определен однозначно. В противном случае все дискретные логарифмы $ b$ по основанию $ a$ можно получить из некоторого такого дискретного логарифма $ x_0$ по формуле $ x=x_0+km$, где $ m$ -- порядок элемента $ a$, а параметр $ k$ пробегает $ \mathbb{Z}$.

Для криптографических приложений наиболее важна задача дискретного логарифмирования в мультипликативных группах конечных полей $ GF(q)$ и колец $ \mathbb{Z}_n$. Эти группы мы будем обозначать, как обычно, через $ GF(q)*$ и $ \mathbb{Z}_n*$ соответственно. Как хорошо известно, группа $ GF(q)*$ циклическая и имеет порядок $ q-1$, поэтому если в качестве $ a$ берется некоторый порождающий этой группы, то дискретный логарифм любого элемента $ GF(q)*$ по основанию $ a$ существует и определен однозначно по модулю $ q-1$. Отметим, что если мы умеем логарифмировать по фиксированному основанию, которое является порождающим $ g$ группы $ GF(q)*$, то можно находить дискретные логарифмы по произвольному основанию. Действительно, чтобы найти дискретный логарифм $ x$ элемента $ b$ по основанию $ a$, достаточно вычислить дискретные логарифмы $ y$ и $ z$ элементов $ a$ и $ b$ соответственно по основанию $ g$ и решить уравнение $ xy\equiv z\mkern5mu({\rm mod}\,\,q-1)$ относительно $ x$.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 11.3 Логарифмирование в GF(q)* Вверх: 11. Задача дискретного логарифмирования Назад: 11.1 Введение   Содержание   Предметный указатель


Проект осуществляется при поддержке:
Геологического факультета МГУ,
РФФИ
   
TopList Rambler's Top100