بیگ بنگ: تیمی از ریاضیدانان دانشگاه نیو ساوت ولز در استرالیا و دانشگاه پلی تکنیک اکول در فرانسه، معمای ریاضیاتی که چندین دهه حلنشده باقی مانده بود را حل کردند که باعث میشود ضرب اعداد بزرگ در زمان ِ بسیار سریعتری انجام شود.

به گزارش بیگ بنگ، دکتر دیوید هاروی از دانشکده ریاضی و آمار دانشگاه نیو ساوت ولز، بیان داشت: «به لحاظ فنی، ما حدسی که در سال ۱۹۷۱ توسط شونهاگ و استراسن در مورد پیچیدگی ضرب عدد صحیح مطرح شده بود را اثبات کردیم. آنها پیشبینی کرده بودند که باید الگوریتمی وجود داشته باشد که اعدادِ n رقمی را با استفاده از عملیات اصلیِ n* log(n) ضرب کند.»
وی افزود: «مقالۀ ما اولین مثال از الگوریتمی را ارائه میدهد که به این حدس دست یافته است. به بیان دیگر، اگر بخواهیم اعداد ۳۱۴ و ۱۵۹ را با روش ابتدایی مدرسهای ضرب کنیم، باید حاصلضربهای ۹ رقمی را محاسبه کنیم. به طور کلی اگر n بیانگر تعداد رقمها در هر عدد باشد، میتوان در عملیات n۲ به پاسخ دست یافت.» شونهاگ و استراسن خودشان الگوریتمی را ابداع کردند که به عملیاتی کمتر از n۲ نیاز داشت اما نتوانستند به الگوریتم n* log(n) برسند.
دکتر هاروی افزود: «الگوریتم شونهاگ- استراسن بسیار سریع است: کامپیوتری که از روش ابتدایی مدرسهای استفاده میکند ماهها طول میکشد تا دو عدد یک میلیارد رقمی را ضرب کند، اما کامپیوتری که از روش شونهاگ- استراسن استفاده میکند در کمتر از ۳۰ ثانیه این ضرب را انجام میدهد.»
اما برای اعدادی که رقمهای کافی دارند- میلیارد، تریلیون یا حتی بیشتر- الگوریتم جدیدی که توسط دکتر هاروی و دکتر جوریس ون در هوون از دانشگاه پلی تکنیک اکول ارائه شده، میتواند حتی بهتر از الگوریتم شونهاگ و استراسن عمل کند. شونهاگ و استراسن همچنین پیشبینی کردند که n* log(n) بهترین نتیجۀ ممکن است- و هیچکس دیگری هرگز الگویی سریعتر از این برای ضرب پیدا نخواهد کرد.
دکتر هاروی گفت: «بنابراین انتظار میرود که کار ما انتهای راه برای این مسئله باشد، اگر چه هنوز نمیدانیم که چطور این را ثابت کنیم.» گرچه هنوز روزهای اول است اما این پیشرفت، پیامدهای بیشماری خواهد داشت. این بدان معنی است که میتوانیم هر نوع محاسباتی مثل تقسیم و جذر را به طور مؤثرتری انجام دهیم. همچنین میتوانیم رقمهای pi را بهتر از قبل حساب کنیم. این الگوریتم حتی در مسائلی که دارای اعداد اول بزرگ هستند نیز کاربرد دارد.» مقاله این تیم در آرشیو چندرسانهایِ HAL با دسترسی آزاد، منتشر شده است.
ترجمه: زهرا جهانبانی/ سایت علمی بیگ بنگ
منبع: sci-news.com
سپاس یه خاطر این مطلب خوب
تهدیدی جدی برای رمزنگاری RSA
ببخشید دقیقا کجاش تهدیدی برای رمزنگاری RSA است؟؟؟
خوبی الگوریتم RSA این نیست که اعداد بزرگن. خوبیش اینه فضای حالت بزرگه و نمیشه کلید خصوصی رو پیدا کرد.
گفته می شود NSA (امنیت ملی امریکا) پایگاه داده عظیمی از اعداد اول دارد الگوریتم فوق سرعت گسترش این پایگاه داده را افزایش می دهد
کی گفته؟؟ لینک معتبر بفرستید ما داریم علمی حرف میزنیم.
یاد اون جوک افتادم میگه روسیه موشکی ساخته امریکام خبر نداره..بعد طرف میگه خوب شما از کجا خبر دارین……
دقیقا