سلام!
این متنی که گذاشتم قسمتی از این مطلب در ویکی پدیا هست: تجزیه اعداد طبیعی
تجزیه اعداد طبیعی
همچنین ببینید: رکوردهای تجزیه اعداد طبیعی یک تیم در اژانس فدرال امنیت تکنولوژی اطلاعات آلمان (BSI) رکوردی برای تجزیه اعداد نیمه اول که توسط RSA Factoring Challenge پیشنهاد شد بود ثبت کردند. این تیم در تاریخ ۹ می۲۰۰۵ تجزیه RSA-200 (عدد ۶۶۳ بیتی یا ۲۰۰ رقمی در مبنای ۱۰)با استفاده از general number field sieve اعلام کرد. کمی بعد در تاریخ ۴ نوامبر ۲۰۰۵ این تیم تجزیه RSA-640 که عددی کوچکتربا ۱۹۳ رقم در مبنای ۱۰ (۶۴۰ بیت) بود را اعلام کرد. هر دوی این تجزیه‌ها با استفاده ۸۰ عدد سی پی یو AMD Opteron ماه‌های زیادی طول کشید.
دشواری و پیچیدگی
اگر یک عدد بزرگ b بیتی نیمه اول باشدهیچ الگوریتمی برای تجزیه آن با (O(bk که k عددی ثابت است پیدا نشده. الگوریتم‌هایی وجود دارند که از (O((1+ε)b به ازای εهای مثبت، سریع تر هستند. یعنی sub-exponential هستند. بهترین الگوریتم از نظر زمانی برای (general number field sieve (GNFS است، که برای اعداد b بیتی زمان اجرا آن به صورت زیر می‌باشد:
برای کامپیوترهای معمولی GNFS بهترین الگوریتم برای اعداد بزرگتر از ۱۰۰ رقم می‌باشد. اگرچه Peter Shor در سال ۱۹۹۴ الگوریتمی پیدا کرد که از نظر زمانی چند جمله‌ای بود. و این بسیار مهم خواهد بود وقتی که یک کامپیوتر کوانتومی بزرگ ساخته شود. الگوریتم Shor از (O(b۳ است و از (O(b فضا، برای یک عدد ورودی b بیتی می‌گیرد. در سال ۲۰۰۱ اولین کامپیوتر کوانتومی ۷ کیو بیتی نخستین بار الگوریتم Shor را اجرا نمود و عدد ۱۵ را تجزیه کرد.
ویرایش: همون طور که دوست خوبمون BlueBlade گفتن، تجزیه کردن با تشخیص اول بودن تفاوت داره... که من موقع پاسخ دادن به این موضوع دقت کافی نداشتم... البته ارتباط این ۲ موضوع هم قابل بحث هست و جالبه...
روش های مختلفی برای تست اول بودن یه عدد هست... بعضی روش ها خیلی جالب هستن... مثلا یه روش احتمالی به این صورت هست:
فرض کنیم عدد صحیح n داده شده، عدد صحیح a ای را انتخاب کنید که نسبت به عدد n اول باشد، باقی مانده ی a به توان n-1 را بر n حساب کنید، اگر نتیجه غیر از ۱ بود یعنی عدد n مرکب است، در غیر این صورت ممکن است اول باشد یا نباشد! که بهش می گیم "شبه اول" در مبنای a.
من برای مثال عدد n رو ۱۴ و a رو ۳ انتخاب کردم، و اتفاقا همین اول مشخص شد که ۱۴ مرکبه! چون ۳ به توان ۱۳ می شه ۱۵۹۴۳۲۳ و باقی مانده ی این عدد بر ۱۴ می شه ۳. پس ۱۴ مرکبه.
این مطلب رو هم در ویکی پدیا بخونید:
Primality test
ویرایش ۲:
یادم رفت که اشاره کنم برای محاسبه ی هم نهشتی نمایی روش های بهتری هست تا محاسبه ی مستقیم اون عبارت بزرگ! این مقاله رو بخونید: Modular exponential
ویرایش ۳:
و بالاخره تا الان در عمل سریع ترین الگوریتم شناخته شده ی همه منظوره (نه فقط برای حالت خاص) برای این کار: ECPP
Eliptic curve primality
یادمه Eliptic curve برای رمز گذاری ارتباطات در شبکه هم استفاده می شد... مثل الگوریتم RSA...