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

الگوریتم کانتور-زاسنهاوس در جبر محاسباتی الگوریتم کانتور-زاسنهاوس روش شناخته شده‌ای برای تجزیه ی چند جمله‌ای‌ها به عوامل محدود است. این الگوریتم عمدتاً شامل محاسبات توانی و چند جمله‌ای ب.م.م می‌شود که توسط 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{align} 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{align}$

باشد، $\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^m_s(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.