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

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

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

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

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

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

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

А.24, теоремы А.25 и теоремы А.27, или же в пакете “Mathematica” с помощью функции JacobiSymbol, которую можно применить сразу ко всему списку чисел.-
192
Глава 9. Системы, основанные на методе RSA
m = -Cl, 5, 7, 11 , 13, 17, 19, 23};
JacobiSymbol[-1, m]
JacobiSymbol[2, m]
JacobiSymbol[3, m]
II -ci, 1, -1, -1, 1, 1, -1, -1}
II -ci, -1, 1, -1, -1, 1 , -1, 1}
11 -Cl, -1, -1, 1, 1, -1 , -1, 1}
Легко проверить, что матрица с этими тремя векторами-строками обладает тем свойством, что все ее столбцы различны. Это показывает, что три значения (^) ,и = —1,2,3, однозначно определяют га в множестве {1,5,7,11,13,17,19,23}.
Например, глядя на второй столбец, мы видим, что га = 5 однозначно определяется в {1,5,7,11,13,17,19,23} тремя значениями (у^) = 1, (JL) = _1 и (±) = -1.
\ m / чттг/
Лемма 9.16
Пусть га — произвольное целое число. Тогда
НОД(т, 6) = 1 => га2 = 1 (mod 24).
Доказательство. Так как га не делится на 3, получаем m2 = 1 (mod 3). Аналогично, из нечетности гп следует, что га2 = 1 (mod 8). Чтобы увидеть это, запишем га = 2п + 1. Тогда га2 - (2п + I)2 =
- - 4п(п + 1) + 1.
Поскольку 3 и 8 взаимно просты, наше утверждение следует из китайской теоремы об остатках.
Конечно, последнюю лемму можно проверить с помощью функции Mod из пакета “Mathematica” следующим образом:
m = -Cl, 5, 7, 11, 13, 17, 19, 23};
Mod[m2, 24]
II -Cl, 1, 1, 1, 1, 1, 1, 1}
Теперь мы готовы доказать теорему 9.13.
Доказательство теоремы 9.13. То, что показатель j в (9.25) может быть приведен по модулю 2, прямо следует из условия НОд(га,6) = = 1 и леммы 9.16. Это показывает, что сравнение (9.25) можно заменить на (9.26).
Далее, заметим, что (9.25) достаточно доказать только для простых делителей d числа га. Запишем га — 1 = f • 2к и d — 1 = <7 • 2^, где / и g нечетны и к, ? > 0.
9.4. Генерация простых чисел; тесты простоты
193
Докажем сначала, что ? > к, а затем используем лемму 9.15, чтобы показать, что либо d, — m° mod 24, либо d = га1 mod 24.
Возведем обе части сравнения (9.24) в степень д и приведем результат по модулю d. Так как d\m и д нечетно, получим
af-g-2к 1 ^ (—1)3 = — 1 (mod d).
Поскольку мы предполагаем, что d просто и а не имеет общих делителей с d или с га, из теоремы Ферма (теорема А. 15) следует, что
af-9-2* = af(d-i) = — i (mod d).
Из двух последних сравнений вытекает, что к — 1 < ?.
Рассмотрим теперь и Є {—1,2,3}. Так как д нечетно и d\m,, имеем
и/.д.2‘- = мв(т-1)/2 <9|3> QL)9 = (mod
С другой стороны (снова ввиду простоты d),
/
и
Из двух последних сравнений вытекает, что для і = —1, 2, 3
и\ _ / и Я/
\ 2е~к
) . (9.27)
Заметим, что мы заменили отношение сравнения равенством. Это можно сделать, потому что обе части принимают значения ±1.
Если ? = к, то равенство (9.15) и лемма 9.15 влекут за собой, что d = т = т1 (mod 24). С другой стороны, если ? > к, то правая часть в (9.27) равна 1, что также есть (и/1). Поэтому лемма 9.15 дает d = 1 = т° (mod 24).
В применении теоремы 9.13 решающим является тот факт, что условие (9.25) можно заменить на (9.26). Ввиду этого в четырех шагах алг. 9.14 только одно условие нуждается в проверке. Основанием для замены
(9.25) на (9.26) служит то (см. лемму 9.16), что
НОД(ш, 24) = 1 =Ф- т2 = 1 (mod 24).
Теорема 9.13 проверяет простоту только таких чисел га, что 24 <
< га < 242. Для больших значений га необходимы обобщения теоремы 9.13. Как можно ожидать, в этих обобщениях показатель в лемме 9.16
194
Глава 9. Системы, основанные на методе RSA
должен возрастать. Примером такого обобщения может служить импликация
нод(т, 65520) = 1 =* га12 = 1 (mod 65520).
Для проверки на простоту 100-значного числа га используется импликация
НОД(т, s) = 1 =4> га5040 = 1 (mod s), где s — 53-значное число
26 х З3 х 52 х 72 х И х 13 х 17 х 19 х 31 х 37 х 41 х 43 х 61 х 71 х 73х
х 113 х 127 х 181 х 211 х 241 х 281 х 337 х 421 х 631 х 1009 х 2521.
Заметим, что л/гп < s, если га имеет не более 100 цифр. Приведем грубый набросок теста простоты для 100-значного числа10.
Алгоритм 9.17 (набросок теста простоты Коэна-Ленстры)
input натуральное га < Ю100; initialize prime = True;
test 1: if НОД(га, s) ф 1 then prime = False;
test 2: if га не удовлетворяет одному из 67 сравнений,
подобных (9.23) then prime = False; test 3: вычислить d = тг mod s для г = 1, 2,... , 5039;
if одно из этих d делит га, then prime = False; output prime.
Если га — составное, то приведенный выше алгоритм иногда даст делитель числа га. Но вероятность такого события очень мала: в большинстве случаев составного га алгоритм будет заканчиваться на шаге 2, не “выдавая” делителей га. Этот алгоритм можно адаптировать для тестирования на простоту и бблыних целых чисел. Ожидаемым временем пробега служит
Предыдущая << 1 .. 64 65 66 67 68 69 < 70 > 71 72 73 74 75 76 .. 171 >> Следующая