تجزیه اعداد طبیعی

مسئله حل نشده در علوم رایانه:

آیا می‌توان مسئله‌ی تجزیه‌ی اعداد را در زمان اجرای چندجمله‌ای بر روی یک رایانه‌ی عادی حل کرد؟

(مسائل حل‌نشده بیشتر در علوم رایانه)

در نظریه اعداد به فرایند شکستن یک عدد مرکب و نوشتن آن به صورت حاصل ضرب چند عدد اول تجزیه اعداد طبیعی گفته می‌شود. هیچ الگوریتم کارآمدی برای تجزیهٔ اعداد خیلی بزرگ شناخته نشده. تلاشی که اخیراً برای تجزیه یک عدد ۲۰۰ رقمی صورت گرفته ۱۸ ماه به طول انجامید. دشواری این مسئله در برخی الگوریتم‌های رمزنگاری مانند آر‌اس‌ای می‌باشد. بسیاری از زمینه‌های ریاضیات و علوم رایانه، از جمله رایانش کوانتومی و نظریه‌ی جبری اعداد، برای بهبود روش حل این مسئله به کار گرفته شده‌اند. تجزیه همه اعداد با طول یکسان به یک اندازه مشکل نیست. مشکل‌ترین مثال‌ها (برای روش‌های فعلی) اعداد نیمه اول هستند. اعداد نیمه اول به اعدادی گفته می‌شود که می‌توان آنها را به صورت ضرب دو عدد اول نوشت. وقتی دو عدد بسیار بزرگ باشند و به‌طور تصادفی انتخاب شده باشند و مقدار نسبتاً نزدیکی داشته باشند حتی سریع‌ترین الگوریتم‌ها بروی سریع‌ترین رایانهها به قدری زمان می‌گیرند که در واقع ناکارآمد هستند.

تجزیه به عوامل اول

طبق قضیه اساسی حساب هر عدد طبیعی بزرگتر از ۱ یک تجزیه منحصربه‌فرد به اعداد اول دارد. با این وجود قضیه اساسی حساب هیچ راهی برای بدست آوردن این تجزیه در اختیار نمی‌گذارد و فقط وجود این تجزیه را تضمین می‌کند. از این رو روش‌های بسیاری برای این کار وجود دارد، یکی از این روش‌ها برای تجزیه اعداد طبیعی نسبتاً کوچک روش نمودار درختی می‌باشد. در این روش عدد به حاصل ضرب دو عدد تقسیم می‌شود و اعداد به دست آمده هم دوباره به همین ترتیب تا جایی که همهٔ اعداد به دست آمده اول باشند. به عنوان مثال عدد ۱۸۰ به این روش تجزیه می‌گردد:

• مرحله اول: ۹۰٫۲=۱۸۰
• مرحله دوم: ۴۵٫۲=۹۰
• مرحله سوم: ۱۵٫۳=۴۵
• مرحله چهارم: ۵٫۳=۱۵

بنابرین تجزیه عدد۱۸۰ به این صورت می‌باشد:

٢. ٢. ٣. ٣. ٥=١٨٠

کاربردهای عملی

سختی این مسئله در دل بسیاری از سیستم‌های رمز نگاری حس می‌شود. وجود یک الگوریتم سریع برای تجزیه اعداد طبیعی به معنی امن نبودن آر‌اس‌ای خواهد بود. بعضی سیستم‌های رمز نگاری مانند روش رمزنگاری رابین و بلام بلام شاپ اطمینان بیشتری می‌دهند. در واقع، هر روشی برای شکستن این روش‌های رمزنگاری می‌تواند برای ساخته شدن یک الگوریتم سریع تجزیه اعداد اول مورد استفاده قرار گیرد. به همان اندازه که تجزیه اعداد طبیعی سخت می‌باشد این سیستم‌های رمز نگاری قوی هستند.

مسئله لگاریتم گسسته یک مسئله سخت مشابه و با کاربردهای رمزنگاری است.

تجزیه اعداد طبیعی به غیر از رمزنگاری کاربردهای زیادی در الگوریتم‌ها دارد. برای مثال وقتی عدد طبیعی n به صورت ضرب عوامل اول باشد محاسبه سریع را ممکن می‌سازد، همچنین حافظه کمتری اشغال می‌کند زیرا می‌توان عدد را به صورت ضرب عوامل اول نوشت بدون آنکه اطلاعاتی از دست برود؛ که به‌طور مثال توسط Arecibo message استفاده شده‌است.

جدیدترین روش

همچنین ببینید: رکوردهای تجزیه اعداد طبیعی

در عمل، سخت‌ترین اعداد برای تجزیه میان اعداد b بیتی، آنهایی هستند که برابر با حاصل‌ضرب دو عدد اول با اندازه‌ی مشابه هستند. به همین دلیل، از همین اعداد در کاربردهای رمزنگاری استفاده می‌شود. در فوریه‌ ۲۰۲۰، عدد RSA-250 که یک عدد ۸۲۹ بیتی با ۲۵۰ رقم است، با محاسباتی زیاد و بهینه‌سازی‌های فراوان الگوریتم‌های تجزیه‌ی اعداد، با موفقیت مورد تجزیه قرار گرفت و این بزرگ‌ترین عدد نیمه‌اولی است که تا مه ۲۰۲۱ تجزیه شده است.

