§3. Алгоритмы дискретного логарифмирования.
Проблема дискретного логарифмирования в группе Zp* состоит в следующем: пусть p – простое число, g – порождающий элемент группы Zp* (или, иначе, примитивный корень по модулю p), a=gx (mod p). Пусть известны g, p, a, но неизвестно x. Требуется найти x, или, иначе, logga mod (p—1), то есть вычислить дискретный логарифм.
В отличие от логарифма непрерывного, дискретный логарифм не является дифференцируемой монотонной функцией, его нельзя найти приближенно, разложив в ряд Тейлора, и вообще никакого приближенного значения здесь не может быть, ведь x – целое число.
Дискретное логарифмирование считается сложной проблемой. С этой проблемой связаны и другие теоретико-числовые проблемы, такие как проблема Диффи-Хеллмана, логарифмирование в Zn. Если удастся решить проблему дискретного логарифма, то приведенные задачи решаются за полиномиальное время.
3.1. Метод прямого поиска.
Этот наивный метод является самым трудоемким, он требует O(n) умножений, то есть обладает экспоненциальной сложностью. Состоит он в следующем: вычисляются g0, g1, g2,…, gp—1 пока не попадется gi≡a(mod p). Полученное i будет искомым дискретным логарифмом i=logga (mod p—1).
Пример
p=23, g=5, a=19.
i0123456789101112131415gi mod p15210420817161192218211319
Ответ: log519 mod 22 = 15.
3.2. Шаг младенца – шаг великана.
В открытой литературе этот метод впервые был описан Шенксом (Daniel Shanks), ссылки на него известны с 1973 года. Это был один из первых методов, более быстрый чем метод прямого перебора.
Общая схема алгоритма такова:
Берем два целых числа m и k, таких что mk>p (как правило, m=k= ). Затем вычисляются два ряда чисел:
a, ga, g2a, … , gm—1a (mod p)
gm, g2m, g3m, … , gkm (mod p)
(все вычисления произведены по модулю p).
Найдем такие i и j, для которых gia=gjm. Тогда x=jm—i.
Справедливость последнего равенства подтверждается следующей цепочкой, все вычисления в которой произведены по модулю p:
gx=gjm-i=gjm(gi)-1=gjma(gia)-1=gjma(gjm)-1=a.
Заметим, что числа i и j непременно будут найдены, поскольку при i= , j= выполняется jm—i= , причем km>p. То есть среди всех чисел вида jm—i обязательно содержится 0 < x ≤ p.
Замечание: Указанный метод можно применять для разыскания дискретных логарифмов в любой циклической группе порядка n.
Приведем этот метод в форме алгоритма.
Алгоритм «Шаг младенца-шаг великана»:
Вход: g - порождающий элемент конечной группы G порядка n; a G.
Ш.1. Вычислить m= .
Ш.2. Вычислить b=gm.
Ш.3. Вычислить последовательности ui=bi, vj=agj Для i,j= .
Ш.4. Найти i, j такие что ui=vj. x=mi—j mod n. Идти на Выход.
Выход: logga=x.
Одна из трудоемких частей этого алгоритма – это поиск на Шаге 4. Он может быть осуществлен несколькими способами:
Сначала построить таблицу (i, ui), отсортировать ее по второй компоненте а затем произволить сравнения по мере нахождения компонент vj.
Построить две таблицы (i, ui) и (j, vj), отсортировать каждую из них, а затем произвести поиск совпадений.
Объединить u, v в одну таблицу, снабдив их номером в соответствующей последовательности и битом принадлежности к одной из двух последовательностей, а затем применить совместную сортировку. И т. п.
Сложность данного алгоритма составляет O( ) умножений по модулю и O( log n) операций сравнения.
Пример.
Пусть n=229 (простое число), g=6, a=12.
Ш.1. m=16.
Ш.2. b=ga mod n =612 mod 229 = 183.
Ш.3. В этом примере вычислим сначала ряд ui, а затем будем вычислять компоненты vj до тех пор, пока не найдется совпадение.
i, j12345678910
ui183552184882121159144383
vj7220373209109196
11121314151675214391165196
i=16, j=6. x=mi—j mod n = 250 mod 228 = 22.
Проверка: 622 mod 229= 12.
Ответ: log612 mod 228 = 22.
3.3. Ро-метод Полларда для дискретного логарифмирования.
Этот алгоритм осуществляет случайный поиск дискретных логарифмов, как и метод «шаг ребенка – шаг великана», но он требует меньшего объема памяти для хранения данных, поэтому предпочтительней для практических целей. В основе данного метода лежит та же идея, что и в основе ро-метода для факторизации – строится псевдослучайная последовательность, в которой находятся совпадающие элементы при помощи метода Флойда, а затем на основании полученной величины вычисляется искомый дискретный логарифм.
Пусть требуется вычислить logga в конечной группе G порядка n.
Группа G разбивается на три непересекающихся подмножества примерно равной мощности: G=S1US2US3, так чтобы 1 S2. Причем разбиение должно быть построено таким образом, чтобы проверка, к какому подмножеству принадлежит данный элемент x, была простой.
Например, если G=Zp, где p – простое число, то можно задать разбиение S1={1,…, }, S2={ ,…, }, S3={ , … , p—1}, или разбиение может быть таким: если x mod 3=1, то x S1, если x mod 3=2, то x S2, если x mod 3=0, то x S3.
Далее на G задается последовательность x0, x1, x2, … , где x0=1, xi+1 вычисляется по xi посредством функции f для i≥0:
xi+1=f(xi)=
Вычисления проводятся в группе G, то есть если G=Zm, то вычисления следует производить по модулю m.
Такая последовательность групповых элементов может быть представлена двумя последовательностями u0, u1, u2,… и v0, v1, v2,… такими, что xi= , u0=v0=0,
ui+1= , vi+1=
Вычисления в последовательностях u и v производятся по модулю n.
В силу того, что группа G – конечная, при помощи метода Флойда можно найти такие xi и x2i, что xi = x2i. Тогда = . Логарифмируя по основанию g обе части данного уравнения, получим
(vi—v2i)logga≡(u2i—ui) (mod n)
Решая это сравнение, получим искомый логарифм. (Заметим, что если G=Z*m, то n=φ(m)).
Сложность данного метода составляет O( ) , где n – порядок группы G.
Замечание. Метод может дать отказ в том случае, когда vi =v2i. Тогда следует назначить случайные значения от 0 до n—1 переменным u0, v0 , вычислить x0= и повторить все шаги алгоритма.
Замечание. В том случае, когда имеется достаточно места для хранения данных в процессе вычислений (например, когда G невелико или вычисления производятся вручную), можно обойтись без метода Флойда. Тогда следует хранить все члены последовательностей x, u и v до того, как xi = xj и дискретный логарифм находится из сравнения (vi—vj)logga≡(uj—ui) (mod n).
Пример.
G=Z*19, a=8, g=2.
Тогда n=φ(19)=18. Поскольку решение будем производить вручную, то не будем пользоваться методом Флойда.
Разбиение G на подмножества произведем следующим образом: если x mod 3=1, то x S1, если x mod 3=2, то x S2, если x mod 3=0, то x S3.
Вычисления будут производиться по формулам:
xi+1=f(xi)=
ui+1= , vi+1=
i012345678xi1871817413918ui000012223vi012336788SS1S2S1S3S2S1S1S3S3
x3=x8. Логарифм найдем из сравнения (v3—v8)log28≡(u8—u3) (mod 18)
-5 log28≡3(mod 18)
13 log28≡3(mod 18)
log28≡3·7(mod 18)
log28≡3(mod 18).
Действительно, 23≡8 (mod 19).
Ответ: log28≡3(mod 18).
3.4. Алгоритм Полига-Хеллмана.
Этот алгоритм использует следующий подход: пусть G – группа порядка n, и n= - каноническое разложение на простые сомножители. Если x=logga mod n, то, вычислив xi=logga mod , для 1 ≤ i ≤ k, можно восстановить x, используя китайскую теорему об остатках.
Для того чтобы вычислить xi, вычисляют коэффициенты l0, l1,…, в pi-чном представлении числа xi: xi=l0+l1pi+…+ , где 0 ≤ lj ≤ pi—1.
Представим метол Полига-Хеллмана следующим алгоритмом:
Алгоритм Полига-Хеллмана:
Вход: g – порождающий элемент циклической группы порядка n, a G.
Ш.1. Найти каноническое разложение n= .
Ш.2. Для i от 1 до k выполнить следующие действия:
1. Задать q=pi, α=αi.
2. Задать γ=1, l-1=0.
3. Вычислить .
4. Для j от 1 до α—1 выполнить:
4.1. Вычислить γ=γ ,
4.2. Вычислить li= . (например, используя алгоритм «шаг младенца - шаг великана» или прямой поиск).
5. Вычислить xi=l0+l1q+…+lα—1qα—1.
Ш.3. Используя Китайскую теорему об остатках, решить систему сравнений x≡xi(mod ) .
Выход. x=logga mod n.
Замечание. Все вычисления производятся в группе G кроме случаев, когда оговорено иное.
Замечание. Поскольку порядок элемента (в чем нетрудно убедиться, подставив вместо его выражение из 4.2 и учитывая, что порядок есть q), то li= .
Заметим, что вычисление логарифма прямым поиском на этапе 4.2. происходит сравнительно быстро, так как приходится перебирать не более q значений.
Данный метод эффективен в случаях, когда n является большим числом, а все его простые сомножители – малыми числами.
Сложность данного алгоритма составляет O( ) умножений в группе при условии, что разложение n известно.
Пример.
Пусть G=Z*p, p=61, g=2, a=7.
Ш.1. n=φ(p)=p—1=60=22·3·5.
Ш.2.
1. q=2, α=2.
2. γ=1, l-1=0.
3. =230 mod 61=60.
4. j=0 γ=1, =730 mod 61 = 60 l0=log6060 mod 61=1.
j=1 γ=2, =(7·2-1)30mod 61=(7·31)30mod 61=1 l0=log601 mod 61=0.
5. x1=1+0·2=1.
1. q=3, α=1.
2. γ=1, l-1=0.
3. =220 mod 61=47.
4. j=0 γ=1, =720 mod 61 = 47 l0=log4747 mod 61=1.
5. x2=1.
1. q=5, α=1.
2. γ=1, l-1=0.
3. =212 mod 61=9.
4. j=0 γ=1, =712 mod 61 = 34 l0=log934 mod 61=4 (этот логарифм нашли прямым перебором).
5. x3=4.
Ш.3. Составим и решим систему . Решением этой системы будет x≡48 (mod 60).
Проверка: 248mod 61=7.
Ответ: log27 mod 60 = 48.
3.5. Алгоритм исчисления порядка (index-calculus algorithm).
Основные идеи алгоритма исчисления порядка были известны с 20-х годов XX века, но лишь в 1979 году Адлерман указал на этот алгоритм как на средство вычисления дискретного логарифма и исследовал его трудоемкость. В настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в некоторых конечных группах, в частности, в группе Zp*.
Этот алгоритм в отличие от алгоритмов прямого поиска и ро-метода подходит не для всех циклических групп.
Алгоритм состоит в следующем:
Алгоритм исчисления порядка
Вход: g – порождающий элемент циклической группы порядка n, a G, с≈10 – параметр надежности.
Ш.1. Выбирается факторная база S={p1, p2,…,pt}. (Если G=Zp*, то S состоит из t первых простых чисел.)
Ш.2. Выбрать случайное k: 0≤k<n и вычислить gk.
Ш.3. Попытаться разложить gk по факторной базе:
, αi≥0.
Если это не удалось, вернуться на Шаг 2.
Ш.4. Логарифмируя обе части получившегося выражения, получаем
(mod n) *
В этом выражении неизвестными являются логарифмы.
Это сравнение с t неизвестными следует запомнить.
Ш.5. Если сравнений вида (*), полученных на Шаге 4, меньше, чем t+c, то вернуться на Шаг 2.
Ш.6. Решить систему t+c сравнений с t неизвестными вида (*), составленную на Шагах 2-5.
Ш.7. Выбрать случайное k: 0≤k<n и вычислить agk.
Ш.8. Попытаться разложить agk по факторной базе:
, βi≥0.
Если это не удалось, вернуться на Шаг 7.
Ш.9. Логарифмируя обе части последнего равенства, получаем
x= ,
где loggpi (1≤i≤t) вычислены на Шаге 6 как решение системы сравнений.
Выход. x = logga mod n.
В том случае, когда G=Zp*, в качестве факторной базы S берут t первых простых чисел. Такой выбор оправдан следующим наблюдением. Число, наугад выбранное из множества целых чисел, с вероятностью 1/2 делится на 2, с вероятностью 1/3 – на 3, с вероятностью 1/5 – на 5 и т.д. Поэтому можно ожидать, что в промежутке от 1 до p—1 найдется достаточно много чисел, в разложении которых участвуют только маленькие простые делители из множества S. Именно такие числа отыскиваются на шагах 2 и 7.
Параметр c вводится для того, чтобы система сравнений, решаемая на Шаге 6, имела единственное решение. Дело в том, что полученная система может содержать линейно зависимые сравнения. Считается, что при значении с порядка 10 и большом p система сравнений имеет единственное решение с высокой вероятностью.
Пример.
G=Z*71, g=7, a=17, n=φ(71)=70.
S={2, 3, 5, 7} (Шаг 1). (Можем сразу указать log77 mod 70=1).
Теперь будем перебирать k для составления системы сравнений вида * (Шаги 2—5).
k=2, 72 mod 71=49=7·7. (поскольку log77 уже вычислен, это сравнение нам не пригодится).
k=3, 73 mod 71=59.
k=4, 74 mod 71=58=2·29.
k=5, 75 mod 71=51=3·17.
k=6, 76 mod 71=2 6≡log72(mod 70)
k=7, 77 mod 71=14=2·7 7≡log72+log77(mod 70)
k=8, 78 mod 71=27=33 8≡3log73(mod 70)
k=9, 79 mod 71=47.
k=10, 710 mod 71=45=32·5 10≡2log73+log75(mod 70)
Теперь имеем достаточно сравнений для того, чтобы определить логарифмы от элементов факторной базы. Вот эти сравнения:
6≡log72(mod 70)
7≡log72+log77(mod 70)
8≡3log73(mod 70)
10≡2log73+log75(mod 70)
Решая полученную систему, получаем (Шаг 6):
log72≡6(mod 70), log73≡26(mod 70),
log75≡28(mod 70), log77≡1(mod 70).
Перейдем к Шагам 7—9:
k=1, 26·7 mod 71=40=23·5 log726≡3log72+log75—1(mod 70)
log726≡3·6+28—1(mod 70)
log726≡45(mod 70)
Проверка: 745 mod 71 = 26. Верно.
Ответ: log726≡45(mod 70).
Замечание: Для случая G=Zp и для случая G=F2m составляет Lq[1/2,c], где q есть мощность G, с > 0 – константа. Алгоритм, имеющий наилучшую оценку сложности (по времени) для дискретного логарифмирования в Zp есть вариант алгоритма исчисления индексов под названием «метод решета числового поля» (number field sieve), для дискретного логарифмирования в F2m - вариант данного алгоритма под названием «алгоритм Копперсмита» (Coppersmith’s algorithm). Эти алгоритмы слишком сложны, чтобы приводить их здесь.
Задачи и упражнения.
Упражнения к Главе 1.
Вычислить НОД(a,b) при помощи алгоритма Евклида с делением с остатком и бинарного алгоритма Евклида. Сравнить количество итераций.
a) a = 715, b = 195; d) a = 1818, b = 726; g) a = 2448, b = 1632;
b) a = 246, b = 396; e) a= 6887, b = 6319; h) a = 1600, b = 1120;
c) a = 175, b = 14945; f) a = 1763, b = 1634; i) a = 2310, b = 3388.
Пользуясь таблицей простых чисел, найти канонические разложения следующих чисел:
a) 492; d) 4144; g) 624239;
b) 22011; e) 2597; h) 422375;
c) 7533; f) 425106; i) 11502.
Вычислить НОК(a,b).
a) a = 744, b = 198; d) a = 50, b = 42; g) a = 3131, b = 808;
b) a = 60, b = 1575; e) a= 231, b = 1089; h) a = 1063, b = 3;
c) a = 128, b = 81; f) a = 73, b = 219; i) a = 1960, b = 1232.
Пользуясь свойствами функции Эйлера, вычислить φ(a).
a) a = 73; d) a = 343; g) a = 210;
b) a = 81; e) a= 6; h) a = 10800;
c) a = 97; f) a = 28; i) a = 32.
1.5. Выяснить, верны ли сравнения:
a) 25 ≡ —1 (mod 13); d) 3 ≡ 15 (mod 11); g) 128 ≡ 20 (mod 9);
b) 11 ≡ 3 (mod 2); e) 45 ≡ 12 (mod 11); h) 32 ≡ 5 (mod 7);
c) 100 ≡ 14 (mod 17); f) 98 ≡ 46 (mod 5); i) 13 ≡ 1 (mod 14).
1.6. Выписать полную и приведенную системы вычетов по модулю n. Сравнить количество чисел в приведенной системе вычетов со значением функции Эйлера от n.
a) n = 7; b) n = 9; c) n = 11; d) n = 16; e) n = 6; f) n = 2;
1.7. Вычислить абсолютно наименьший и наименьший неотрицательный вычеты числа a по модулю m.
a) a = 12, m = 15; d) a = 50, m = 12; g) a = —80 , m = 100;
b) a = 35, m = 31; e) a= 8, m = 15; h) a = —4, m = 3;
c) a = —1, m = 81; f) a = 8, m = 17; i) a = 11, m = 11.
1.8. Вычислить обратный элемент, если он существует:
a) 5-1 mod 8; d) 14-1 mod 25; g) 46-1 mod 51;
b) 7-1 mod 41; e) 13-1 mod 92; h) 77-1 mod 101;
c) 23-1 mod 63; f) 9-1 mod 27; i) 22-1 mod 25.
1.9. Пользуясь теоремой Эйлера, вычислить:
a) 9042 mod 41; d) 8485 mod 187; g) 3161613 mod 16;
b) 34160003 mod 15; e) (-2)634178 mod 117; h) 5186609 mod 9;
c) (-5)100016 mod 11; f) 50190021 mod 38; i) 347174007 mod 349;
1.10. Решить сравнения:
a) 5x ≡ 3(mod 11); d) 6x ≡15(mod 21); g) 13x≡8(mod 16);
b) 8x ≡ 5(mod 13); e) 16x≡26(mod 62); h) 25x≡50(mod 125);
c) 15x≡25(mod 17); f) 21x≡14(mod 42); i) 13x≡37(mod 29).
1.11. Решить системы сравнений.
a) ; c) ; e) ;
b) ; d) ; f) .
1.12. Вычислить, пользуясь свойствами символа Якоби:
a) ; c) ; e) ; g) ; i) ; k) ;
b) ; d) ; f) ; h) ; j) ; l) .
1.13. Решить следующие квадратичные сравнения по простому модулю, если решение существует.
a) x2≡17(mod 19); d) x2≡2 (mod 7); g) x2≡3 (mod 41);
b) x2≡3 (mod 13); e) x2≡3 (mod 11); h) x2≡2 (mod 17);
c) x2≡8 (mod 41); f) 2x2≡10 (mod 11); i) 3x2≡15(mod 31).
1.14. Решить следующие квадратичные сравнения по составному модулю, если решение существует.
a) x2≡7(mod 9); g) x2≡1 (mod 32); m) x2≡11 (mod 35);
b) x2≡—1(mod 25); h) x2≡67 (mod 81); n) x2≡5 (mod 12);
c) x2≡32(mod 49); i) x2≡59 (mod 125); o) x2≡9 (mod 20);
d) x2≡1(mod 4); j) x2≡4(mod 6); p) x2≡31 (mod 105);
e) x2≡3(mod 8); k) x2≡1(mod 15); q) x2≡4 (mod 105);
f) x2≡9(mod 16); l) x2≡1(mod 24); r) x2≡ 16 (mod 75).
1.15. Определить, сколько решений имеют сравнения.
a) x2≡—1(mod 59); d) x2≡ 17(mod 32); g) x2≡1(mod 150);
b) x2≡ 3(mod 83); e) x2≡ 25(mod 96); h) x2≡4(mod 343);
c) x2≡ 1(mod 8); f) x2≡ 2(mod 315); i) x2≡1(mod 2).
1.16. Выписать все квадраты и все псевдоквадраты из приведенной системы вычетов по модулю n.
a) n = 15; b) n = 21; c) n = 33; d) n = 6; e) n = 14; f) n = 35.
1.17. Указать, какие их приведенных ниже чисел являются числами Блюма.
a) 7; b) 21; c) 47; d) 469; e) 35; f) 59.
1.18. Отыскать p8 и p9 – 8-е и 9-е простые числа, представимые в виде 4k+3. Составить число Блюма n=p8p9. На основе BBS-генератора с ключом s0=121 составить ключевую последовательность длиной 10 бит.
1.19. Существуют ли первообразные корни по модулю n, и если существуют, то сколько их?
a) n = 15; b) n = 71; c) n = 53; d) n = 202; e) n = 16; f) n = 25.
1.20. Найти первообразные корни по следующим модулям:
a) 3; c) 27; e) 26; g) 43; i) 169; k) 89;
b) 9; d) 13; f) 18; h) 86; j) 4; l) 41.
|
