نسخهٔ قابل چاپ دیگر پشتیبانی نمیشود و ممکن است در زمان رندر کردن با خطا مواجه شوید. لطفاً بوکمارکهای مرورگر خود را بهروزرسانی کنید و در عوض از عمبکرد چاپ پیشفرض مرورگر خود استفاده کنید.
در نظریه اعدادتابع فی اویلر یا تابعی است که تعداد اعداد طبیعی کوچکتر مساوی n که نسبت به n اول اند را میشمارد. اگر n یک عدد طبیعی مثبت باشد، آنگاه برابر است با تعداد اعداد طبیعی k در بازه ۱ تا n بهطوریکه بزرگترین مقسومعلیه مشترک (ب.م.م) n و k برابر ۱ باشد.
تابع فی اویلر یک تابع ضربی است، بدین معنی که اگر دو عدد m و n نسبت به هم اول باشند آنگاه .
برای مثال (9)φ برابر ۶ است. زیرا اعداد ۱، ۲، ۴، ۵، ۷ و ۸ نسبت به ۹ اول هستند.
تابع فی اویلر نقش کلیدی در تعریف سیستم رمزنگاری RSA دارد.
تاریخچه و نمادگذاری
لئونارد اولر این تابع را در سال ۱۷۶۳ معرفی کرد. در آن زمان او هنوز نماد خاصی برای این تابع تعیین نکرده بود. بعدها لئونارد اویلر با مطالعه بیشتر تابع فی، حرف یونانی π را برای آن برگزید. نماد استاندارد φ بعدها توسط گاوس استفاده شدهاست.
محاسبه مقدار تابع فی
چندین راه برای محاسبه این فرمول وجود دارد.
فرمول ضرب اویلر
این تابع بیان میکند که:
که در آن یک عدد اول است بهطوریکه بر بخش پذیر نیست.
توجه کنید که برخلاف دو فرمول دیگر در این فرمول نیازی به دانستن عوامل اول n نیست. اما چون فرمول شامل محاسبه ب.م.م n و همه اعداد مثبت کمتر از n است در نهایت به تجزیه n نیاز خواهیم داشت.
در سیستم RSA ابتدا دو عدد اول بزرگ p و q را انتخاب میکنیم. سپس مقادیر n=pq و k= را محاسبه میکنیم؛ و دوعدد e و d را پیدا میکنیم بهطوریکه ed به پیمانه k برابر ۱ باشد. n و e به عنوان کلید عمومی اعلان میشوند و n و d به عنوان کلید خصوصی مخفی نگاه داشته میشود.
یک پیام مانند عدد مثبت m به صورت S = me mod n رمزگذاری میشود.
برای رمزگشایی مقدار t = Sd mod n محاسبه میشود. قضیه اویلر نشان میدهد که اگر t کمتر از n باشد آنگاه t=m.
سیستم RSA به خطر خواهد افتاد اگر بتوانیم عدد n را تجزیه کنیم یا بتوانیم مقدار تابع فی را بدون تجزیه n بدست بیاوریم.
مسئلههای حل نشده
حدس لیمر
اگر p اول باشد آنگاه . لیمر در سال ۱۹۳۲ سؤال زیر را مطرح کرد:
آیا عدد مرکب n وجود دارد بهطوریکه ؟
در سال ۱۹۳۳ لیمر اثبات کرد که اگر n وجود داشته باشد آنگاه حتماً باید فرد باشد و باید حداقل ۷ عامل اول داشته باشد. در سال ۱۹۸۰ کوهن و هاگیس اثبات کردند که n>1020 و باید حداقل ۱۴ عامل اول داشته باشد. بعدها هاگیس نشان داد که اگر n بر ۳ بخش پذیر باشد آنگاه n>101937042 و باید حداقل ۲۹۸۸۴۷ عامل اول داشته باشد.
حدس کارمایکل
حدس: هیچ عددی مانند n وجود ندارد بهطوریکه برای هر عدد دیگر مانند m داشته باشیم .
اگر یک مثال نقض برای این گزاره پیدا شود آنگاه میتوان نشان داد که بینهایت مثال نقض برای این گزاره وجود دارد.
میتوان نشان داد که کوچکترین مثال نقض برای این گزاره در مبنای ۱۰ بیش از ۱۰ میلیارد رقم دارد.