دشواری و پیچیدگی

اگر یک عدد بزرگ b بیتی نیمه اول باشد، هیچ الگوریتمی برای تجزیه آن با (O(b^k که k عددی ثابت است پیدا نشده. الگوریتم‌هایی وجود دارند که از (O((1+ε)^b به ازای εهای مثبت، سریع‌تر هستند؛ یعنی زیر-نمایی هستند. بهترین الگوریتم از نظر زمانی برای (general number field sieve (GNFS است، که برای اعداد b بیتی زمان اجرا آن به صورت زیر می‌باشد:

$O\left(\exp \left(\left({\begin{matrix}{\frac {64}{9}}\end{matrix}}b\right)^{1 \over 3}(\log b)^{2 \over 3}\right)\right).$

برای کامپیوترهای معمولی GNFS بهترین الگوریتم برای اعداد بزرگتر از ۱۰۰ رقم است. اگرچه پیتر شر در سال ۱۹۹۴ الگوریتمی پیدا کرد که از نظر زمانی چند جمله‌ای بود؛ و این بسیار مهم خواهد بود وقتی که یک رایانه‌‌ی کوانتومی بزرگ ساخته شود. الگوریتم شُر (Shor) از (O(b^۳ است و از (O(b فضا، برای یک عدد ورودی b بیتی می‌گیرد. در سال ۲۰۰۱ اولین رایانه‌ی کوانتومی ۷ کیو بیتی نخستین بار الگوریتم شُر را اجرا و عدد ۱۵ را تجزیه کرد.

الگوریتم‌های تجزیه

تک‌منظوره

زمان اجرای یک الگوریتم تک‌منظوره بستگی به فاکتورهای ناشناختهٔ آن دارد: اندازه، فرم مخصوص و غیره. اینکه دقیقاً زمان اجرای الگوریتم به چه فاکتورهایی بستگی دارد بین الگوریتم‌های مختلف فرق می‌کند. برای مثال، آزمون تقسیم برای هدف مخصوصی در نظر گرفته شده چون که زمان اجرای آن تقریباً متناسب با اندازهٔ کوچک‌ترین عامل اول آن است.

• آزمون تقسیم
• الگوریتم رو پولارد
• الگوریتم‌های فاکتورگیری گروه‌جبری؛ الگوریتم پی-۱ پولارد، الگوریتم پی+۱ ویلیامز و فاکتورگیری خم بیضوی لنسترا در این دسته قرار دارند.
• روش فاکتورگیری فرما
• روش فاکتورگیری اویلر
• غربال ویژه روی میدان اعداد

چند‌منظوره

زمان اجرای الگوریتم‌های چندمنظوره فقط به اندازهٔ عددِ طبیعیِ موردِ تجزیه بستگی دارد. این مدل از الگوریتم‌ها برای تجزیه اعداد آر‌اس‌ای استفاده می‌شود. بیشتر الگوریتم‌های تجزیه بر پایهٔ روش هم‌نهشتی مربعات هستند.

• روش فاکتورگیری دیکسون
• Continued fraction factorization (CFRAC)
• غربال مربعی
• غربال تعمیم‌یافته روی میدان اعداد
• Shanks' square forms factorization (SQUFOF)

سایر الگوریتم‌های قابل ذکر

• الگوریتم شُر، برای رایانش کوانتومی

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

• Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", Computing and Combinatorics", 2000, pp.3-22. download
• Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P.» Annals of Mathematics ۱۶۰(۲): ۷۸۱–۷۹۳ (۲۰۰۴). August 2005 version PDF
• [۱] is a public-domain integer factorization program for Windows. It claims to handle 80-digit numbers. See also the web site for this program MIRACL
• http://www.alpertron.com.ar/ECM.HTM is an integer factorization Java applet that uses the Elliptic Curve Method and the Self Initializing Quadratic Sieve.
• The RSA Challenge Numbers - a factoring challenge.
• Eric W. Weisstein, “RSA-640 Factored,” MathWorld Headline News, November 8, 2005, http://mathworld.wolfram.com/news/2005-11-08/rsa-640/
• Qsieve, a suite of programs for integer factorization. It contains several factorization methods like Elliptic Curve Method and MPQS
• Pollard p-1 method, summary of the algorithms and C source code

منابع

• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.4: Factoring into Primes, pp. 379–417.
• Richard Crandall and Carl Pomerance (2001), Prime Numbers: A Computational Perspective (به انگلیسی) (1st edition ed.), Springer {{citation}}: |edition= has extra text (help) Chapter 5: Exponential Factoring Algorithms, pp. 191–226. Chapter 6: Subexponential Factoring Algorithms, pp. 227–284. Section 7.4: Elliptic curve method, pp. 301–313.