Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 72

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 66 67 68 69 70 71 < 72 > 73 74 75 76 77 78 .. 125 >> Следующая


t t 1г t

случиться одно из двух: 1)6 =1 (mod р) и 6 =1 (mod q) или 2)6 = -1 (mod р) и 6 = — 1 (mod q) для некоторого г, 0 ^ г < s. По лемме 1 число оснований 6, для которых реализуется первая возможность, равно НОД (t, t') ¦ НОД (t, t") (произведению чисел классов вычетов по модулям р и q); ясно, что это число не превосходит і і". По лемме 2

для каждого г < min (s ,s ) = s число таких 6, что 6 = -1 (mod п), равно 2Г НОД (i, t') ¦ 2Т НОД (t, t") < 4rt't". Так как п - 1 > <р(п) =

2s +s t't", то доля оснований 6 Є (Z/nZ)*, по которым п — сильно псевдопростое, не превышает

и" + t't"+ 4t't"+ 42t't" + ... + /-Уг" _ _,._,» / 43' - A

2S'+S'Y*" ~2 V + 4-1 J •

г " ^ ' * o-2s'-l/2 , 4'' \ ^ n-32 , 1 1

ЕХЛИ S > S , TO ЭТО НЄ ПреВОСХОДИТ 2 (1 + —)<2 3 + 6~=4'

что и требовалось доказать. С другой стороны, если s' = s", то одно из неравенств НОД (t,t')^ і', НОД (м") =? t" должно быть строгим: если бы мы имели одновременно t'\t и t"\t, то из сравнения

п — 1 = 2st = pq — 1 = q—1 (mod і') следовало бы, что <'|(д- 1) = 2s t", т.е. ; аналогично t"\t' и, значит, = t". Но тогда р = q, вопреки

* В дальнейшем предполагается, что п - 1 = 2*і, 1 нечетно. — Прим. ред.

150

ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ

предположению. В строгом неравенстве вида НОД (t, Ґ) < Ґ левая часть составляет не более 1/3 от правой (так как все числа в этом неравенстве — нечетные). Таким образом, в нашем случае можно за-

,/,// л .1.4 - l

менить it на jt і в числителе оценки для числа основании о, по которым п является сильно псевдопростым. Это приводит к следующей оценке сверху доли тех оснований Ь, 0 < Ь < п, по которым п — сильно псевдопростое:

что и требовалось. Это завершает доказательство предложения в случае 2.

Случай 3. Предположим, наконец, что п — произведение более, чем двух различных простых чисел: п = р\р2 ¦ ¦ -рь к ^ 3. Положим Pj-I = 2s' tj, где tj нечетно, и будем действовать в точности так же, как в случае 2. Без ущерба для общности можно предполагать, что .S1 ^ Sj, j = 2,.. ., к. Мы получаем следующую верхнюю оценку доли возможных оснований Ь, по которым п — сильно псевдопростое число:

так как к ^ 3 в случае 3. Тем самым доказательство предложения V.1. 7 закончено.

Замечания. 1. Практически не возникает необходимости брать большое количество оснований Ь, чтобы быть «почти» уверенным, что число п простое, если оно сильно псевдопростое по каждому из оснований Ь. Например, было показано, что существует лишь одно составное число, меньшее 2,5 • 1010, а именно, 3215031751, которое является сильно псевдопростым по каждому из оснований b = 2,3,5,7.

2. Полностью полагаться на вероятностный тест не вполне надежно. Несмотря на заверение Эмиля Бореля, цитированное в начале параграфа, было бы неплохо иметь быстрые методы доказательства того, что данное число п действительно простое (особенно, если важно с практической или теоретической точки зрения знать, что данное п действительно простое). Например, допустим, что существует такое небольшое число В (зависящее от п), что любое составное п не является сильно псевдопростым хотя бы по одному основанию 6 < В.

§ 1. ПСЕВДОПРОСТЫЕ ЧИСЛА

151

Если бы мы знали такое В, то для абсолютной уверенности в простоте п было бы достаточно провести тест (3) для первых В оснований.

Подобное утверждение имеет место, однако оно является следствием недоказанного предположения, называемого «обобщенной гипотезой Римана». Обычная гипотеза Римана утверждает, что все комплексные нули так называемой дзета-функции Римана ((s) (определяемой при s > 1 как сумма дробей 1 /п ), которые лежат в «критической полосе» (где действительная часть s находится между 0 и 1), должны лежать на «критической прямой» (действительная часть s равна |). «Обобщенная гипотеза Римана» — это то же самое утверждение для некоторых обобщений C(s), называемых «Z-рядами Дирихле». Следующее предложение, доказательство которого выходит за рамки этой книги, показывает, что условие (3) в критерии Миллера-Рабина дает детерминистический тест на простоту, временная сложность которого является полиномиальной функцией от log п, если справедлива обобщенная гипотеза Римана (ОГР).

Если ОГР справедлива и п — составное нечетное число, то п не удовлетворяет условию (3) хотя бы для одного основания Ь, меньшего 2 log п.

3. В 1980-е гг. был разработан эффективный детерминистический тест на простоту, который хотя и не является, строго говоря, полиномиальным по logn, на практике может доказать простоту чисел, имеющих свыше ста цифр в десятичной записи, в течение каких-то секунд (на современных больших компьютерах). Этот метод Адлемана-Померанца-Рамли (Adleman-Pomerance-Rumely) и Коэна-Ленстры (Cohen-Lenstra) основывается на тех же идеях, что и рассмотренные выше тесты на простоту, с той разницей, что он использует аналоги малой теоремы Ферма в расширениях полей рациональных чисел. Основную роль играют гауссовы суммы (некоторые их типы были введены в § П. 2 для доказательства закона квадратичной взаимности) и тесно с ними связанные «суммы Якоби». Подробное рассмотрение их метода завело бы нас слишком далеко. Обстоятельное и не слишком сложное изложение имеется в статье Коэна и Ленстры в «Mathematics of Computation*.
Предыдущая << 1 .. 66 67 68 69 70 71 < 72 > 73 74 75 76 77 78 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed