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