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

الگوریتم کانتور-زاسنهاوس
در جبر محاسباتی الگوریتم کانتور-زاسنهاوس روش شناخته شده‌ای برای تجزیهٔ چند جمله‌ای‌ها به عوامل محدود است.
این الگوریتم عمدتاً شامل محاسبات توانی و چند جمله‌ای ب.م.م می‌شود که توسط D.cantor و Hans Zassenhaus در سال 1981 نوآوری شد.
این الگوریتم مسلماً الگوریتم برتری نسبت به راه حل قبلی (Berlekamp's algorithm) در سال 1967 است. و در حال حاضر در بسیاری از سیستم‌های جبر محاسباتی اجرا می‌شود.
 بررسی اجمالی 
 پیش زمینه 
الگوریتم کانتور-زاسنهاوس یک چند جمله‌ای با درجهٔ n با ضرایب محدود که چند جمله‌ای‌های تجزیه ناپذیر آن از درجهٔ یکسانی هستند را به عنوان ورودی می‌گیرد(f(x. و در خروجی چند جمله‌ای (g(x را می‌دهد به طوری که تابع خروجی تابع ورودی
را تقسیم می‌کند.
اگر فرض کنیم(f(x عوامل تجزیه ناپذیر  از درجهٔ d دارد این حلقهٔ عوامل هم ریخت محصول مستقیم حلقهٔ عامل  است. مثلاً اگر:


باشد، .
 نتیجه اصلی 
اگر  یک چند جمله‌ای با شرایط زیر باشد:



که  کاهش یافتهٔ باقی‌مانده تقسیم  بر  باشد و هیچ‌کدام از مجموعه‌های زیر تهی نباشند:





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





 الگوریتم 
الگوریتم کانتور-زاسنهاوس چند جمله‌ای‌های شبیه (a(x در قسمت بالا را با استفاده از همریختی‌های بحث شده در قسمت پیش زمینه محاسبه می‌کند:
چند جمله‌ای  را به صورت تصادفی در نظر می‌گیرد به طوری که .
همچنین مقدار  را در نظر بگیر و  را محاسبه کن.

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

 منابع 

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

رده:الگوریتم‌ها
رده:جبر رایانه‌ای
رده:میدان‌های متناهی