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

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

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

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

مفاهیم اصلی

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

${\displaystyle a^{K(p-1)}\equiv 1{\pmod {p}}}$

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

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

عوامل مختلف

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle M'=\prod _{{\text{primes}}~p\leq B_{2}}q^{\lfloor \log _{q}{B_{2}}\rfloor }}$

'M را برای B_۲ محاسبه کنیم و ب. م. م (a^M' − ۱, n) را چک کنیم، Q را محاسبه می‌کنیم:

${\displaystyle Q=\prod _{{\text{primes}}~q\in (B_{1},B_{2}]}(H^{q}-1)}$

که در آن H = a^M می‌باشد. همچنین چک می‌کنیم که ب. م. م (Q, n) یک عامل اول غیر بدیهی تولید می‌کند یا نه. دقت کنید مانند قبل، عملیات به توان رساندن می‌تواند به پیمانهٔ n باشد.

فرض کنید { … ,q_۱, q_۲} اعداد اول متوالی در بازهٔ [B_۱, B_۲) باشند و d_n = q_n − q_n−۱ فاصلهٔ دو عدد اول پشت سرهم باشد. به‌طور معمول B_۱> ۲ و d_n اعداد زوج هستند. توزیع اعداد اول به گونه‌ای است که d_n همیشه نسبتاً کوچک خواهد بود. پیشنهاد می‌شود که d_n ≤ ln^۲ B_۲ ; بنابراین مقادیر H ^۶، H ^۴، H ^۲، … به پیمانهٔ n را می‌توان در یک جدول ذخیره کرد و H ^q_n را می‌توان از H ^q_n−۱⋅H ^d_n محاسبه کرد که این کار نیاز به توان رساندن را کم خواهد کرد.

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

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

منابع

• Pollard, J. M. (1974). "Theorems of factorization and primality testing". Proceedings of the Cambridge Philosophical Society. ۷۶ (۳): ۵۲۱–۵۲۸. doi:10.1017/S0305004100049252.
• Montgomery, P. L.; Silverman, R. D. (1990). "An FFT extension to the P − 1 factoring algorithm". Mathematics of Computation. ۵۴ (190): ۸۳۹–۸۵۴. doi:10.1090/S0025-5718-1990-1011444-3.

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

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