نظریه اعداد را می توان شاخه ای از ریاضیات است که با خواص
اعداد صحیح سروکار دارد. الگوریتم های نظریه اعداد ممکن است بزرگترین مقسوم علیه
مشترک دو عدد صحیح را پیدا کند.
یک کاربرد مهم الگوریتم نظر به اعداد، رمز نگاری
است که پیامی را رمز گذاری می کند و از مبدا مقصد می فرستد، به طوری که دیگران نمی
توانند آن پیام را درک کنند.
الگوریتم اقلیدس چیست؟
روش ساده ای را برای
تعیین بزرگ ترین مقسوم علیه مشترک دو عدد صحیح را ارائه می کند.یعنی،
برای یافتن) gcd(n.m به طور بازگشتی، تساوی موجود در این قضیه را اعمال می کنیم تا
m= 0 شود و سپس n را بر می گردانیم. این روش ، الگوریتم اقلیدس نام دارد زیرا توسط
اقلیدس طراحی شده است.
یافتن اعداد اول بزرگ چگونه است؟
یافتن اعداد
اول بزرگ، برای موفقیت در رمز گذاری کلید عمومی RSA ضروری است. پس از اینکه در مورد
جست و جو برای اعداد اول بزرگ، الگوریتمی را ارائه می دهیم که مشخص می کند عددی اول
است که یا خیر.
جست و جو برای عدد اول بزررگ چگونه است؟
برای یافتن عدد
اول بزرگ ، به طور تصادفی اعداد صحیح با اندازه مناسب را انتخاب می کنیم و تست می
کنیم که آیا اول است یا خیر. یکی از ملاحظات مهم در این روش، احتمال یافتن عدد اول
در انتخاب تصادفی است. با اسفاده از قضیه توزیع عدد اول که در ادامه می آید،
می توانیم این احتمال را برآوورد کنیم.