Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13.7.2 Алгоритм Вверх: 13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма" Назад: 13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма"   Содержание   Предметный указатель

13.7.1 Общетеоретические обоснования

Основную часть алгоритма можно описать следующим образом. Предположим, что как-то удалось построить простое число $ q$ и требуется построить еще большее простое число $ p$. Это большее число ищется в виде

$\displaystyle p=2kq+1,\qquad k\in\mathbb{Z},\ k\geqslant 1.$ (1)

Можно, выбирая как-либо целые числа $ k$, тестировать появляющиеся числа $ p$ на простоту, например, с помощью тестов, использующих знание частичного разложения $ p-1$ на множители (см. раздел. 13.5). Для этого нужно, чтобы число $ k$, разложение которого на простые множители, вообще говоря, считается неизвестным, было не очень большим по сравнению с $ q$, скажем $ k\leqslant f(q)$, где возрастающая не очень быстро функция $ f(q)$ описывается в соответствующем тесте. Конструкция $ p$, естественно, должна быть не уникальной, а обеспечивать получение достаточно большого количества простых чисел в прогрессии $ 2kq+1$. Это достигается случайным выбором начала отсчета -- четного числа $ N$ на промежутке $ 1<N<f(q)$, перебором чисел $ 2k=N,N+2,\ldots$ и последующим тестированием на простоту. Мы сейчас коротко обсудим теоретические основы такого метода построения простых чисел.

Прежде всего, согласно теореме Дирихле, доказанной еще в 1839 г., прогрессия (1) содержит бесконечное количество простых чисел. Нас интересуют простые числа, лежащие недалеко от начала прогрессии, ведь согласно условиям тестирования должно выполняться ограничение $ k\leqslant f(q)$. Оценка наименьшего простого числа в арифметической прогрессии была получена еще в 1944 г. Ю. В. Линником. Она утверждает, что существует абсолютная постоянная $ C$ такая, что наименьшее простое число в прогрессии (1) не превосходит $ q^C$. Постоянная $ C$ очень велика, заведомо выполняется неравенство $ f(q)<q^{C-1}$. В предположении расширенной гипотезы Римана о нулях L-функций Дирихле можно доказать (см. [Прах], с. 272), что при любом $ \varepsilon>0$ наименьшее простое число в прогрессии (1) не превосходит $ c(\varepsilon)\cdot q^{2+\varepsilon}$. Таким образом, в настоящее время никаких теоретических гарантий для существования простого числа (1) с $ k<f(q)$ не существует. Тем не менее опыт вычислений на ЭВМ показывает, что простые числа в прогрессии встречаются достаточно близко к ее началу. Упомянем в этой связи гипотезу о существовании бесконечного количества простых чисел $ q$ с условием, что число $ 2q+1$ также простое (уже первый член прогрессии (1) есть простое число).

Очень важен в связи с описываемым методом построения простых чисел также вопрос о расстоянии между соседними простыми числами в арифметической прогрессии. Ведь если это расстояние велико, нет надежды обеспечить построение большого количества простых $ p$. Перебор чисел $ 2k\geqslant N$ до того момента, как мы наткнемся на простое $ p$, окажется слишком долгим. В более простом вопросе о расстоянии между соседними простыми числами $ p_n$ и $ p_{n-1}$ в натуральном ряде доказано лишь, что $ p_{n+1}-p_n=O\left(p_n^{38/61+\varepsilon}\right)$, что, конечно же, слишком велико для наших целей. Вместе с тем, существует так называемая гипотеза Крамера (1936 г.), что $ p_{n+1}-p_n=O\left((\log p_n)^2\right)$, дающая вполне приемлемую оценку. Вычисления на ЭВМ показывают, что простые числа в арифметических прогрессиях расположены достаточно плотно.

В качестве итога обсуждения в этом пункте подчеркнем следующее: если принять на веру, что наименьшее простое число, а также расстояние между соседними простыми числами при $ k<f(q)$ в арифметической прогрессии (1) оцениваются величиной $ O\left((\log q)^2\right)$, то предложенная схема построения простых чисел имеет полиномиальную сложность. Кроме того, несмотря на отсутствие теоретических оценок времени работы алгоритмов, отыскивающих простые числа в арифметических прогрессиях со сравнительно большой разностью, на практике эти алгоритмы работают вполне удовлетворительно.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13.7.2 Алгоритм Вверх: 13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма" Назад: 13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма"   Содержание   Предметный указатель

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