Быстрые вычисления с целыми числами и полиномами — страница 10
логарифмом числа b. Выше мы описали алгоритм, позволяющий по заданному числу x достаточно быстро вычислять ах mod p. Обратная же операция – вычисление по заданному b его дискретного логарифма, вообще говоря, является очень сложной в вычислительном отношении задачей. Именно это свойство дискретного логарифма и используется в его многочисленных криптографических применениях. Наиболее быстрые (из известных) алгоритмы решения этой задачи, основанные на так называемом методе решета числового поля, требуют выполнения exp(c(ln p)1/3(ln ln p)2/3) арифметических операций, где c – некоторая положительная постоянная. Это сравнимо со сложностью наиболее быстрых алгоритмов разложения чисел на множители. Конечно, указанная оценка сложности получена при условии справедливости ряда достаточно правдоподобных гипотез. Говоря о сложности задачи дискретного логарифмирования, мы имели в виду «общий случай». Ведь и большое целое число легко может быть разложено на простые сомножители, если все эти сомножители не очень велики. Известен алгоритм, позволяющий быстро решать задачу дискретного логарифмирования, если p – 1 есть произведение малых простых чисел. Пусть 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…, позволяющее достаточно быстро вычислять логарифмы с произвольной точностью. Например, это можно делать с помощью быстро
Похожие работы
- Доклады
- Рефераты
- Рефераты
- Рефераты
- Контрольные