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

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

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

طبق قضیه اساسی حساب هر عدد طبیعی بزرگتر از ۱ یک تجزیه منحصر به فرد به اعداد اول دارد. با این وجود قضیه اساسی حساب هیچ راهی برای بدست آوردن این تجزیه در اختیار نمی‌گذارد و فقط وجود این تجزیه را تضمین می‌کند.

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

سختی این مسئله در دل بسیاری از سیستم‌های رمز نگاری حس می‌شود. وجود یک الگوریتم سریع برای تجزیه اعداد طبیعی به معنی امن نبودن RSA خواهد بود. بعضی سیستم‌های رمز نگاری مانند Rabin public-key algorithm و The Blum Blum Shub pseudo-random generator و اطمینان بیشتری می‌دهند - هر روشی برای شکستن این رمز نگاری‌ها می‌تواند برای ساخته شدن یک الگوریتم تجزیه اعداد اول سریع مورد استفاده قرار گیرد. به همان اندازه که تجزیه اعداد طبیعی سخت می‌باشد این سیستم‌های رمز نگاری قوی هستند.

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

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

جدیدترین روش

همچنین ببینید: رکوردهای تجزیه اعداد طبیعی یک تیم در اژانس فدرال امنیت تکنولوژی اطلاعات آلمان (BSI) رکوردی برای تجزیه اعداد نیمه اول که توسط RSA Factoring Challenge پیشنهاد شد بود ثبت کردند. این تیم در تاریخ ۹ می‌۲۰۰۵ تجزیه RSA-200 (عدد ۶۶۳ بیتی یا ۲۰۰ رقمی در مبنای ۱۰)با استفاده از general number field sieve اعلام کرد. کمی بعد در تاریخ ۴ نوامبر ۲۰۰۵ این تیم تجزیه RSA-640 که عددی کوچکتربا ۱۹۳ رقم در مبنای ۱۰ (۶۴۰ بیت) بود را اعلام کرد. هر دوی این تجزیه‌ها با استفاده ۸۰ عدد سی پی یو AMD Opteron ماه‌های زیادی طول کشید.

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

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

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

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

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

تک منظوره

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

• Trial division
• Pollard's rho algorithm
• Algebraic-group factorisation algorithms amongst which are Pollard's p − 1 algorithm, Williams' p+1 algorithm and Lenstra elliptic curve factorization
• Fermat's factorization method
• Euler's factorization method
• Special number field sieveSpecial number field sieve

چند منظوره

زمان اجرای الگوریتم‌های چند منظوره فقط به‌اندازهٔ عدد طبیعی که می‌خواهند تجزیه کنند بستگی دارد. این مدل از الگوریتمها برای تجزیه اعداد RSA استفاده می‌شود. بیشتر الگوریتم‌های تجزیه بر پایهٔ روش congruence of squarescongruence of squares هستند.

• Dixon's algorithm
• Continued fraction factorization (CFRAC)
• Quadratic sieve
• General number field sieve
• Shanks' square forms factorization (SQUFOF)

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

• Shor's algorithm, for quantum computers

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

• Richard P. Brent, «Recent Progress and Prospects for Integer Factorisation Algorithms», Computing and Combinatorics", ۲۰۰۰, pp.۳-۲۲. download
• Manindra Agrawal, Neeraj Kayal, Nitin Saxena, «PRIMES is in P.» Annals of Mathematics ۱۶۰(۲): ۷۸۱-۷۹۳ (۲۰۰۴). August ۲۰۰۵ version PDF
• [۱] is a public-domain integer factorization program for Windows. It claims to handle ۸۰-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-۶۴۰ Factored,” MathWorld Headline News, November ۸, ۲۰۰۵, 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. Prime Numbers: A Computational Perspective. 1st edition ed. Springer, 2001. ISBN 0-387-94777-9.  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.