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

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

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

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

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

Обзор

Фон

Алгоритм Кантора–Цассенхауза принимает в качестве входных данных бесквадратный многочлен (т. е. многочлен без повторяющихся множителей) степени n с коэффициентами в конечном поле, все неприводимые многочленные множители которого имеют одинаковую степень (существуют алгоритмы для эффективного разложения произвольных многочленов на произведение многочленов, удовлетворяющих этим условиям, например, является бесквадратным многочленом с теми же множителями, что и , так что алгоритм Кантора–Цассенхауза может использоваться для разложения произвольных многочленов). Он дает в качестве выходных данных многочлен с коэффициентами в том же поле, такой что делит . Затем алгоритм можно применять рекурсивно к этим и последующим делителям, пока мы не найдем разложение на степени неприводимых многочленов (напоминая, что кольцо многочленов над любым полем является уникальной областью факторизации ). ${\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)}$

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

${\displaystyle {\begin{aligned}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{aligned}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм

Алгоритм Кантора–Цассенхауза вычисляет многочлены того же типа, что и выше, используя изоморфизм, обсуждаемый в разделе «Предыстория». Он действует следующим образом в случае, когда поле имеет нечетную характеристику (процесс может быть обобщен на поля характеристики 2 довольно простым способом. ^[2] Выберите случайный многочлен , такой что . Установите и вычислите . Поскольку является изоморфизмом, мы имеем (используя нашу теперь установленную нотацию): ${\displaystyle a(x)}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle b(x)\in R}$ ${\displaystyle b(x)\neq 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)\rangle ,\ldots ,b_{s}^{m}(x)+\langle p_{s}(x)\rangle ).}$

Теперь, каждый является элементом поля порядка , как было отмечено ранее. Мультипликативная подгруппа этого поля имеет порядок и поэтому, если только , мы имеем для каждого i и, следовательно, для каждого i . Если , то, конечно , . Следовательно, является многочленом того же типа, что и выше. Далее, поскольку , по крайней мере два из множеств и C непусты и вычисляя вышеуказанные НОД, мы можем получить нетривиальные множители. Поскольку кольцо многочленов над полем является евклидовой областью , мы можем вычислить эти НОД, используя алгоритм Евклида . ${\displaystyle b_{i}(x)+\langle p_{i}(x)\rangle }$ ${\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)\neq 0,\pm 1}$ ${\displaystyle A,B}$

Приложения

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

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

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

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

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

Ссылки

1. Кантор, Дэвид Г.; Цассенхаус , Ганс (апрель 1981 г.), «Новый алгоритм факторизации многочленов над конечными полями», Математика вычислений , 36 (154): 587–592, doi : 10.1090/S0025-5718-1981-0606517-5 , JSTOR  2007663, MR  0606517
2. Элиа, Микеле; Скипани, Давиде (2015), «Улучшения в алгоритме факторизации Кантора–Цассенхауза», Mathematica Bohemica , 140 (3), Институт математики, Чешская академия наук: 271–290, arXiv : 1012.5322 , doi : 10.21136/mb.2015.144395

Внешние ссылки

• https://web.archive.org/web/20200301213349/http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor- zassenhaus-в-нечетной характеристике/