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

                                     

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

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

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

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

                                     

1. مفاهیم اصلی

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

a K p − 1 ≡ 1 mod p {\displaystyle a^{Kp-1}\equiv 1{\pmod {p}}}

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

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

                                     

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

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

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

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

  • M را این‌گونه تعریف کن: M = ∏ primes q ≤ B q ⌊ log q ⁡ B ⌋ {\displaystyle M=\prod _ نکته: محاسبهٔ صریح M احتمالاً ضروری نخواهد بود
  • g را این‌گونه محاسبه کن: g = a M − ۱، n. نکته: می‌توان به پیمانهٔ n به توان رساند
  • اگر 1 < n > g آنگاه g را برگردان.
  • اگر if g = ۱ آنگاه یک B با مقدار بزرگتر انتخاب کن و به خط ۲ برو یا عدم موفقیت را برگردان.
  • اگر g = n آنگاه یک B با مقدار کوچکتر را انتخاب کن و به خط ۲ برو یا عدم موفقیت را برگردان.
  • عدد a را که نسبت به n اول است به‌طور تصادفی انتخاب کن نکته: در واقع در این جا انتخاب تصادفی a اجباری نیست و می‌توان آن را ثابت در نظر گرفت
  • یک کران صافی مانند B انتخاب کن.

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

                                     

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

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

                                     

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

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

M ′ = ∏ primes p ≤ B 2 q ⌊ log q ⁡ B 2 ⌋ {\displaystyle M=\prod _~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 محاسبه کرد که این کار نیاز به توان رساندن را کم خواهد کرد.



                                     

5. منابع

  • 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.
  • Pollard, J. M. 1974. "Theorems of factorization and primality testing". Proceedings of the Cambridge Philosophical Society. ۷۶ ۳: ۵۲۱–۵۲۸. doi:10.1017/S0305004100049252.