الگوریتم های نظریه اعداد + ویدئو?

نظریه اعداد شاخه‌ای از ریاضیات محض است که خود را عمدتاً وقف مطالعه اعداد صحیح نموده‌است. در خصوص اهمیت این مبحث گفته میشود که «ریاضیات ملکه علوم است، و نظریه اعداد ملکه ریاضیات.»

از کاربردهای نظریه اعداد در علوم کامپیوتر میتوان به موارد زیر اشاره کرد:

الگوریتم اقلیدس برای یافتن بزرگترین مقسوم علیه مشترک، الگوریتم تشخیص اعداد اول، الگوریتم حل معادلات همنهشتی، الگوریتم به توان رسانی پیمانه ای و ... . کاربرد اکثر این موارد در رمزنگاری پیام ها می‌باشد.

الگوریتم اقلیدس

این الگوریتم به منظور یافتن ب.م.م دو عدد می‌باشد.

با توجه به قضیه فوق، gcd(a,b) را به صورت بازگشتی صدا می‌کنیم تا زمانی که b=0 شود و در نهایت a را برمیگردانیم.

زمان اجرای الگوریتم اقلیدس

زمان اجرا را با توجه به اندازه ی a و b بررسی می‌کنیم.

ابتدا فرض می‌کنیم که a > b >= 0

اگر b > a >= 0 باشد، به واسطه فراخوانی EUCLID ( a , b ) جای a و b تغییر می‌کندو جا به جا می‌شوند و در مرحله بعد EUCLID ( b , a ) فراخوانی می‌شود.

اگر a = b > 0 با یک فراخوانی کار تمام می‌شود، زیرا ب.م.م همان a = b است.

زمان اجرای کلی متناسب با تعداد فراخوانی ها است.

برای یافتن تعداد دفعات فراخوانی تابع از اعداد فیبوناچی استفاده می‎کنیم. به این منظور گزاره‌هایی که در ادامه بیان می‌شود آن ها را اثبات شده در نظر میگیریم.

گزاره

قضیه

قضیه فوق نیز از گزاره ی فوق، به صورت مستقیم نتیجه می‌شود. با استفاده از این قضیه پیچیدگی زمانی را مشخص می‌کنیم.

قضیه

الگوریتم توسعه یافته اقلیدس

علاوه بر محاسبه ب.م.م ، ضرائب ترکیب خطی دو عدد ورودی را که حاصلش ب.م.م می‌شود به عنوان خروجی به ما می‌دهد.

gcd( a,b ) = d = ax + by

از الگوریتم توسعه یافته اقلیدس در حل معادلات همنهشتی استفاده می‌شود. پیچیدگی زمانی الگوریتم توسعه یافته اقلیدس مانند الگوریتم اقلیدس می‌باشد و تفاوتی ندارد. پس زمان اجرای آن از مرتبه O(lg(b)) می‌باشد.

توان رسانی پیمانه ای

عمل توان‌رسانی پیمانه‌ای باقی‌مانده را در حالتی که عدد صحیح a به توان b برسد حساب می‌کند. اگر بخواهیم آن را با نمادگذاری نشان دهیم به شکل زیر خواهد بود:

الگوریتم

متغیر c لازم نیست اما به دو دلیل آن را فقط نشان می‌دهیم:

این متغیر مانند اندیس برای نمایش دودویی b استفاده می‌شود.
d = a^c mod n

رمزنگاری RSA

هرنفر یک کلید عمومی و یک کلید مخفی دارد. هر کلید تکه از اطلاعات است؛ هر نفر کلیدهای عمومی و مخفی خود را ایجاد می کند. کلیدهای مخفی پنهان می‌مانند، اما کلیدهای عمومی را می‌توان برای هر کسی فاش کرد و یا منتشر کرد.