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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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