الگوریتم پی-۱ پولارد

الگوریتم p-۱ پولارد یک الگوریتم تجزیه اعداد طبیعی در نظریه اعداد است که توسط جان پولارددر سال ۱۹۷۴ ابداع شده‌است. این الگوریتم خاص منظوره است، بدین معنی که تنها مناسب اعداد طبیعی با انواع خاصی از عوامل است؛ این ساده‌ترین مثال از یک الگوریتم تجزیه در گروه‌های جبری است.

عواملی که این الگوریتم پیدا می‌کند، عدد اولی است که عدد ما قبل آن، p-۱، یک عدد توان-صاف الگو:به انگلیسی است؛ مشاهدهٔ ابتدایی این است که با کار در گروه ضربی به پیمانه‌ی یک عدد مرکب مانند N، در همهٔ گروه‌های ضربی عوامل اول N نیز کار خواهیم کرد.

موجودیت این الگوریتم ما را به سمت مفهوم اعداد اول امن الگو:به انگلیسی سوق می‌دهد که اعداد اولی هستند مانند p که p-۱ دو برابر یک عدد اول Sophie Germain مانند q است، بنابراین به صورت حداقلی عددی صاف است. بعضی مواقع این اعداد اول برای اهداف رمزنگاری امن تفسیر می‌شوند ولی ممکن است غیر امن باشند — در توصیه‌های فعلی برای اعداد اول قوی الگو:به انگلیسی در رمزنگاری، این شرط لازم ولی غیرکافی است که p-۱ حداقل یک عامل اول بزرگ داشته باشد. اکثر اعداد اول به اندازه کافی بزرگ قوی هستند؛ اگر مشخص شود که یک عدد اول استفاده شده در رمزنگاری غیرقوی است، به نظر می‌رسد که بیشتر از روی عمد بوده تا اینکه از تولید اعداد تصادفی باشد. این کلمات فنی در صنعت رمزنگاری کهنه محسوب می‌شوند.[۱]

مفاهیم اصلی

فرض کنید n یک عدد مرکب و p یکی از عوامل اول آن باشد. از قضیهٔ کوچک فرما الگو:به انگلیسی، می‌دانیم که برای هر عدد صحیح مانند a که نسبت به P اول باشد و برای هر عدد طبیعی k داریم:

$a^{K(p-1)}\equiv 1(\mathrm{mod}p)$

اگر عدد x به پیمانهٔ یکی از عوامل n همنهشت با ۱ باشد، آنگاه ب.م. م (x-1,n) بر آن عامل بخش‌پذیر است.

ایده اصلی این است که توان را عددی با تعداد بسیار زیادی عامل اول در نظر بگیریم تا یک مضرب بزرگ از p-۱ شود؛ به‌طور کلی ضرب تمام توان‌هایی از اعداد اول را در نظر می‌گیریم که این توان‌های اول از یک عدد مانند B بیشتر نباشند. با یک عدد تصادفی x شروع می‌کنیم، و مکرراً آن را با $x^{w}modn$ جایگزین می‌کنیم که w از همان توان‌های اعداد اول بدست می‌آید. در هر مرحله یا اگر ترجیح می‌دهید در مرحلهٔ آخر چک می‌کنیم که آیا ب. م. م (x-1,n) مخالف ۱ است یا نه.

عوامل مختلف

ممکن است که برای تمام عوامل اول n مانند p-۱، p بر اعداد اول کوچک بخش پذیر باشد که در این صورت الگوریتم P-۱ پولارد دوباره n را برمی‌گرداند.

الگوریتم و زمان اجرا

الگوریتم را می‌توان به صورت زیر نوشت:

ورودی : عدد مرکب n

خروجی : یک عامل اول غیر بدیهی از n یا عدم موفقیت

