الگوریتم کانتور-زاسنهاوس

الگوریتم کانتور-زاسنهاوس در جبر محاسباتی الگوریتم کانتور-زاسنهاوس روش شناخته شده‌ای برای تجزیهٔ چند جمله‌ای‌ها به عوامل محدود است. این الگوریتم عمدتاً شامل محاسبات توانی و چند جمله‌ای ب.م.م می‌شود که توسط D.cantor و Hans Zassenhaus در سال 1981 نوآوری شد. این الگوریتم مسلماً الگوریتم برتری نسبت به راه حل قبلی (Berlekamp's algorithm) در سال 1967 است. و در حال حاضر در بسیاری از سیستم‌های جبر محاسباتی اجرا می‌شود.

بررسی اجمالی

پیش زمینه

الگوریتم کانتور-زاسنهاوس یک چند جمله‌ای با درجهٔ n با ضرایب محدود که چند جمله‌ای‌های تجزیه ناپذیر آن از درجهٔ یکسانی هستند را به عنوان ورودی می‌گیرد(f(x. و در خروجی چند جمله‌ای (g(x را می‌دهد به طوری که تابع خروجی تابع ورودی را تقسیم می‌کند. اگر فرض کنیم(f(x عوامل تجزیه ناپذیر $p_{1}(x),p_{2}(x),\ldots ,p_{s}(x)$ از درجهٔ d دارد این حلقهٔ عوامل هم ریخت محصول مستقیم حلقهٔ عامل $S=\prod _{i=1}^{s}{\frac {\mathbb {F} _{q}[x]}{\langle p_{i}(x)\rangle }}$ است. مثلاً اگر:

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

باشد، $\phi (g(x)+\langle f(x)\rangle )=(g_{1}(x)+\langle p_{1}(x)\rangle ,\ldots ,g_{s}(x)+\langle p_{s}(x)\rangle )$.

نتیجه اصلی

اگر $a(x)\in R$ یک چند جمله‌ای با شرایط زیر باشد:

$a(x)\neq 0,\pm 1$

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

که $a_{i}(x)$ کاهش یافتهٔ باقی‌مانده تقسیم $a(x)$ بر $p_{i}(x)$ باشد و هیچ‌کدام از مجموعه‌های زیر تهی نباشند:

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

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

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

عوامل غیر تهی زیر برای (f(x وجود دارند:

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

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

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

الگوریتم

الگوریتم کانتور-زاسنهاوس چند جمله‌ای‌های شبیه (a(x در قسمت بالا را با استفاده از همریختی‌های بحث شده در قسمت پیش زمینه محاسبه می‌کند: چند جمله‌ای $b(x)\in R$ را به صورت تصادفی در نظر می‌گیرد به طوری که $b(x)\neq 0,\pm 1$. همچنین مقدار $m=(q^{d}-1)/2$ را در نظر بگیر و $b(x)^{m}$ را محاسبه کن.

$\phi (b(x)^{m})=(b_{1}^{m}(x)+\langle p_{1}(x)\rangle ,\ldots ,b_{s}^{m}(x)+\langle p_{s}(x)\rangle ).$

که هر $b_{i}(x)+\langle p_{i}(x)\rangle$ عنصری از زمینه رتبهٔ $q^{d}$ است.

کاربرد ها

یکی از کاربردهای الگوریتم کانتور-زاسنهاوس در محاسبهٔ لگاریتم گسسته روی عوامل با درجهٔ اول است. محاسبهٔ لگاریتم گسسته یکی از مسایل مهم رمزنگاری کلید عمومی است.

منابع

• David G. Cantor and Hans Zassenhaus. "A New Algorithm for Factoring Polynomials Over Finite Fields". Mathematics of Computation, 36:587-592, 1981.