Быстрые вычисления с целыми числами и полиномами — страница 10

  • Просмотров 4181
  • Скачиваний 39
  • Размер файла 75
    Кб

логарифмом числа 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…, позволяющее достаточно быстро вычислять логарифмы с произвольной точностью. Например, это можно делать с помощью быстро