موضوع مقاله: الگوریتم پی-۱ پولارد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم پی-۱ پولارد | مقدمه: الگوریتم p-۱ پولارد یک الگوریتم تجزیه اعداد طبیعی در نظریه اعداد است که توسط جان پولارددر سال ۱۹۷۴ ابداع شده‌است. | ## بخش 1: الگوریتم پی-۱ پولارد | این الگوریتم خاص منظوره است، بدین معنی که تنها مناسب اعداد طبیعی با انواع خاصی از عوامل است؛ این ساده‌ترین مثال از یک الگوریتم تجزیه در گروه‌های جبری است. عواملی که این الگوریتم پیدا می‌کند، عدد اولی است که عدد ما قبل آن، p-۱، یک عدد توان-صاف است؛ مشاهدهٔ ابتدایی این است که با کار در گروه ضربی به پیمانه‌ی یک عدد مرکب مانند N، در همهٔ گروه‌های ضربی عوامل اول N نیز کار خواهیم کرد. بعضی مواقع این اعداد اول برای اهداف رمزنگاری امن تفسیر می‌شوند ولی ممکن است غیر امن باشند — در توصیه‌های فعلی برای اعداد اول قوی در رمزنگاری، این شرط لازم ولی غیرکافی است که p-۱ حداقل یک عامل اول بزرگ داشته باشد. اکثر اعداد اول به اندازه کافی بزرگ قوی هستند؛ اگر مشخص شود که یک عدد اول استفاده شده در رمزنگاری غیرقوی است، به نظر می‌رسد که بیشتر از روی عمد بوده تا اینکه از تولید اعداد تصادفی باشد. از قضیهٔ کوچک فرما ، می‌دانیم که برای هر عدد صحیح مانند a که نسبت به P اول باشد و برای هر عدد طبیعی k داریم: اگر عدد x به پیمانهٔ یکی از عوامل n همنهشت با ۱ باشد، آنگاه ب.م. ایده اصلی این است که توان را عددی با تعداد بسیار زیادی عامل اول در نظر بگیریم تا یک مضرب بزرگ از p-۱ شود؛ به‌طور کلی ضرب تمام توان‌هایی از اعداد اول را در نظر می‌گیریم که این توان‌های اول از یک عدد مانند B بیشتر نباشند. با یک عدد تصادفی x شروع می‌کنیم، و مکرراً آن را با جایگزین می‌کنیم که w از همان توان‌های اعداد اول بدست می‌آید. عوامل مختلف ممکن است که برای تمام عوامل اول n مانند p-۱، p بر اعداد اول کوچک بخش پذیر باشد که در این صورت الگوریتم P-۱ پولارد دوباره n را برمی‌گرداند. | ## بخش 2: الگوریتم پی-۱ پولارد | الگوریتم و زمان اجرا الگوریتم را می‌توان به صورت زیر نوشت: ورودی : عدد مرکب n خروجی : یک عامل اول غیر بدیهی از n یا عدم موفقیت یک کران صافی مانند B انتخاب کن. M را این‌گونه تعریف کن: (نکته: محاسبهٔ صریح M احتمالاً ضروری نخواهد بود) عدد a را که نسبت به n اول است به‌طور تصادفی انتخاب کن (نکته: در واقع در این جا انتخاب تصادفی a اجباری نیست و می‌توان آن را ثابت در نظر گرفت) g را این‌گونه محاسبه کن: (g (aM − ۱، n. اگر if آنگاه یک B با مقدار بزرگتر انتخاب کن و به خط ۲ برو یا عدم موفقیت را برگردان. اگر آنگاه یک B با مقدار کوچکتر را انتخاب کن و به خط ۲ برو یا عدم موفقیت را برگردان. اگر در خط ۶، g برابر ۱ باشد، آنگاه مشخص می‌شود که تمام عوامل B, p-۱-توان-صاف نبوده‌اند. اگر در خط ۷، g = n باشد، معمولاً این نشان می‌دهد که همهٔ عوامل B-توان-صاف بوده‌اند، ولی در موارد نادر ممکن است نشانهٔ این باشد که مرتبهٔ a به پیمانهٔ n کوچک بوده‌است. زمان اجرای این الگوریتم از ( است؛ مقادیر بزرگتر B باعث کندی الگوریتم می‌شود ولی با احتمال بیشتری عامل اول را پیدا می‌کند. از آنجا که الگوریتم افزایشی است، ممکن است به اجرای خود ادامه دهد و کران به‌طور ثابت افزایش یابد. | ## بخش 3: الگوریتم پی-۱ پولارد | فرض کنید p-۱ که در آن p کوچکترین عامل اول n است را بتوان به صورت یک عدد تصادفی کوچکتر از n√ مدل کرد. ازقضیه دیکسون احتمال اینکه بزرگترین عامل اول n کمتر از p − ۱)ε) باشد تقریباً برابر ε−ε است، بنابراین به احتمال تقریباً ۱/۲۷ عدد B با مقدار n۱/۶ یک عامل اول بدست می‌دهد. در عمل وقتی عوامل همگی بزرگ باشند روش منحنی بیضوی سریع تر از روش p-۱ پولارد است؛ اجرای الگوریتم p-۱ تا B = ۱۰۶، یک چهارم عوامل ۱۲ رقمی و ۱/۲۷ عوامل ۱۸ رقمی را قبل از روش‌های دیگر پیدا خواهد کرد. نوع دیگر دو مرحله‌ای یک نوع دیگر از الگوریتم اصلی بعضی مواقع استفاده می‌شود؛ به جای اینکه نیاز باشد p-۱ همهٔ عوامل اولش از B کمتر باشد، مستلزم این است که که همهٔ عواملش به جز یک عامل از یک عدد B۱ کمتر باشند و عامل باقی‌مانده از یک عدد B۲ کمتر باشد که . بعد از اتمام مرحله اول که مانند الگوریتم اصلی است، به جای اینکه 'M را برای B۲ محاسبه کنیم و ب. فرض کنید { … ,q۱, q۲} اعداد اول متوالی در بازهٔ باشند و dn = qn − qn−۱ فاصلهٔ دو عدد اول پشت سرهم باشد. | ## جمع‌بندی | پیشنهاد می‌شود که ; بنابراین مقادیر ، ، ، … به پیمانهٔ n را می‌توان در یک جدول ذخیره کرد و را می‌توان از محاسبه کرد که این کار نیاز به توان رساندن را کم خواهد کرد.