הופכי כפלי מודולרי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

הופכי כפל מודולרי הוא מושג במתמטיקה ובפרט בחשבון מודולרי.

באופן כללי, הופכי של מספר \ a הוא מספר \ b כך שמתקיים שמכפלת שני המספרים היא 1: \ a\cdot b=1. למשל, עבור מספרים רציונליים ההופכי של \ a הוא \ \frac{1}{a}.

כאשר עוסקים בחשבון מודולרי, שבו החשבון מתבצע עם מספרים שלמים בלבד, עדיין קיים מושג ההופכי, אך הוא שונה מעט. ההגדרה הבסיסית נותרת זהה: \ a,b הם הופכיים אם \ a\cdot b=1, כאשר הפעם הכפל הוא מודולרי.

על פי ההגדרה הפורמלית, a,b הם הופכיים כפליים מודולרים מודולו n, אם ab\equiv 1\ (\mbox{mod}\ n). לדוגמה, מודולו 9, ההופכי הכפלי של 2 הוא 5, מכיוון ש: 2\cdot 5=1\ (\mbox{mod}\ 9). על כן ניתן להגיד ש: 3:2=3\cdot 5 \ (\mbox{mod}\ 9). אפשר לבדוק ולהיווכח שאכן 5 הוא ההופכי של 2 בדוגמה זו, כלומר אחרי שנבצע פעולה והיפוכה נקבל בחזרה 3. מתקיים: (3:2)\cdot 2 \ (\mbox{mod}\ 9)\equiv (3\cdot 5)\cdot 2 \ (\mbox{mod}\ 9) = 3

ל-a יש הופכי מודולו n אם ורק אם a ו-n זרים. זאת מכיוון שחוג המספרים השלמים הוא תחום ראשי, עבור כל שני מספרים זרים a ו-n אפשר למצוא מספרים שלמים u ו-v כך ש- \ ua+vn=1. ניתן למצוא הופכי כפלי מודולרי באמצעות גרסה מורחבת של האלגוריתם האוקלידי. ההופכי של איבר בחבורת אוילר הוא ההופכי הכפלי המודולרי שלו.

בהופכי כפלי מודולרי משתמשים בפתרון קונגרואנציות (משוואת מודולריות), ובתחום ההצפנה, ביצירת מפתחות RSA.

ראו גם[עריכת קוד מקור | עריכה]

P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.