تابع فی اویلر
در نظریه اعداد تابع فی اویلر یا
تابع فی اویلر نقش کلیدی در تعریف سیستم رمزنگاری RSA دارد.
تاریخچه و نمادگذاری
لئونارد اولر این تابع را در سال ۱۷۶۳ معرفی کرد. در آن زمان او هنوز نماد خاصی برای این تابع تعیین نکرده بود. بعدها لئونارد اویلر با مطالعه بیشتر تابع فی، حرف یونانی π را برای آن برگزید. نماد استاندارد φ بعدها توسط گاوس استفاده شدهاست.
محاسبه مقدار تابع فی
چندین راه برای محاسبه این فرمول وجود دارد.
فرمول ضرب اویلر
این تابع بیان میکند که
که در آن
تبدیل فوریه
مقدار تابع فی برابر است با مقدار تبدیل فوریه گسسته ب.م.م در ۱ یعنی:
مقدار حقیقی این فرمول برابر است با:
توجه کنید که برخلاف دو فرمول دیگر در این فرمول نیازی به دانستن عوامل اول n نیست. اما چون فرمول شامل محاسبه ب.م.م n و همه اعداد مثبت کمتر از n است در نهایت به تجزیه n نیاز خواهیم داشت.
جمع مقسوم علیهها
فرمول کلاسیک اویلر
این فرمول به روشهای مختلف قابل اثبات است.
تابع زتای ریمان
برای n>1 میتوان تابع فی را به عنوان یک حد تابع زتای ریمان محاسبه کرد
که در این فرمول
چند مقدار تابع
۹۹ مقدار اولیه این تابع در جدول و نمودار زیر قابل مشاهده است.
+۰ | +۱ | +۲ | +۳ | +۴ | +۵ | +۶ | +۷ | +۸ | +۹ | |
---|---|---|---|---|---|---|---|---|---|---|
۰+ | ۱ | ۱ | ۲ | ۲ | ۴ | ۲ | ۶ | ۴ | ۶ | |
۱۰+ | ۴ | ۱۰ | ۴ | ۱۲ | ۶ | ۸ | ۸ | ۱۶ | ۶ | ۱۸ |
۲۰+ | ۸ | ۱۲ | ۱۰ | ۲۲ | ۸ | ۲۰ | ۱۲ | ۱۸ | ۱۲ | ۲۸ |
۳۰+ | ۸ | ۳۰ | ۱۶ | ۲۰ | ۱۶ | ۲۴ | ۱۲ | ۳۶ | ۱۸ | ۲۴ |
۴۰+ | ۱۶ | ۴۰ | ۱۲ | ۴۲ | ۲۰ | ۲۴ | ۲۲ | ۴۶ | ۱۶ | ۴۲ |
۵۰+ | ۲۰ | ۳۲ | ۲۴ | ۵۲ | ۱۸ | ۴۰ | ۲۴ | ۳۶ | ۲۸ | ۵۸ |
۶۰+ | ۱۶ | ۶۰ | ۳۰ | ۳۶ | ۳۲ | ۴۸ | ۲۰ | ۶۶ | ۳۲ | ۴۴ |
۷۰+ | ۲۴ | ۷۰ | ۲۴ | ۷۲ | ۳۶ | ۴۰ | ۳۶ | ۶۰ | ۲۴ | ۷۸ |
۸۰+ | ۳۲ | ۵۴ | ۴۰ | ۸۲ | ۲۴ | ۶۴ | ۴۲ | ۵۶ | ۴۰ | ۸۸ |
۹۰+ | ۲۴ | ۷۲ | ۴۴ | ۶۰ | ۴۶ | ۷۲ | ۳۲ | ۹۶ | ۴۲ | ۶۰ |
خط y = n-1 یک کران بالا برای تابع است و زمانی رخ میدهد که n اول باشد.
قضیه اویلر
بیان میکند: اگر n و a نسبت به هم اول باشند آنگاه
در حالت خاصی که n عدد اول باشد این قضیه به قضیه کوچک فرما معروف است. این قضیه از قضیه لاگرانژ نتیجه میشود.
سیستم رمزنگاری RSA بر روی همین قضیه بنا شده است: بیان میکنید که معکوس تابع
دیگر فرمولهای مرتبط با
- →
- (a, n> 1)
- d = gcd(m, n).
نسبت طلایی
اشنایدر دو رابطه پیدا کرد که نسبت طلایی و تابع فی و تابع موبیوس را به هم مرتبط میکرد.
در فرمولهای زیر
این روابط به صورت زیر هستند:
از کم کردن این دو نتیجه میشود
با اعمال تابع نمایی به هر دو طرف رابطه به یک رابطه برای عدد نپر میرسیم
اثبات بر پایه دو فرمول زیر است:
- and
توابع مولد
سری دیریکله برای تابع فی را میتوان بر حسب جملات تابع زتای ریمان به صورت زیر نوشت
- )
همچنین تابع مولد سری لامبرت به صورت زیر است
که در ان اندازه q کمتر از ۱ است. هر دو روابط بالا با استفاده ضرب سریهای پایه و با استفاده از فرمولهای محاسبه تابع فی قابل اثبات هستند.
نسبت دو جمله متوالی
در سال ۱۹۵۰ سومایاجولو اثبات کرد
و
کاربرد
رمزنگاری RSA
در سیستم RSA ابتدا دو عدد اول بزرگ p و q را انتخاب میکنیم. سپس مقادیر n=pq و k=
یک پیام مانند عدد مثبت m به صورت S = m mod n رمزگذاری میشود.
برای رمزگشایی مقدار t = S mod n محاسبه میشود. قضیه اویلر نشان میدهد که اگر t کمتر از n باشد آنگاه t=m.
سیستم RSA به خطر خواهد افتاد اگر بتوانیم عدد n را تجزیه کنیم یا بتوانیم مقدار تابع فی را بدون تجزیه n بدست بیاوریم.
مسئلههای حل نشده
حدس لیمر
اگر p اول باشد آنگاه
آیا عدد مرکب n وجود دارد بهطوریکه
در سال ۱۹۳۳ لیمر اثبات کرد که اگر n وجود داشته باشد آنگاه حتماً باید فرد باشد و باید حداقل ۷ عامل اول داشته باشد. در سال ۱۹۸۰ کوهن و هاگیس اثبات کردند که n>10 و باید حداقل ۱۴ عامل اول داشته باشد. بعدها هاگیس نشان داد که اگر n بر ۳ بخش پذیر باشد آنگاه n>10 و باید حداقل ۲۹۸۸۴۷ عامل اول داشته باشد.
حدس کارمایکل
حدس: هیچ عددی مانند n وجود ندارد بهطوریکه برای هر عدد دیگر مانند m داشته باشیم