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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

که در آن H = a می‌باشد. همچنین چک می‌کنیم که ب. م. م (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 _n را می‌توان از H _n−۱⋅H _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)