Алгоритм исчисления порядка
Алгоритм исчисления порядка (index-calculus algorithm) — вероятностный алгоритм вычисления дискретного алгоритма в кольце вычетов по модулю простого числа. На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с криптографией. Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный компьютер. Примером такого алгоритма является ГОСТ Р 34.10-2012.
Содержание
История
Маурис Крайчик первым предложил основную идею данного алгоритма в своей книге «Théorie des Nombres» в 1922 году. После 1976 года задача дискретного логарифмирования становится важной для математики и криптоанализа. Это связано с созданием криптосистемы Диффи-Хелмана. В связи с этим в 1977 году Р.Меркле возобновил обсуждения данного алгоритма. Спустя два года он был впервые опубликован коллегами Меркеля. Наконец в 1979 году Адлерман оптимизировал его, исследовал трудоемкость и представил его в форме, которую мы знаем сейчас. В настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в некоторых конечных группах.
Постановка задачи дискретного логарифмирования
Для заданного простого числа <math>p </math> и двух целых чисел <math>g </math> и <math>c </math> требуется найти целое число <math>x </math>, удовлетворяющее сравнению:
| <math>g^x\equiv c\;\pmod{p},</math> |
где <math>c </math> является элементом циклической группы <math>G </math>, порожденной элементом <math>g </math>.
Алгоритм
Вход: g — генератор циклической группы порядка n, a — из циклической подгруппы, p — простое число, c — параметр надежности, обычно берут равным 10 или близкое к этому значению число(используется для реализации алгоритма на компьютере, если решает человек, то его не задают).
Задача: найти x такое, что
| <math>g^x\equiv c,</math> |
1) Выбираем факторную базу S = {p1, p2, p3, …, pt} (Если G = Z*p, то база состоит из t первых простых чисел)
2)Возводим g в случайную степень <math>k</math>, где k такое, что <math>0 \leqslant k < n </math>. Получаем: <math>g^k</math>.
3) Представляем gk следующим образом <math> g^k = {\displaystyle\prod_{i=1}^{t} p^{a_i}_i}</math>, где <math>a_i \geqslant 0</math> (То есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-ому пункту.
4) Из пункта 3 следует выражение: <math> k \equiv \sum_{i=1}^t a_ilog_gp_i\;(modn)</math>, полученное путём логарифмирования (берется сравнение по модулю порядка группы так, как мы работаем с показателем степени, а <math>g^n \equiv 1</math> в группе G). В этом выражении неизвестны логарифмы. Их t штук. Необходимо получить таких уравнений t+c штук, если этого не возможно сделать, возвращаемся к пункту 2(при реализации на компьютере) или получить необходимое количество уравнений, чтобы найти все неизвестные логарифмы(при решении человеком).
5) Решаем получившуюся систему уравнений, с t штук неизвестными и t+c штук сравнениями.
6) Выбираем случайное число k такое, что <math>0 \leqslant k < n </math>. Вычисляем <math>cg^k</math>.
7) Повторяем пункт 3, только для числа <math>cg^k</math>. Если не получается, то возвращаемся к 6-ому пункту.
8) Аналоногично пункту 4, получаем: <math> x = log_gc = \sum_{i=1}^t a_ilog_gp_i - k\;(modn)</math>, где <math>log_gp_i</math> (<math>1\leqslant i \leqslant t</math>), где <math>k\;(modn) = log _gg^kmod(n)</math> В этом пункте мы и решили задачу дискретного логарифма отыскав <math> x = log_gc</math>.
Выход: <math> x = log_gc</math>.
Пример
Решить уравнение: <math>17 \equiv 10^x\;(mod47)</math>
Выбираем факторную базу <math> S = \{2,3,5\}</math> Пусть k = 7 Вычисляем <math>g^k</math>
<math> k = 1 \;\;\;\; 10^1 mod 47 = 10 = 2 * 5</math>
<math> k = 2 \;\;\;\; 10^2 mod 47 \equiv 6 = 2 * 3</math>
<math> k = 3 \;\;\;\; 10^3 mod 47 \equiv 13 </math>
<math> k = 4 \;\;\;\; 10^4 mod 47 \equiv 36 = 2 * 2 * 3 * 3</math>
<math> k = 5 \;\;\;\; 10^5 mod 47 \equiv 31</math>
<math> k = 6 \;\;\;\; 10^6 mod 47 \equiv 28 = 2 * 2* 7</math>
<math> k = 7 \;\;\;\; 10^7 mod 47 \equiv 45 = 3 * 3 * 5</math>
Логарифмируем и обозначаем <math>U_i = log_gp_i</math> И получаем систему уравнений <math>\left\{\begin{matrix}U_1+U_3 = 1 \\ U_1 + U_2 = 2 \\ 2U_1 + 2U_2 = 4 \\ 2U_2 + U_3 = 7\end{matrix}\right.</math>
Решаем её
<math>u_2 = \frac{8}{3} (mod46) = 8*3^{-1}(mod46) = \{\varphi(46) = \varphi(2*23)\} = 22 = 8*3^{22}(mod46)\equiv 17</math>
Действительно, <math>10^8 mod47 \equiv 3</math>, следовательно <math>U_1 = 30</math>, <math>U_2 = 18</math>, <math>U_3 = 17</math>
Находим k такое, чтобы <math> cg^k = {\displaystyle\prod_{i=1}^{t} p^{a_i}_i}</math>
<math> 17 * 10^1 (mod47) = 29</math>
<math> 17 * 10 ^2 (mod47) = 8 = 2 * 2 * 2</math>
Следовательно <math> k = 2 </math>
Логарифмируем данное выражение и получаем
<math> log_a17 = [(log_a2 + log_a2 + log_a2) -2] mod46 = (3*30 - 2)mod 46 \equiv 42</math>
Ответ: <math> x = 42 </math>
Сложность
В данном алгоритме, количество итераций зависит, как от размера p, так и от размера факторной базы. Но факторную базу мы выбираем заранее, и её размер является фиксированным. Поэтому итоговая сложность определяется только размером простого числа и равняется: <math> O(c_1*2^{(c_2 + o(1))\sqrt{logp\;loglogp}})</math> , где <math>c_1</math>,<math>c_2</math> — некоторые константы, зависящие от промежуточных вычислений, в частности, от выбора факторной базы.
Усовершенствования
Ускоренный алгоритм исчисления порядка, суть которого состоит в том, чтобы использовать таблицу индексов.
Сложность
Вычислительная сложность снижена до <math>O(2log_2(p))</math>, по сравнению с оригинальном алгоритмом.
См. также
Напишите отзыв о статье "Алгоритм исчисления порядка"
Ссылки
- refdb.ru/look/1629414-pall.html
- pratsi.opu.ua/app/webroot/articles/1414145386.pdf
- en.wikipedia.org/wiki/Index_calculus_algorithm
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Алгоритм исчисления порядка
И, не дожидаясь ответа от посторонившегося часового, Долохов шагом поехал в гору.Заметив черную тень человека, переходящего через дорогу, Долохов остановил этого человека и спросил, где командир и офицеры? Человек этот, с мешком на плече, солдат, остановился, близко подошел к лошади Долохова, дотрогиваясь до нее рукою, и просто и дружелюбно рассказал, что командир и офицеры были выше на горе, с правой стороны, на дворе фермы (так он называл господскую усадьбу).
Проехав по дороге, с обеих сторон которой звучал от костров французский говор, Долохов повернул во двор господского дома. Проехав в ворота, он слез с лошади и подошел к большому пылавшему костру, вокруг которого, громко разговаривая, сидело несколько человек. В котелке с краю варилось что то, и солдат в колпаке и синей шинели, стоя на коленях, ярко освещенный огнем, мешал в нем шомполом.
– Oh, c'est un dur a cuire, [С этим чертом не сладишь.] – говорил один из офицеров, сидевших в тени с противоположной стороны костра.
– Il les fera marcher les lapins… [Он их проберет…] – со смехом сказал другой. Оба замолкли, вглядываясь в темноту на звук шагов Долохова и Пети, подходивших к костру с своими лошадьми.
– Bonjour, messieurs! [Здравствуйте, господа!] – громко, отчетливо выговорил Долохов.
Офицеры зашевелились в тени костра, и один, высокий офицер с длинной шеей, обойдя огонь, подошел к Долохову.
– C'est vous, Clement? – сказал он. – D'ou, diable… [Это вы, Клеман? Откуда, черт…] – но он не докончил, узнав свою ошибку, и, слегка нахмурившись, как с незнакомым, поздоровался с Долоховым, спрашивая его, чем он может служить. Долохов рассказал, что он с товарищем догонял свой полк, и спросил, обращаясь ко всем вообще, не знали ли офицеры чего нибудь о шестом полку. Никто ничего не знал; и Пете показалось, что офицеры враждебно и подозрительно стали осматривать его и Долохова. Несколько секунд все молчали.
– Si vous comptez sur la soupe du soir, vous venez trop tard, [Если вы рассчитываете на ужин, то вы опоздали.] – сказал с сдержанным смехом голос из за костра.
Долохов отвечал, что они сыты и что им надо в ночь же ехать дальше.
Он отдал лошадей солдату, мешавшему в котелке, и на корточках присел у костра рядом с офицером с длинной шеей. Офицер этот, не спуская глаз, смотрел на Долохова и переспросил его еще раз: какого он был полка? Долохов не отвечал, как будто не слыхал вопроса, и, закуривая коротенькую французскую трубку, которую он достал из кармана, спрашивал офицеров о том, в какой степени безопасна дорога от казаков впереди их.
– Les brigands sont partout, [Эти разбойники везде.] – отвечал офицер из за костра.
Долохов сказал, что казаки страшны только для таких отсталых, как он с товарищем, но что на большие отряды казаки, вероятно, не смеют нападать, прибавил он вопросительно. Никто ничего не ответил.
«Ну, теперь он уедет», – всякую минуту думал Петя, стоя перед костром и слушая его разговор.
Но Долохов начал опять прекратившийся разговор и прямо стал расспрашивать, сколько у них людей в батальоне, сколько батальонов, сколько пленных. Спрашивая про пленных русских, которые были при их отряде, Долохов сказал:
– La vilaine affaire de trainer ces cadavres apres soi. Vaudrait mieux fusiller cette canaille, [Скверное дело таскать за собой эти трупы. Лучше бы расстрелять эту сволочь.] – и громко засмеялся таким странным смехом, что Пете показалось, французы сейчас узнают обман, и он невольно отступил на шаг от костра. Никто не ответил на слова и смех Долохова, и французский офицер, которого не видно было (он лежал, укутавшись шинелью), приподнялся и прошептал что то товарищу. Долохов встал и кликнул солдата с лошадьми.
«Подадут или нет лошадей?» – думал Петя, невольно приближаясь к Долохову.
Лошадей подали.
– Bonjour, messieurs, [Здесь: прощайте, господа.] – сказал Долохов.
Петя хотел сказать bonsoir [добрый вечер] и не мог договорить слова. Офицеры что то шепотом говорили между собою. Долохов долго садился на лошадь, которая не стояла; потом шагом поехал из ворот. Петя ехал подле него, желая и не смея оглянуться, чтоб увидать, бегут или не бегут за ними французы.
Выехав на дорогу, Долохов поехал не назад в поле, а вдоль по деревне. В одном месте он остановился, прислушиваясь.
– Слышишь? – сказал он.
Петя узнал звуки русских голосов, увидал у костров темные фигуры русских пленных. Спустившись вниз к мосту, Петя с Долоховым проехали часового, который, ни слова не сказав, мрачно ходил по мосту, и выехали в лощину, где дожидались казаки.
– Ну, теперь прощай. Скажи Денисову, что на заре, по первому выстрелу, – сказал Долохов и хотел ехать, но Петя схватился за него рукою.
– Нет! – вскрикнул он, – вы такой герой. Ах, как хорошо! Как отлично! Как я вас люблю.
– Хорошо, хорошо, – сказал Долохов, но Петя не отпускал его, и в темноте Долохов рассмотрел, что Петя нагибался к нему. Он хотел поцеловаться. Долохов поцеловал его, засмеялся и, повернув лошадь, скрылся в темноте.
