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

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

بررسی اجمالی

پیش زمینه

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

\begin{matrix} g (x) & \equiv g_{1} (x) (\mod p_{1} (x)), \\ g (x) & \equiv g_{2} (x) (\mod p_{2} (x)), \\ ⋮ \\ g (x) & \equiv g_{s} (x) (\mod p_{s} (x)), \end{matrix}

باشد، $ϕ (g (x) + ⟨ f (x) ⟩) = (g_{1} (x) + ⟨ p_{1} (x) ⟩, \dots, g_{s} (x) + ⟨ p_{s} (x) ⟩)$ .

نتیجه اصلی

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

a (x) \neq 0, \pm 1

a_{i} (x) \in {0, - 1, 1} for i = 1, 2, \dots, 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) .