Алгоритм Полига — Хеллмана

15.12.2020

Алгоритм Полига — Хеллмана (также называемый алгоритм Сильвера — Полига — Хеллмана) — детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Одной из особенностей алгоритма является то, что для простых чисел специального вида можно находить дискретный логарифм за полиномиальное время.

История

Данный алгоритм был придуман американским математиком Роландом Сильвером (англ. Roland Silver), но впервые был опубликован другими двумя американскими математиками Стивеном Полигом (англ. Stephen Pohlig) и Мартином Хеллманом в 1978 году в статье «An improved algorithm for computing logarithms over GF(p) and its cryptographic significance», которые независимо от Роланда Сильвера разработали данный алгоритм.

Исходные данные

Пусть задано сравнение

и известно разложение числа p − 1 {displaystyle p-1} на простые множители:

Необходимо найти число x , 0 ≤ x < p − 1 {displaystyle x,;0leq x<p-1} , удовлетворяющее сравнению (1).

Идея алгоритма

Суть алгоритма в том, что достаточно найти x {displaystyle x} по модулям q i α i {displaystyle q_{i}^{alpha _{i}}} для всех i {displaystyle i} , а затем решение исходного сравнения можно найти с помощью китайской теоремы об остатках.
Чтобы найти x {displaystyle x} по каждому из таких модулей, нужно решить сравнение:

( a x ) ( p − 1 ) / q i α i ≡ b ( p − 1 ) / q i α i ( mod p ) {displaystyle (a^{x})^{(p-1)/{q_{i}^{alpha _{i}}}}equiv b^{(p-1)/{q_{i}^{alpha _{i}}}}{pmod {p}}} .

Описание алгоритма

Упрощённый вариант

Лучшим путём, чтобы разобраться с данным алгоритмом, будет рассмотрение особого случая, в котором p = 2 n + 1 {displaystyle p=2^{n}+1} .

Нам даны a {displaystyle a} , p {displaystyle p} и b {displaystyle b} , при этом a {displaystyle a} есть примитивный элемент G F ( p ) {displaystyle GF(p)} и нужно найти такое x {displaystyle x} , чтобы удовлетворялось a x ≡ b ( mod p ) {displaystyle a^{x}equiv b{pmod {p}}} .

Принимается, что 0 ≤ x ≤ p − 2 {displaystyle 0leq xleq p-2} , так как x = p − 1 {displaystyle x=p-1} неотличимо от x = 0 {displaystyle x=0} , потому что в нашем случае примитивный элемент a {displaystyle a} по определению имеет степень p − 1 {displaystyle p-1} , следовательно:

a p − 1 ≡ 1 ≡ a 0 ( mod p ) {displaystyle a^{p-1}equiv 1equiv a^{0}{pmod {p}}} .

Когда p = 2 n + 1 {displaystyle p=2^{n}+1} , легко определить x {displaystyle x} двоичным разложением c коэффициентами { q 0 , q 1 , … , q n − 1 } {displaystyle {q_{0},q_{1},dots ,q_{n-1}}} , например:

x = ∑ i = 0 n − 1 q i 2 i = q 0 + q 1 2 1 + ⋯ + q n − 1 2 n − 1 {displaystyle x=sum limits _{i=0}^{n-1}q_{i}2^{i}=q_{0}+q_{1}2^{1}+cdots +q_{n-1}2^{n-1}}

Самый младший бит q 0 {displaystyle q_{0}} определяется путём возведения b {displaystyle b} в степень ( p − 1 ) / 2 = 2 n − 1 {displaystyle (p-1)/2=2^{n-1}} и применением правила

