آیا می توان مسئله ی تجزیه ی اعداد را در زمان اجرای چندجمله ای بر روی یک رایانه ی عادی حل کرد؟
در نظریه اعداد به فرایند شکستن یک عدد مرکب و نوشتن آن به صورت حاصل ضرب چند عدد اول تجزیه اعداد طبیعی گفته می شود. هیچ الگوریتم کارآمدی برای تجزیهٔ اعداد خیلی بزرگ شناخته نشده. تلاشی که اخیراً برای تجزیه یک عدد ۲۰۰ رقمی صورت گرفته ۱۸ ماه به طول انجامید. دشواری این مسئله در برخی الگوریتم های رمزنگاری مانند آر اس ای می باشد. بسیاری از زمینه های ریاضیات و علوم رایانه، از جمله رایانش کوانتومی و نظریه ی جبری اعداد، برای بهبود روش حل این مسئله به کار گرفته شده اند. تجزیه همه اعداد با طول یکسان به یک اندازه مشکل نیست. مشکل ترین مثال ها ( برای روش های فعلی ) اعداد نیمه اول هستند. اعداد نیمه اول به اعدادی گفته می شود که می توان آنها را به صورت ضرب دو عدد اول نوشت. وقتی دو عدد بسیار بزرگ باشند و به طور تصادفی انتخاب شده باشند و مقدار نسبتاً نزدیکی داشته باشند حتی سریع ترین الگوریتم ها بروی سریع ترین رایانهها به قدری زمان می گیرند که در واقع ناکارآمد هستند.
طبق قضیه اساسی حساب هر عدد طبیعی بزرگتر از ۱ یک تجزیه منحصربه فرد به اعداد اول دارد. با این وجود قضیه اساسی حساب هیچ راهی برای بدست آوردن این تجزیه در اختیار نمی گذارد و فقط وجود این تجزیه را تضمین می کند. از این رو روش های بسیاری برای این کار وجود دارد، یکی از این روش ها برای تجزیه اعداد طبیعی نسبتاً کوچک روش نمودار درختی می باشد. در این روش عدد به حاصل ضرب دو عدد تقسیم می شود و اعداد به دست آمده هم دوباره به همین ترتیب تا جایی که همهٔ اعداد به دست آمده اول باشند. به عنوان مثال عدد ۱۸۰ به این روش تجزیه می گردد:
• مرحله اول: ۹۰٫۲=۱۸۰
• مرحله دوم: ۴۵٫۲=۹۰
• مرحله سوم: ۱۵٫۳=۴۵
• مرحله چهارم: ۵٫۳=۱۵
بنابرین تجزیه عدد۱۸۰ به این صورت می باشد:
٢. ٢. ٣. ٣. ٥=١٨٠
سختی این مسئله در دل بسیاری از سیستم های رمز نگاری حس می شود. وجود یک الگوریتم سریع برای تجزیه اعداد طبیعی به معنی امن نبودن آر اس ای خواهد بود. بعضی سیستم های رمز نگاری مانند روش رمزنگاری رابین و بلام بلام شاپ اطمینان بیشتری می دهند. در واقع، هر روشی برای شکستن این روش های رمزنگاری می تواند برای ساخته شدن یک الگوریتم سریع تجزیه اعداد اول مورد استفاده قرار گیرد. به همان اندازه که تجزیه اعداد طبیعی سخت می باشد این سیستم های رمز نگاری قوی هستند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفدر نظریه اعداد به فرایند شکستن یک عدد مرکب و نوشتن آن به صورت حاصل ضرب چند عدد اول تجزیه اعداد طبیعی گفته می شود. هیچ الگوریتم کارآمدی برای تجزیهٔ اعداد خیلی بزرگ شناخته نشده. تلاشی که اخیراً برای تجزیه یک عدد ۲۰۰ رقمی صورت گرفته ۱۸ ماه به طول انجامید. دشواری این مسئله در برخی الگوریتم های رمزنگاری مانند آر اس ای می باشد. بسیاری از زمینه های ریاضیات و علوم رایانه، از جمله رایانش کوانتومی و نظریه ی جبری اعداد، برای بهبود روش حل این مسئله به کار گرفته شده اند. تجزیه همه اعداد با طول یکسان به یک اندازه مشکل نیست. مشکل ترین مثال ها ( برای روش های فعلی ) اعداد نیمه اول هستند. اعداد نیمه اول به اعدادی گفته می شود که می توان آنها را به صورت ضرب دو عدد اول نوشت. وقتی دو عدد بسیار بزرگ باشند و به طور تصادفی انتخاب شده باشند و مقدار نسبتاً نزدیکی داشته باشند حتی سریع ترین الگوریتم ها بروی سریع ترین رایانهها به قدری زمان می گیرند که در واقع ناکارآمد هستند.
طبق قضیه اساسی حساب هر عدد طبیعی بزرگتر از ۱ یک تجزیه منحصربه فرد به اعداد اول دارد. با این وجود قضیه اساسی حساب هیچ راهی برای بدست آوردن این تجزیه در اختیار نمی گذارد و فقط وجود این تجزیه را تضمین می کند. از این رو روش های بسیاری برای این کار وجود دارد، یکی از این روش ها برای تجزیه اعداد طبیعی نسبتاً کوچک روش نمودار درختی می باشد. در این روش عدد به حاصل ضرب دو عدد تقسیم می شود و اعداد به دست آمده هم دوباره به همین ترتیب تا جایی که همهٔ اعداد به دست آمده اول باشند. به عنوان مثال عدد ۱۸۰ به این روش تجزیه می گردد:
• مرحله اول: ۹۰٫۲=۱۸۰
• مرحله دوم: ۴۵٫۲=۹۰
• مرحله سوم: ۱۵٫۳=۴۵
• مرحله چهارم: ۵٫۳=۱۵
بنابرین تجزیه عدد۱۸۰ به این صورت می باشد:
٢. ٢. ٣. ٣. ٥=١٨٠
سختی این مسئله در دل بسیاری از سیستم های رمز نگاری حس می شود. وجود یک الگوریتم سریع برای تجزیه اعداد طبیعی به معنی امن نبودن آر اس ای خواهد بود. بعضی سیستم های رمز نگاری مانند روش رمزنگاری رابین و بلام بلام شاپ اطمینان بیشتری می دهند. در واقع، هر روشی برای شکستن این روش های رمزنگاری می تواند برای ساخته شدن یک الگوریتم سریع تجزیه اعداد اول مورد استفاده قرار گیرد. به همان اندازه که تجزیه اعداد طبیعی سخت می باشد این سیستم های رمز نگاری قوی هستند.
wiki: تجزیه اعداد طبیعی