1. یک کران صافی مانند B انتخاب کن.
2. M را این‌گونه تعریف کن: $M=\prod _{\text{primes}q\le B}{q}^{\lfloor {\log }_{q}B\rfloor }$ (نکته: محاسبهٔ صریح M احتمالاً ضروری نخواهد بود)
3. عدد a را که نسبت به n اول است به‌طور تصادفی انتخاب کن (نکته: در واقع در این جا انتخاب تصادفی a اجباری نیست و می‌توان آن را ثابت در نظر گرفت)
4. g را این‌گونه محاسبه کن: (g = (a^M − ۱، n. (نکته: می‌توان به پیمانهٔ n به توان رساند)
5. اگر الگو:Nowrap آنگاه g را برگردان.
6. اگر if الگو:Nowrap آنگاه یک B با مقدار بزرگتر انتخاب کن و به خط ۲ برو یا عدم موفقیت را برگردان.
7. اگر الگو:Nowrap آنگاه یک B با مقدار کوچکتر را انتخاب کن و به خط ۲ برو یا عدم موفقیت را برگردان.

اگر در خط ۶، g برابر ۱ باشد، آنگاه مشخص می‌شود که تمام عوامل B, p-۱-توان-صاف نبوده‌اند. اگر در خط ۷، g = n باشد، معمولاً این نشان می‌دهد که همهٔ عوامل B-توان-صاف بوده‌اند، ولی در موارد نادر ممکن است نشانهٔ این باشد که مرتبهٔ a به پیمانهٔ n کوچک بوده‌است. زمان اجرای این الگوریتم از (الگو:Nowrap است؛ مقادیر بزرگتر B باعث کندی الگوریتم می‌شود ولی با احتمال بیشتری عامل اول را پیدا می‌کند.

چگونه B را انتخاب کنیم؟

از آنجا که الگوریتم افزایشی است، ممکن است به اجرای خود ادامه دهد و کران به‌طور ثابت افزایش یابد. فرض کنید p-۱ که در آن p کوچکترین عامل اول n است را بتوان به صورت یک عدد تصادفی کوچکتر از n√ مدل کرد. ازقضیه دیکسون الگو:به انگلیسی احتمال اینکه بزرگترین عامل اول n کمتر از p − ۱)^ε) باشد تقریباً برابر ε^−ε است، بنابراین به احتمال تقریباً ۱/۲۷ عدد B با مقدار n^۱/۶ یک عامل اول بدست می‌دهد. در عمل وقتی عوامل همگی بزرگ باشند روش منحنی بیضوی سریع تر از روش p-۱ پولارد است؛ اجرای الگوریتم p-۱ تا B = ۱۰^۶، یک چهارم عوامل ۱۲ رقمی و ۱/۲۷ عوامل ۱۸ رقمی را قبل از روش‌های دیگر پیدا خواهد کرد.

نوع دیگر دو مرحله‌ای

یک نوع دیگر از الگوریتم اصلی بعضی مواقع استفاده می‌شود؛ به جای اینکه نیاز باشد p-۱ همهٔ عوامل اولش از B کمتر باشد، مستلزم این است که که همهٔ عواملش به جز یک عامل از یک عدد B_۱ کمتر باشند و عامل باقی‌مانده از یک عدد B_۲ کمتر باشد که الگو:Nowrap. بعد از اتمام مرحله اول که مانند الگوریتم اصلی است، به جای اینکه

$M^{\prime }=\prod _{\text{primes}p\le B_2}{q}^{\lfloor {\log }_q{B}_2\rfloor }$

'M را برای B_۲ محاسبه کنیم و ب. م. م الگو:Nowrap را چک کنیم، Q را محاسبه می‌کنیم:

$Q=\prod _{\text{primes}q\in (B_1,B_2]}(H^q-1)$

که در آن الگو:Nowrap می‌باشد. همچنین چک می‌کنیم که ب. م. م (Q, n) یک عامل اول غیر بدیهی تولید می‌کند یا نه. دقت کنید مانند قبل، عملیات به توان رساندن می‌تواند به پیمانهٔ n باشد.

فرض کنید { … ,q_۱, q_۲} اعداد اول متوالی در بازهٔ الگو:Nowrap باشند و d_n = q_n − q_n−۱ فاصلهٔ دو عدد اول پشت سرهم باشد. به‌طور معمول الگو:Nowrap و الگو:Nowrap اعداد زوج هستند. توزیع اعداد اول به گونه‌ای است که d_n همیشه نسبتاً کوچک خواهد بود. پیشنهاد می‌شود که الگو:Nowrap ; بنابراین مقادیر الگو:Nowrap، الگو:Nowrap، الگو:Nowrap، … به پیمانهٔ n را می‌توان در یک جدول ذخیره کرد و الگو:Nowrap را می‌توان از الگو:Nowrap محاسبه کرد که این کار نیاز به توان رساندن را کم خواهد کرد.

جستارهای وابسته

• الگوریتم p+۱ ویلیام

منابع

• الگو:Cite journal
• الگو:Cite journal

پیوند به بیرون

• روش p-۱ پولارد
• الگوریتم p-۱ پولارد(Source code)