Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Цуканов Б.И. "Время в психике человека" (Медицина)

Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Яблоков Н.П. "Криминалистика" (Юриспруденция)
Реклама

Основы криптологии - Тилборг Х.К.А.

Тилборг Х.К.А. Основы криптологии — Мир , 2006. — 474 c.
ISBN 5-03-003639-3
Скачать (прямая ссылка): osnovikriptologiyi2006.pdf
Предыдущая << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 171 >> Следующая

9.4. Генерация простых чисел; тесты простоты
181
Теорема 9.4
Пусть 7г(ж) подсчитывает число простых чисел, меньших или равных х (см. определение А.1). Тогда
limx_+oo —г,--- = 1.
х/ In X
С помощью закона распределения простых чисел (ЗРП) довольно легко получить долю нечетных Z-значных чисел, которые просты. Вычисляем:
tt(10z) - 7г(10*-1) ЗРП lOVln 10і - 10i_1/ln 10і-1 2(9 -І - 10)
(10і - 10і-1)/2 (10г - 10г-!)/2 9 - 1(1 — 1)1п 10
~ Z • 1п 10 Например, при І = 100 получится
1 = 100;
EstimateProb[1_] = 2*(9*1 - 10)/(9*1*(1 - l)*Log[10]); N[EstimateProb[100], 3]
II 0.00868
Так как обратное к этому числу приблизительно равно 115, ожидаемое число проходов в нашем “алгоритме” порождения простых чисел оценивается числом 115.
9.4.2 Вероятностные тесты простоты
? Тест простоты Соловэя—Штрассена
Пусть р — простое число. Напомним (см. определение А.9), что целое число и, где р )(и (читается: р не делит и), называется квадратичным вычетом (QR) по модулю р, если уравнение
х2 = и (mod р)
имеет целочисленное решение. Если р J( и и данное сравнение не имеет целочисленного решения, то и называется квадрат,ичным невычетом
(NQR) по модулю р. Хорошо известный символ Лежандра (см. определение А.10) задается равенством
+1, если и — квадратичный вычет по модулю р,
— 1, если и — квадратичный невычет по модулю р,
0, если р делит и.
182
Глава 9. Системы, основанные на методе RSA
Символ Якоби (^) (см. определение А. 11) обобщает символ Лежандра на все нечетные натуральные числа т. Пусть т = Y\iPT> гДе Pi (необязательно различные) нечетные простые числа. Тогда (^) определяется равенством
(й)-п,(5)"-
В разд. А.4 читатель может найти все свойства символов Лежандра и Якоби. Эти свойства достигают кульминации в крайне эффективном алгоритме вычисления значений этих символов. Пример можно найти там же. В пакете “Mathematica” оба символа вычисляются с помощью функции JacobiSymbol:
и = 12703; m = 16361; JacobiSymbol[u, m]
II 1
Так как m в примере выше — простое число, фактически легко вычислить квадратный корень из и. Читатель отсылается к разд. 9.5, где обсуждается, как именно это сделать. В пакете “Mathematica” можно просто использовать функцию Solve.
Clear[х];
Solve[{х2 == 12703, Modulus == 16361}, х]
|| {Modulus—>16361, х—>7008}, {Modulus—>16361, х^9353}
В самом деле, (±7008)2 = 12703 (mod 16361), что можно проверить с помощью функции PowerMod.
PowerMod [7008, 2, 16361]
II 12703
Нахождение решений сравнения х2 = и (mod т) для составных чисел т является, вообще говоря, очень трудной задачей, неноддающейся решению для больших значений т (обсуждение этой проблемы см. в [Рега86]).
Если т — произведение различных простых чисел, и это разложение известно (!), то можно найти квадратный корень из и по модулю га, найдя квадратные корни из и по модулю всех простых делителей числа т, а затем скомбинировав результаты посредством китайской теоремы об остатках. Этот метод будет продемонстрирован в разд. 9.5. Когда разложение т содержит более высокие степени простых чисел, все становится намного более сложным.
9.4. Генерация простых чисел; тесты простоты
183
Пусть р — простое число, р > 2. Напомним, что по теореме А.23 для всех целых чисел U
Алгоритм Соловэя-Штрассена [SolS77] опирается на следующую теорему:
Теорема 9.5
Пусть гп — нечетное целое число, a G определяется равенством
Доказательство. Если га просто, то любое целое и, 0 < и < га, удовлетворяет сравнению (9.15) и имеет нод с га, равный 1, так что в этом случае |G| = га — 1.
Поэтому нужно рассмотреть лишь случай, когда га не просто. Очевидно, G — подгруппа мультипликативной группы
Из теоремы В.5 следует, что мощность G делит мощность Z^. Поэтому, если G ф Z^, можно заключить, что
Это докажет теорему. Таким образом, достаточно доказать существование такого элемента и в Z^, что (^) ф и^гп~1^2 (mod га).
Мы различаем два случая. В [SolS77] авторы опускают рассмотрение случая, когда га — квадрат. В приводимом ниже доказательстве, принадлежащем Дж.У.Найенхьюзу (частное сообщение), случай 1 покрывает опущенную возможность.
Случай 1: число га делится на квадрат некоторого простого числа.
Запишем тп = pr ' s, где р — нечетное простое, г > 2 и нод(р, s) = 1. Пусть и — решение системы сравнений
В силу китайской теоремы об остатках (теорема А. 19) такое решение и существует и единственно по модулю га. Очевидно, НОд(и,рг) —
(mod р).
(9.15)
G = |о < и < га НОД(u, га) = 1 и — г^т 1^2
Тогда
|G| = га — 1, если га просто; (9.16)
\G\ < (га — 1)/2, если гп не просто. (9-17)
Z^ = {0 < и < га|нод(г/,га) = 1}.
\G\ < |Zl|/2 = ip(m)/2 < (m - l)/2.
Предыдущая << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 171 >> Следующая