b ( p − 1 ) / 2 ( mod p ) ≡ { + 1 , q 0 = 0 − 1 , q 0 = 1. {displaystyle b^{(p-1)/2}{pmod {p}}equiv {egin{cases}+1,&q_{0}=0-1,&q_{0}=1.end{cases}}} Вывод верхнего правила

Рассмотрим ранее полученное сравнение:

a p − 1 ≡ 1 ( mod p ) ⇒ a ( p − 1 ) / 2 ≡ ± 1 ( mod p ) {displaystyle a^{p-1}equiv 1{pmod {p}}Rightarrow a^{(p-1)/2}equiv pm 1{pmod {p}}} ,

но a {displaystyle a} в степени ( p − 1 ) / 2 < p − 1 {displaystyle (p-1)/2<p-1} по определению принимает значение, отличное от 1 {displaystyle 1} , поэтому остаётся только одно сравнение:

a ( p − 1 ) / 2 ≡ − 1 ( mod p ) {displaystyle a^{(p-1)/2}equiv -1{pmod {p}}} .

Возведём сравнение (1) в степень ( p − 1 ) / 2 {displaystyle (p-1)/2} и подставим выше полученное сравнение:

b ( p − 1 ) / 2 ≡ ( a x ) ( p − 1 ) / 2 ≡ ( a ( p − 1 ) / 2 ) x ≡ ( − 1 ) x ( mod p ) {displaystyle b^{(p-1)/2}equiv (a^{x})^{(p-1)/2}equiv (a^{(p-1)/2})^{x}equiv (-1)^{x}{pmod {p}}}

Равенство ( − 1 ) x = 1 {displaystyle (-1)^{x}=1} верно, если x {displaystyle x} чётное, то есть в разложении в виде многочлена свободный член q 0 {displaystyle q_{0}} равен 0 {displaystyle 0} , следовательно ( − 1 ) x = − 1 {displaystyle (-1)^{x}=-1} верно, когда q 0 = 1 {displaystyle q_{0}=1} .

Теперь преобразуем известное разложение и введём новую переменную z 1 {displaystyle z_{1}} :

b ≡ a x ≡ a x 1 + q 0 ( mod p ) ⇒ z 1 ≡ b a − q 0 ≡ a x 1 ( mod p ) {displaystyle bequiv a^{x}equiv a^{x_{1}+q_{0}}{pmod {p}}Rightarrow z_{1}equiv ba^{-q_{0}}equiv a^{x_{1}}{pmod {p}}} ,

где

x 1 = ∑ i = 1 n − 1 q i 2 i = q 1 2 1 + q 2 2 2 + ⋯ + q n − 1 2 n − 1 {displaystyle x_{1}=sum limits _{i=1}^{n-1}q_{i}2^{i}=q_{1}2^{1}+q_{2}2^{2}+cdots +q_{n-1}2^{n-1}}

Понятно, что x 1 {displaystyle x_{1}} делится на 4 {displaystyle 4} при q 1 = 0 {displaystyle q_{1}=0} , а при q 1 = 1 {displaystyle q_{1}=1} делится на 2 {displaystyle 2} , а на 4 {displaystyle 4} уже нет.

Рассуждая как раньше, получим сравнение:

z 1 ( p − 1 ) / 4 ( mod p ) ≡ { + 1 , q 1 = 0 − 1 , q 1 = 1 , {displaystyle z_{1}^{(p-1)/4}{pmod {p}}equiv {egin{cases}+1,&q_{1}=0-1,&q_{1}=1,end{cases}}}

из которого находим q 1 {displaystyle q_{1}} .

Оставшиеся биты получаются похожим способом. Напишем общее решение нахождения q i {displaystyle q_{i}} с новыми обозначениями:

m i = ( p − 1 ) / 2 i + 1 {displaystyle m_{i}=(p-1)/2^{i+1}} z i ≡ b ⋅ a − q 0 − q 1 2 1 − ⋯ − q i − 1 2 i − 1 ≡ a x i ( mod p ) {displaystyle z_{i}equiv bcdot a^{-q_{0}-q_{1}2^{1}-dots -q_{i-1}2^{i-1}}equiv a^{x_{i}}{pmod {p}}} ,

где

x i = ∑ k = i n − 1 q k 2 k {displaystyle x_{i}=sum limits _{k=i}^{n-1}q_{k}2^{k}} .

Таким образом, возведение z i {displaystyle z_{i}} в степень m i {displaystyle m_{i}} даёт:

z i m i ≡ a ( x i ⋅ m i ) ≡ ( a ( p − 1 ) / 2 ) ( x i / 2 i ) ≡ ( − 1 ) x i / 2 i ≡ ( − 1 ) q i ( mod p ) {displaystyle z_{i}^{m_{i}}equiv a^{(x_{i}cdot m_{i})}equiv left(a^{(p-1)/2} ight)^{(x_{i}/2^{i})}equiv (-1)^{x_{i}/2^{i}}equiv (-1)^{q_{i}}{pmod {p}}} .

Следовательно:

z i m i ( mod p ) ≡ { + 1 , q i = 0 − 1 , q i = 1 , {displaystyle z_{i}^{m_{i}}{pmod {p}}equiv {egin{cases}+1,&q_{i}=0-1,&q_{i}=1,end{cases}}}

из которого находим q i {displaystyle q_{i}} .

Найдя все биты, получаем требуемое решение x {displaystyle x} .

Пример

Дано:

a = 3 , b = 11 , p = 17 = 2 4 + 1 {displaystyle a=3,;b=11,;p=17=2^{4}+1}

Найти:

x {displaystyle x}

Решение:
Получаем p − 1 = 2 4 {displaystyle p-1=2^{4}} . Следовательно x {displaystyle x} имеет вид:

x = q 0 + q 1 2 1 + q 2 2 2 + q 3 2 3 {displaystyle x=q_{0}+q_{1}2^{1}+q_{2}2^{2}+q_{3}2^{3}}

Находим q 0 {displaystyle q_{0}} :

b ( p − 1 ) / 2 ≡ 11 ( 17 − 1 ) / 2 ≡ 11 8 ≡ ( − 6 ) 8 ≡ ( 36 ) 4 ≡ 2 4 ≡ 16 ≡ − 1 ( mod 17 ) ⇒ q 0 = 1 {displaystyle b^{(p-1)/2}equiv 11^{(17-1)/2}equiv 11^{8}equiv (-6)^{8}equiv (36)^{4}equiv 2^{4}equiv 16equiv -1{pmod {17}}Rightarrow q_{0}=1}

Подсчитываем z 1 {displaystyle z_{1}} и m 1 {displaystyle m_{1}} :

z 1 ≡ b ⋅ a − q 0 ≡ 11 ⋅ 3 − 1 ≡ 11 ⋅ 6 ≡ 66 ≡ − 2 ( mod 17 ) {displaystyle z_{1}equiv bcdot a^{-q_{0}}equiv 11cdot 3^{-1}equiv 11cdot 6equiv 66equiv -2{pmod {17}}} m 1 = ( p − 1 ) / 2 1 + 1 = ( 17 − 1 ) / 2 2 = 4 {displaystyle m_{1}=(p-1)/2^{1+1}=(17-1)/2^{2}=4}

Находим q 1 {displaystyle q_{1}} :

z 1 m 1 ≡ ( − 2 ) 4 ≡ 16 ≡ − 1 ( mod 17 ) ⇒ q 1 = 1 {displaystyle z_{1}^{m_{1}}equiv (-2)^{4}equiv 16equiv -1{pmod {17}}Rightarrow q_{1}=1}

Подсчитываем z 2 {displaystyle z_{2}} и m 2 {displaystyle m_{2}} :

z 2 ≡ z 1 ⋅ a − q 1 2 1 ≡ ( − 2 ) ⋅ 3 − 2 ≡ ( − 2 ) ⋅ 6 2 ≡ ( − 2 ) ⋅ 36 ≡ ( − 2 ) ⋅ 2 ≡ − 4 ≡ 13 ( mod 17 ) {displaystyle z_{2}equiv z_{1}cdot a^{-q_{1}2^{1}}equiv (-2)cdot 3^{-2}equiv (-2)cdot 6^{2}equiv (-2)cdot 36equiv (-2)cdot 2equiv -4equiv 13{pmod {17}}} m 2 = ( p − 1 ) / 2 2 + 1 = ( 17 − 1 ) / 2 3 = 2 {displaystyle m_{2}=(p-1)/2^{2+1}=(17-1)/2^{3}=2}

Находим q 2 {displaystyle q_{2}} :

z 2 m 2 ≡ 13 2 ≡ ( − 4 ) 2 ≡ 16 ≡ − 1 ( mod 17 ) ⇒ q 2 = 1 {displaystyle z_{2}^{m_{2}}equiv 13^{2}equiv (-4)^{2}equiv 16equiv -1{pmod {17}}Rightarrow q_{2}=1}

Подсчитываем z 3 {displaystyle z_{3}} и m 3 {displaystyle m_{3}} :

z 3 ≡ z 2 ⋅ a − q 2 ⋅ 2 2 ≡ 13 ⋅ 3 − 4 ≡ 13 ⋅ 9 − 2 ≡ 13 ⋅ 2 2 ≡ ( − 4 ) ⋅ 4 ≡ − 16 ≡ 1 ( mod 17 ) {displaystyle z_{3}equiv z_{2}cdot a^{-q_{2}cdot 2^{2}}equiv 13cdot 3^{-4}equiv 13cdot 9^{-2}equiv 13cdot 2^{2}equiv (-4)cdot 4equiv -16equiv 1{pmod {17}}} m 3 = ( p − 1 ) / 2 3 + 1 = ( 17 − 1 ) / 2 4 = 1 {displaystyle m_{3}=(p-1)/2^{3+1}=(17-1)/2^{4}=1}

Находим q 3 {displaystyle q_{3}} :

z 3 m 3 ≡ 1 1 ≡ 1 ( mod 17 ) ⇒ q 3 = 0 {displaystyle z_{3}^{m_{3}}equiv 1^{1}equiv 1{pmod {17}}Rightarrow q_{3}=0}

Находим искомый x {displaystyle x} :

x = 1 + 1 ⋅ 2 1 + 1 ⋅ 2 2 + 0 ⋅ 2 3 ≡ 7 {displaystyle x=1+1cdot 2^{1}+1cdot 2^{2}+0cdot 2^{3}equiv 7}

Ответ: x = 7 {displaystyle x=7}

Основное описание

Шаг 1 (составление таблицы). Составить таблицу значений { r i , j } {displaystyle {r_{i,j}}} , где r i , j = a j ⋅ p − 1 q i , i ∈ { 1 , … , k } , j ∈ { 0 , … , q i − 1 } . {displaystyle r_{i,j}=a^{jcdot {frac {p-1}{q_{i}}}},iin {1,dots ,k},jin {0,dots ,q_{i}-1}.} Шаг 2 (вычисление log a ⁡ b mod q i α i {displaystyle log _{a}{b};{mod {q_{i}^{alpha _{i}}}}} ). Для i от 1 до k: Пусть x ≡ log a ⁡ b ≡ x 0 + x 1 q i + . . . + x α i − 1 q i α i − 1 ( mod q i α i ) , {displaystyle xequiv log _{a}{b}equiv x_{0}+x_{1}q_{i}+...+x_{alpha _{i}-1}q_{i}^{alpha _{i}-1}{pmod {q_{i}^{alpha _{i}}}},} где 0 ≤ x i ≤ q i − 1 {displaystyle 0leq x_{i}leq q_{i}-1} . Тогда верно сравнение: a x 0 ⋅ p − 1 q i ≡ b p − 1 q i ( mod p ) {displaystyle a^{x_{0}cdot {frac {p-1}{q_{i}}}}equiv b^{frac {p-1}{q_{i}}}{pmod {p}}} Вывод верхнего сравнения

Возведём левую и правую части сравнения (1) в степень ( p − 1 ) / q i {displaystyle (p-1)/q_{i}} :

a x ⋅ p − 1 q i ≡ b p − 1 q i ( mod p ) {displaystyle a^{xcdot {frac {p-1}{q_{i}}}}equiv b^{frac {p-1}{q_{i}}}{pmod {p}}}

Подставим x {displaystyle x} и преобразуем сравнение:

a x 0 ⋅ p − 1 q i + x 1 ⋅ ( p − 1 ) + x 2 ⋅ q i ⋅ ( p − 1 ) + ⋯ + x α i − 1 ⋅ q i α i − 2 ⋅ ( p − 1 ) ≡ b p − 1 q i ( mod p ) {displaystyle a^{x_{0}cdot {frac {p-1}{q_{i}}}+x_{1}cdot (p-1)+x_{2}cdot q_{i}cdot (p-1)+dots +x_{alpha _{i}-1}cdot q_{i}^{alpha _{i}-2}cdot (p-1)}equiv b^{frac {p-1}{q_{i}}}{pmod {p}}} a x 0 ⋅ p − 1 q i ⋅ a x 1 ⋅ ( p − 1 ) ⋅ a x 2 ⋅ q i ⋅ ( p − 1 ) ⋅ ⋯ ⋅ a x α i − 1 ⋅ q i α i − 2 ⋅ ( p − 1 ) ≡ b p − 1 q i ( mod p ) {displaystyle a^{x_{0}cdot {frac {p-1}{q_{i}}}}cdot a^{x_{1}cdot (p-1)}cdot a^{x_{2}cdot q_{i}cdot (p-1)}cdot dots cdot a^{x_{alpha _{i}-1}cdot q_{i}^{alpha _{i}-2}cdot (p-1)}equiv b^{frac {p-1}{q_{i}}}{pmod {p}}}

Т.к. a {displaystyle a} - примитивный элемент, следовательно верны сравнения вида:

a m ⋅ ( p − 1 ) ≡ 1 ( mod p ) , ∀ m ∈ { 0 , 1 , … , p − 1 } {displaystyle a^{mcdot (p-1)}equiv 1{pmod {p}},;forall min {0,1,dots ,p-1}}

Получаем

a x 0 ⋅ p − 1 q i ⋅ 1 ⋅ 1 ⋅ ⋯ ⋅ 1 ≡ b p − 1 q i ( mod p ) {displaystyle a^{x_{0}cdot {frac {p-1}{q_{i}}}}cdot 1cdot 1cdot dots cdot 1equiv b^{frac {p-1}{q_{i}}}{pmod {p}}} a x 0 ⋅ p − 1 q i ≡ b p − 1 q i ( mod p ) {displaystyle a^{x_{0}cdot {frac {p-1}{q_{i}}}}equiv b^{frac {p-1}{q_{i}}}{pmod {p}}} С помощью таблицы, составленной на шаге 1, находим x 0 . {displaystyle x_{0}.} Для j от 0 до α i − 1 {displaystyle alpha _{i}-1} Рассматриваем сравнение a x j ⋅ p − 1 q i ≡ ( b a − x 0 − x 1 q i . . . − x j − 1 q i j − 1 ) p − 1 q i j + 1 ( mod p ) {displaystyle a^{x_{j}cdot {frac {p-1}{q_{i}}}}equiv (ba^{-x_{0}-x_{1}q_{i}...-x_{j-1}q_{i}^{j-1}})^{frac {p-1}{q_{i}^{j+1}}}{pmod {p}}} Решение опять же находится по таблице Конец цикла по j Конец цикла по i Шаг 3 (нахождение ответа). Найдя log a ⁡ b mod q i α i {displaystyle log _{a}{b};{mod {q_{i}^{alpha _{i}}}}} для всех i, находим log a ⁡ b mod ( p − 1 ) {displaystyle log _{a}{b};{mod {;}}(p-1)} по китайской теореме об остатках.

Пример

Необходимо найти дискретный логарифм 28 {displaystyle 28} по основанию 2 {displaystyle 2} в G F ( 37 ) {displaystyle GF(37)} , другими словами найти x {displaystyle x} для:

2 x ≡ 28 ( mod 37 ) {displaystyle 2^{x}equiv 28{pmod {37}}} .

Находим разложение φ ( 37 ) = 37 − 1 = 36 = 2 2 ⋅ 3 2 {displaystyle varphi (37)=37-1=36=2^{2}cdot 3^{2}} .

Получаем q 1 = 2 , α 1 = 2 , q 2 = 3 , α 2 = 2 {displaystyle q_{1}=2,alpha _{1}=2,q_{2}=3,alpha _{2}=2} .

Составляем таблицу r i j {displaystyle r_{ij}} :

r 20 ≡ 2 0 ⋅ 37 − 1 2 ≡ 1 ( mod 37 ) {displaystyle r_{20}equiv 2^{0cdot {frac {37-1}{2}}}equiv 1{pmod {37}}} r 21 ≡ 2 1 ⋅ 37 − 1 2 ≡ 2 18 ≡ − 1 ( mod 37 ) {displaystyle r_{21}equiv 2^{1cdot {frac {37-1}{2}}}equiv 2^{18}equiv -1{pmod {37}}} r 30 ≡ 2 0 ⋅ 37 − 1 3 ≡ 1 ( mod 37 ) {displaystyle r_{30}equiv 2^{0cdot {frac {37-1}{3}}}equiv 1{pmod {37}}} r 31 ≡ 2 1 ⋅ 37 − 1 3 ≡ 2 12 ≡ 26 ( mod 37 ) {displaystyle r_{31}equiv 2^{1cdot {frac {37-1}{3}}}equiv 2^{12}equiv 26{pmod {37}}} r 32 ≡ 2 2 ⋅ 37 − 1 3 ≡ 2 24 ≡ 10 ( mod 37 ) {displaystyle r_{32}equiv 2^{2cdot {frac {37-1}{3}}}equiv 2^{24}equiv 10{pmod {37}}}

Рассматриваем q 1 = 2 {displaystyle q_{1}=2} . Для x {displaystyle x} верно:

x ≡ x 0 + x 1 q 1 ( mod q 1 α i ) ≡ x 0 + x 1 ⋅ 2 ( mod 2 2 ) {displaystyle xequiv x_{0}+x_{1}q_{1}{pmod {q_{1}^{alpha _{i}}}}equiv x_{0}+x_{1}cdot 2{pmod {2^{2}}}}

Находим x 0 {displaystyle x_{0}} из сравнения:

a x 0 ⋅ p − 1 q 1 ≡ b p − 1 q 1 ( mod p ) ⇒ 2 x 0 ⋅ 37 − 1 2 ≡ 28 37 − 1 2 ≡ 28 18 ≡ 1 ( mod 37 ) {displaystyle a^{x_{0}cdot {frac {p-1}{q_{1}}}}equiv b^{frac {p-1}{q_{1}}}{pmod {p}}Rightarrow 2^{x_{0}cdot {frac {37-1}{2}}}equiv 28^{frac {37-1}{2}}equiv 28^{18}equiv 1{pmod {37}}}

Из таблицы находим, что при x 0 = 0 {displaystyle x_{0}=0} верно выше полученное сравнение.

Находим x 1 {displaystyle x_{1}} из сравнения:

a x 1 ⋅ p − 1 q i ≡ ( b ⋅ a − x 0 ) p − 1 q i 2 ⇒ 2 x 1 ⋅ 37 − 1 2 ≡ ( 28 ⋅ 2 − 0 ) 37 − 1 4 ≡ 28 9 ≡ − 1 ( mod 37 ) {displaystyle a^{x_{1}cdot {frac {p-1}{q_{i}}}}equiv (bcdot a^{-x_{0}})^{frac {p-1}{q_{i}^{2}}}Rightarrow 2^{x_{1}cdot {frac {37-1}{2}}}equiv (28cdot 2^{-0})^{frac {37-1}{4}}equiv 28^{9}equiv -1{pmod {37}}}

Из таблицы получаем, что при x 1 = 1 {displaystyle x_{1}=1} верно выше полученное сравнение. Находим x {displaystyle x} :

x ≡ 0 + 1 ⋅ 2 ≡ 2 ( mod 4 ) {displaystyle xequiv 0+1cdot 2equiv 2{pmod {4}}}

Теперь рассматриваем q 2 = 3 {displaystyle q_{2}=3} . Для x {displaystyle x} верно:

x ≡ x 0 + x 1 ⋅ 3 ( mod 3 2 ) {displaystyle xequiv x_{0}+x_{1}cdot 3{pmod {3^{2}}}}

По аналогии находим x 0 {displaystyle x_{0}} и x 1 {displaystyle x_{1}} :

2 x 0 ⋅ 37 − 1 3 ≡ 28 37 − 1 3 ≡ 28 12 ≡ 26 ( mod 37 ) ⇒ x 0 = 1 {displaystyle 2^{x_{0}cdot {frac {37-1}{3}}}equiv 28^{frac {37-1}{3}}equiv 28^{12}equiv 26{pmod {37}}Rightarrow x_{0}=1} 2 x 1 ⋅ 37 − 1 3 ≡ ( 28 ⋅ 2 − 1 ) 37 − 1 3 2 ≡ 14 4 ≡ 10 ( mod 37 ) ⇒ x 1 = 2 {displaystyle 2^{x_{1}cdot {frac {37-1}{3}}}equiv (28cdot 2^{-1})^{frac {37-1}{3^{2}}}equiv 14^{4}equiv 10{pmod {37}}Rightarrow x_{1}=2}

Получаем x {displaystyle x} :

x ≡ 1 + 2 ⋅ 3 ≡ 7 ( mod 9 ) {displaystyle xequiv 1+2cdot 3equiv 7{pmod {9}}}

Получаем систему:

{ x ≡ 2 ( mod 4 ) x ≡ 7 ( mod 9 ) {displaystyle {egin{cases}xequiv 2{pmod {4}}xequiv 7{pmod {9}}end{cases}}}

Решим систему. Первое сравнение преобразуем в равенство, которое подставляем во второе сравнение:

x = 2 + 4 ⋅ t ⇒ 2 + 4 ⋅ t ≡ 7 ( mod 9 ) ⇒ 4 ⋅ t ≡ 5 ( mod 9 ) ⇒ {displaystyle x=2+4cdot tRightarrow 2+4cdot tequiv 7{pmod {9}}Rightarrow 4cdot tequiv 5{pmod {9}}Rightarrow } t ≡ 5 ⋅ ( 4 ) − 1 ≡ 5 ⋅ ( − 2 ) ≡ − 10 ≡ 8 ( mod 9 ) {displaystyle tequiv 5cdot (4)^{-1}equiv 5cdot (-2)equiv -10equiv 8{pmod {9}}}

Подставляем найденное t {displaystyle t} и получаем искомое x {displaystyle x} :

x ≡ 2 + 4 ⋅ 8 ≡ 34 ( mod 36 ) ≡ 34 ( mod 37 ) {displaystyle xequiv 2+4cdot 8equiv 34{pmod {36}}equiv 34{pmod {37}}}

Ответ: x = 34 {displaystyle x=34} .

Сложность алгоритма

Если известно разложение (2), то сложность алгоритма является

O ( ∑ i = 1 k α i ( log 2 ⁡ p + q i 1 − r i ( 1 + log 2 ⁡ q i r i ) ) ) {displaystyle Oleft(sum limits _{i=1}^{k}alpha _{i}left(log _{2}{p}+q_{i}^{1-r_{i}}(1+log _{2}{q_{i}^{r_{i}}}) ight) ight)} , где 0 ≤ r i ≤ 1 {displaystyle 0leq r_{i}leq 1} .

При этом необходимо O ( log 2 ⁡ p ∑ i = 1 k ( 1 + p i r i ) ) {displaystyle Oleft(log _{2}{p}sum limits _{i=1}^{k}left(1+p_{i}^{r_{i}} ight) ight)} бит памяти.

В общем случае сложность алгоритма также можно оценить как

O ( ∑ i = 1 k α i q i + log ⁡ p ) {displaystyle Oleft(sum limits _{i=1}^{k}alpha _{i}q_{i}+log {p} ight)} .

Если при обработке каждого qi использовать ускоренные методы (например, алгоритм Шенкса), то общая оценка снизится до

O ( ∑ i = 1 k α i q i + log ⁡ p ) {displaystyle Oleft(sum limits _{i=1}^{k}alpha _{i}{sqrt {q_{i}}}+log {p} ight)} .

В указанных оценках подразумевается, что арифметические операции по модулю p выполняются за один шаг. На самом деле это не так — например, сложение по модулю p требует O(log p) элементарных операций. Но поскольку аналогичные уточнения имеют место для любого алгоритма, данный множитель часто отбрасывается.

Полиномиальная сложность

Когда простые множители { q i } i = 1 k {displaystyle left{q_{i} ight}_{i=1}^{k}} малы, то сложность алгоритма можно оценивать как O ( ( log 2 ⁡ p ) 2 ) {displaystyle Oleft((log _{2}p)^{2} ight)} .

Алгоритм имеет полиномиальную сложность в общем виде O ( ( log ⁡ p ) c 1 ) {displaystyle Oleft((log p)^{c_{1}} ight)} в случае, когда все простые множители { q i } i = 1 k {displaystyle left{q_{i} ight}_{i=1}^{k}} не превосходят ( log ⁡ p ) c 2 {displaystyle (log p)^{c_{2}}} ,
где c 1 , c 2 {displaystyle c_{1},c_{2}} — положительные постоянные.

Пример

Верно для простых p {displaystyle p} вида p = 2 α + 1 , p = 2 α 1 3 α 2 + 1 {displaystyle p=2^{alpha }+1,;p=2^{alpha _{1}}3^{alpha _{2}}+1} .

Экспоненциальная сложность

Если имеется простой множитель q i {displaystyle q_{i}} такой, что q i ≥ p c {displaystyle q_{i}geq p^{c}} , где c ≥ 0 {displaystyle cgeq 0} .

Применение

Алгоритм Полига—Хеллмана крайне эффективен, если p − 1 {displaystyle p-1} раскладывается на небольшие простые множители. Это очень важно учитывать при выборе параметров криптографических схем. Иначе схема будет ненадёжной.

Замечание

Для применения алгоритма Полига-Хеллмана необходимо знать разложение p − 1 {displaystyle p-1} на множители. В общем случае задача факторизации — достаточно трудоёмкая, однако если делители числа — небольшие (в том смысле, о котором сказано выше), то это число можно быстро разложить на множители даже методом последовательного деления. Таким образом, в том случае, когда эффективен алгоритм Полига-Хеллмана, необходимость факторизации не усложняет задачу.



Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru © 2020
При цитировании и использовании любых материалов ссылка на сайт обязательна