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

11.3.1 Алгоритм Гельфонда

В настоящее время не известно полиномиальных алгоритмов дискретного логарифмирования в произвольной группе $ GF(q)*$. Мы изложим алгоритм А. О. Гельфонда, который применим к произвольной группе $ GF(q)*$ и имеет сложность $ O\left(q^{0{.}5+\varepsilon}\right)$     1. Положить $ H=[\sqrt q]+1$.

    2. Вычислить $ c=a^H$

    3. Построить наборы $ (c^u\,\vert\,u\in\{0,1,\ldots,H\})$ и $ (ba^v\,\vert\,v\in\{0,1,\ldots,H\})$ элементов $ GF(q)*$.

    4. Найти некоторый элемент, входящий в оба набора. Если $ c^u=ba^v$ -- такой элемент, то это значит, что $ a^{Hu-v}=b$ и $ \log b=(Hu-v)\bmod(q-1)$ -- искомый дискретный логарифм $ b$ по основанию $ a$.

Отметим, что любой элемент $ x\in\{0,1,\ldots,q-2\}$ представим в виде $ x=Hu-v$ при некоторых $ u,v\in\{0,1,\ldots,H\}$ (это следует из того, что $ x\leqslant q\leqslant H^2$). Поэтому элемент, входящий в оба набора из этапа 3 алгоритма, существует.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 11.3.2 Алгоритм Полига - Хеллмана Вверх: 11.3 Логарифмирование в GF(q)* Назад: 11.3 Логарифмирование в GF(q)*   Содержание   Предметный указатель

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