Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата



Пусть q – простое число, делящее р – 1. Обозначим с ( а(p – 1)/q (mod p), тогда классы вычетов 1, с, с2, … , сq – 1 все различны и образуют полное множество решений уравнения хq = 1 в поле Fp = Z/Zp. Если q не велико и целое число d удовлетворяет сравнению хq ( 1 (mod p), то показатель k, 0 ( k < q, для которого выполняется d ( ck (mod p), легко может быть найден, например, с помощью перебора. Именно на этом свойстве основан упомянутый выше алгоритм.

Допустим, что р – 1 = qkh, (q,h) = 1. Алгоритм последовательно строит целые числа uj, j = 0,1,…,k, для которых выполняется сравнение

( 1 (mod p).
(3)
Так как выполняется сравнение ( 1 (mod p), то найдётся целое число u0, для которого ( (mod p). При таком выборе сравнение (3) с j =
0, очевидно, выполняется. Предположим, что найдено число uj, удовлетворяющее сравнению (3). Тогда определим t с помощью сравнения

( ct (mod p),
(4)

и положим. Имеют место сравнения

( ( 1 (mod p), (5) означающие справедливость (3) при j + 1.

При j = k сравнение означает в силу (2), что ( 1 (mod p). Целое число а есть первообразный корень по модулю р, поэтому имеем (x – uk)h ( 0
(mod p – 1) и x ( uk (mod qk).

Если , где все простые числа qj малы, то указанная процедура позволяет найти вычеты x mod , i = 1,…,s, и, с помощью китайской теоремы об остатках, вычет x mod p – 1, т. е. решить сравнение (2).

В случае обычных логарифмов в поле действительных чисел имеется специальное основание e = 2,171828…, позволяющее достаточно быстро вычислять логарифмы с произвольной точностью. Например, это можно делать с помощью быстро сходящегося ряда ln(1+x)/(1 – x) = 2(x + x3/3 + x5/5 + …), |x| < 1. (6)
Логарифмы по произвольному основанию с могут быть вычислены с помощью тождества logc x = ln x/ ln c. (7)
В случае дискретных логарифмов нет основания, по которому логарифмы вычислялись бы столь же быстро, как натуральные в поле действительных чисел. Вместе с тем, последняя формула, связывающая логарифмы с различными основаниями, остаётся справедливой и позволяет выбирать основание удобным способом. Единственное условие для этого состоит в том, чтобы логарифм нового основания Log c был взаимно прост c p - 1. Тогда в формуле (7) возможно деление по модулю р – 1. Заметим, что это условие будет выполнено, если и только если с – первообразный корень. Из расширенной гипотезы Римана следует, что наименьший первообразный корень по модулю р ограничен величиной O(log6 p). Поэтому в дальнейшем для простоты изложения мы будем предполагать, что основание а в (2) невелико, именно а = O(log6 p).

Так как поле Fp неполно, вычисление дискретных логарифмов не может использовать предельный переход и основано на иных принципах. Прежде всего, нужный дискретный логарифм log b вычисляется не сам по себе, а вместе с совокупностью логарифмов ряда других чисел. Заметим, что всякое сравнение вида

( (mod p), (8) где qi, ki, mi ( Z приводит к соотношению между логарифмами

(k1 – m1)Log q1 + … + (ks – ms)Log qs ( 0 (mod p – 1). (9)

А если выполняются сравнения

a ( (mod p – 1) b ( (mod p),

то

r1Log q1 +…+ rsLog qs ( 1 (mod p – 1) (10) и

Log b ( x1Log q1 +…+ xsLog qs (mod p – 1) (11)
Имея достаточно много векторов k1,…,ks, m1,…,ms с условием (8), можно найти решение соответствующей системы сравнений (9), (10). Если эта система имеет единственное решение, то им как раз и будет набор логарифмов Log q1,…,Log qs. Затем с помощью (11) можно найти Log b.

Мы опишем ниже реализацию этой идеи, взятую из работы [1]. Эвристические соображения позволили авторам этой работы утверждать, что предложенный ими алгоритм требует L1 + (, где L = , арифметических операций для вычисления Log b.

Положим

H = [ ] + 1, J = H2 – q.
Тогда 0 < J < 2 + 1, и, как легко проверить, для любой пары целых чисел с1, с2 выполняется сравнение

(H + c1) (H + c2) ( J + (c1 + c2)H + c1c2 (mod p). (12)
Если числа ci не очень велики, скажем ci ( L1/2 + ( при некотором ( > 0, то правая часть сравнения (12) не превосходит p1/2 + (/2. Можно доказать, что случайно выбранное натуральное число x < p1/2 + (/2 раскладывается в произведение простых чисел, меньших с вероятностью, большей, чем L-1/2 -
(/2.

Обозначим через S = {q1,…,qs} совокупность всех простых чисел q < L1/2, а также всех простых чисел вида H + c при 0 < c < L1/2 + (. Тогда s =
O(L1/2 + (). Будем теперь перебирать случайным образом числа и для каждой такой пары пытаться разложить на множители соответствующее выражение из правой части (12). Для разложения можно воспользоваться, например, делением на все простые числа, меньшие, чем L1/2. Перебрав все (L1/2 + ( )2/2 = O(L1
+ 2( ) указанных пар с1, с2 мы найдём, как это следует из указанных выше вероятностных соображений, не менее

L-1/2 - (/2 *O(L1 + 2( ) = O(L1/2 + 3(/2) (13) пар, для которых правая часть сравнения (12) полностью раскладывается на простые сомножители, меньшие L1/2. Сравнение (12), таким образом, принимает вид (8). Так строится система уравнений типа (9).

Напомним, что число а, согласно нашему предположению, существенно меньше, чем L1/2. Поэтому оно раскладывается в произведение простых чисел, входящих во множество {q1,…,qs}, и это приводит к сравнению (10).

Заметим, что количество (13) найденных сравнений типа (9) превосходит число s. Следовательно, построенная система неоднородных линейных сравнений относительно Log qi содержит сравнений больше, чем неизвестных. Конечно, множество её решений может при этом быть бесконечным. Одна из правдоподобных гипотез состоит в том, что система имеет всё-таки единственное решение, и, решив её, можно определить дискретные логарифмы всех чисел qi. На этом завершается первый этап работы алгоритма из [1].

Рекомендуем скачать другие рефераты по теме: доклад 6 класс, здоровый образ жизни реферат.

Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата