Алгоритм Кантора – Цассенхауза - Cantor–Zassenhaus algorithm

В вычислительный алгебра, то Алгоритм Кантора – Цассенхауза это метод факторинга многочлены над конечные поля (также называемые полями Галуа).

Алгоритм состоит в основном из возведения в степень и полиномиального НОД вычисления. Это было изобретено Дэвид Г. Кантор и Ганс Цассенхаус в 1981 г.

Возможно, это доминирующий алгоритм решения проблемы, заменивший предыдущий Алгоритм Берлекампа 1967 года. В настоящее время он внедрен во многих системы компьютерной алгебры.

Обзор

Фон

Алгоритм Кантора – Цассенхауза принимает в качестве входных данных бесквадратный многочлен ${displaystyle f (x)}$ (то есть без повторяющихся факторов) степени п с коэффициентами в конечном поле ${displaystyle mathbb {F} _ {q}}$ чей неприводимый многочлен факторы имеют одинаковую степень (существуют алгоритмы для эффективного факторизации произвольных многочленов в произведение многочленов, удовлетворяющих этим условиям, например, ${displaystyle f (x) / gcd (f (x), f '(x))}$ является бесквадратным многочленом с теми же множителями, что и ${displaystyle f (x)}$, так что алгоритм Кантора – Цассенхауза может быть использован для факторизации произвольных многочленов). На выходе он дает полином ${displaystyle g (x)}$ с коэффициентами в том же поле такими, что ${displaystyle g (x)}$ разделяет ${displaystyle f (x)}$. Затем алгоритм может быть применен рекурсивно к этим и последующим делителям, пока мы не найдем разложение ${displaystyle f (x)}$ в степени неприводимых многочленов (вспоминая, что звенеть полиномов над любым полем является уникальная область факторизации ).

Все возможные факторы ${displaystyle f (x)}$ содержатся в факторное кольцо${displaystyle R = {frac {mathbb {F} _ {q} [x]} {langle f (x) angle}}}$. Если мы предположим, что ${displaystyle f (x)}$ имеет несократимые факторы ${displaystyle p_ {1} (x), p_ {2} (x), ldots, p_ {s} (x)}$, все степени d, то это факторкольцо изоморфно прямой продукт факторных колец ${displaystyle S = prod _ {i = 1} ^ {s} {frac {mathbb {F} _ {q} [x]} {langle p_ {i} (x) angle}}}$. Изоморфизм из р к S, сказать ${displaystyle phi}$, отображает многочлен ${displaystyle g (x) in R}$ к s-набор его редукций по модулю каждого из ${displaystyle p_ {i} (x)}$, т.е. если:

${displaystyle {egin {выровнено} g (x) & {} Equiv g_ {1} (x) {pmod {p_ {1} (x)}}, g (x) & {} Equiv g_ {2} (x ) {pmod {p_ {2} (x)}}, & {} vdots g (x) & {} Equiv g_ {s} (x) {pmod {p_ {s} (x)}}, end { выровнено}}}$

тогда ${displaystyle phi (g (x) + langle f (x) angle) = (g_ {1} (x) + langle p_ {1} (x) angle, ldots, g_ {s} (x) + langle p_ {s) } (x) угол)}$. На этом этапе важно отметить следующее, так как это будет иметь решающее значение позже в алгоритме: ${displaystyle p_ {i} (x)}$ неприводимы, каждое фактор-кольцо в этой прямой сумме фактически является полем. Каждая из этих областей имеет степень ${displaystyle q ^ {d}}$.

Основной результат

Основной результат, лежащий в основе алгоритма Кантора – Цассенхауза, следующий: Если ${displaystyle a (x) in R}$ является многочленом, удовлетворяющим:

${displaystyle a (x) eq 0, pm 1}$

${displaystyle a_ {i} (x) in {0, -1,1} {ext {for}} i = 1,2, ldots, s,}$

куда ${displaystyle a_ {i} (x)}$ сокращение ${displaystyle a (x)}$ по модулю ${displaystyle p_ {i} (x)}$ как и раньше, и если какие-либо два из следующих трех наборов непусты:

${displaystyle A = {imid a_ {i} (x) = 0},}$

${displaystyle B = {imid a_ {i} (x) = - 1},}$

${displaystyle C = {imid a_ {i} (x) = 1},}$

то существуют следующие нетривиальные факторы ${displaystyle f (x)}$:

${displaystyle gcd (f (x), a (x)) = prod _ {iin A} p_ {i} (x),}$

${displaystyle gcd (f (x), a (x) +1) = prod _ {iin B} p_ {i} (x),}$

${displaystyle gcd (f (x), a (x) -1) = prod _ {iin C} p_ {i} (x).}$

Алгоритм

Алгоритм Кантора – Цассенхауза вычисляет многочлены того же типа, что и ${displaystyle a (x)}$ выше, используя изоморфизм, описанный в разделе «Предпосылки». Это происходит следующим образом, если поле ${displaystyle mathbb {F} _ {q}}$ имеет нечетную характеристику (процесс может быть довольно просто обобщен на поля характеристики 2). Выберите случайный многочлен ${displaystyle b (x) in R}$ такой, что ${displaystyle b (x) eq 0, pm 1}$. Набор ${displaystyle m = (q ^ {d} -1) / 2}$ и вычислить ${displaystyle b (x) ^ {m}}$. С ${displaystyle phi}$ является изоморфизмом, мы имеем (используя наши теперь установленные обозначения):

${displaystyle phi (b (x) ^ {m}) = (b_ {1} ^ {m} (x) + langle p_ {1} (x) angle, ldots, b_ {s} ^ {m} (x) + угол p_ {s} (x) угол).}$

Теперь каждый ${displaystyle b_ {i} (x) + langle p_ {i} (x) angle}$ это элемент поля порядка ${displaystyle q ^ {d}}$, как отмечалось ранее. Мультипликативная подгруппа этого поля имеет порядок ${displaystyle q ^ {d} -1}$ и так, если только ${displaystyle b_ {i} (x) = 0}$, у нас есть ${displaystyle b_ {i} (x) ^ {q ^ {d} -1} = 1}$ для каждого я и, следовательно ${displaystyle b_ {i} (x) ^ {m} = pm 1}$ для каждого я. Если ${displaystyle b_ {i} (x) = 0}$, тогда конечно ${displaystyle b_ {i} (x) ^ {m} = 0}$. Следовательно ${displaystyle b (x) ^ {m}}$ является многочленом того же типа, что и ${displaystyle a (x)}$ над. Далее, поскольку ${displaystyle b (x) eq 0, pm 1}$, по крайней мере, два из наборов ${displaystyle A, B}$ и C непусты, и вычисляя вышеуказанные НОД, мы можем получить нетривиальные множители. Поскольку кольцо многочленов над полем является Евклидова область, мы можем вычислить эти НОД, используя Евклидов алгоритм.

Приложения

Одним из важных приложений алгоритма Кантора – Цассенхауза является вычисление дискретные логарифмы над конечными полями степенного порядка. Вычисление дискретных логарифмов - важная проблема в криптография с открытым ключом. Для поля порядка степеней простоты самый быстрый из известных методов - это индексный метод исчисления, который включает факторизацию элементов поля. Если мы представим поле порядка степени простых чисел обычным способом, то есть как полиномы над базовым полем простого порядка, приведенные по модулю неприводимого полинома соответствующей степени, то это будет просто полиномиальная факторизация, как это предусмотрено алгоритмом Кантора – Цассенхауза .

Реализация в системах компьютерной алгебры

Алгоритм Кантора – Цассенхауза реализован в PARI / GP система компьютерной алгебры как factorcantor () функция.

Смотрите также

• Полиномиальная факторизация
• Факторизация многочленов над конечными полями

Рекомендации

• Кантор, Дэвид Г.; Цассенхаус, Ганс (Апрель 1981 г.), «Новый алгоритм факторизации многочленов над конечными полями», Математика вычислений, 36 (154): 587–592, Дои:10.1090 / S0025-5718-1981-0606517-5, JSTOR  2007663, Г-Н  0606517
• http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor-zassenhaus-in-odd-characteristic/