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


11.4 Логарифмирование в

В работе Райзела [Ries] изучаются свойства частных Ферма

$\displaystyle Q(x,r)=((x^{\lambda(r)}-1)/r)\bmod r, $

где $ x$ и $ r$ -- взаимно простые целые числа, $ r\geqslant 2$, а $ \lambda$ -- функция Кармайкла, определенная следующим образом. Если $ m=\prod\limits_{s\in\pi}s^{\alpha_s}$, где $ \pi$ -- конечное множество простых чисел, а $ \alpha_s\geqslant1$, то $ \lambda(m)$ есть наименьшее общее кратное чисел $ \lambda(s^{\alpha_s})$ при $ s\in\pi$, которые равны

$\displaystyle \lambda(s^{\alpha})=\begin{cases} 2^{\alpha-1},&\text{если }s=2\t... ...text{ и }\alpha\geqslant3;\\ s^{\alpha-1}(s-1),&\text{если }s\ne2. \end{cases}$

Нетрудно заметить, что $ \lambda(m)$ есть максимум порядков элементов группы $ \mathbb{Z}_m*$.

Основным свойством частных Ферма является следующая формула:

$\displaystyle Q(xy,r)\equiv(Q(x,r)+Q(y,r))\mkern5mu({\rm mod}\,\,r), $

аналогичная известному свойству логарифмической функции. Как оказалось, частные Ферма в некоторых случаях могут быть полезны для вычисления дискретных логарифмов. Так, в [Ries] показано, что когда $ n$ является $ \lambda$-низким (т. е. если $ n=2^{\alpha_0}p_1^{\alpha_1}\ldots p_s^{\alpha_s}$, где $ p_1,\ldots,p_s$ -- различные нечетные простые числа, а $ \alpha_i\geqslant1$, то $ \lambda(n)=2^{\alpha_0-2}p_1^{\alpha_1-1}\ldots p_s^{\alpha_s-1}u$, где $ u$ нечетно и не делится ни на одно из $ p_i$), вычисление логарифмов в $ \mathbb{Z}_n*$ в некоторых случаях может быть проведено быстро.

Изучение частных Ферма продолжено в работе Ю. В. Нестеренко [Нест], где доказано следующее утверждение.

Теорема.  Пусть $ r=2^{e_0}p_1^{e_1}\ldots p_t^{e_t}$, где $ p_1,\ldots,p_t$ -- различные нечетные простые числа, а $ \alpha_i\geqslant1$, -- $ \lambda$-низкое число, причем $ p_i-1\mid r$ для любого $ i=1,\ldots ,t$. Тогда     1) если $ n=2^{e_0+2}p_1^{e_1+1}\ldots p_t^{e_t+1}$, то из сравнения $ x\equiv y\mkern5mu({\rm mod}\,\,n)$ следует, что $ Q(x,r)=Q(y,r)$; это значит, что $ Q(\cdot,r)$ по существу является отображением $ \mathbb{Z}_n*\to\mathbb{Z}_r$;

    2) $ \lambda(n)=r$;

    3) существует элемент $ a\in\mathbb{Z}_n*$ порядка $ r$ (максимального порядка в группе $ \mathbb{Z}_n*$) такой, что $ Q(a,r)\in\mathbb{Z}_r*$.

Покажем, как вышеприведенная теорема позволяет эффективно находить дискретные логарифмы в группе $ \mathbb{Z}_n*$ по основанию $ a$ из п. 3 теоремы. Пусть $ b=a^x\bmod n$, где $ x\in\mathbb{Z}_r$. Тогда согласно основному свойству частных Ферма $ Q(b,r)\equiv xQ(a,r)\mkern5mu({\rm mod}\,\,r)$, откуда можно однозначно найти искомый дискретный логарифм $ x=Q(a,r)^{-1}Q(b,r)\bmod r$, так как $ Q(a,r)\in\mathbb{Z}_r*$. Отметим, что если $ b$ не является степенью $ a$ в группе $ \mathbb{Z}_n*$, то $ Q(a,r)^{-1}Q(b,r)\bmod r$ может принимать совершенно произвольные значения.

В той же работе [Нест] указан рекуррентный процесс построения по данному натуральному $ k$ числа $ r(k)$, удовлетворяющего условиям теоремы и такого, что $ k\mid r(k)$ и $ \log_2r(k)\leqslant3(\log_2k)^2$. Однако этот процесс требует разложения на простые множители некоторых чисел, что является вычислительно трудной задачей. Кроме того, в [Нест] с помощью частных Ферма показано, что если известно разложение $ n$ на простые множители, то задача дискретного логарифмирования в группе $ \mathbb{Z}_n*$ сводима за полиномиальное от $ \log n$ время к аналогичным задачам в группах $ \mathbb{Z}_p*$, где $ p$ пробегает множество простых делителей $ n$. В частности, если $ n$ гладкое (т. е. имеет только небольшие простые делители), то дискретные логарифмы в группе $ \mathbb{Z}_n*$ можно вычислять эффективно.

В [Kob, $ \mathsection$ 3, гл. 4, задача 2] предложен простой способ логарифмирования в циклической группе $ \mathbb{Z}_{3^k}*$; этот способ сводится к быстрому вычислению логарифма для $ k=i$ через логарифм для $ k=i-1$.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 11.5 Рекомендуемая литература Вверх: 11. Задача дискретного логарифмирования Назад: 11.3.5 Алгоритм Копперсмита   Содержание   Предметный указатель

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