הבדלים בין גרסאות בדף "משתמש:איתמר שטיין/הסבר הופכי"

גרסה מ־11:30, 11 ביולי 2012

כאשר אנו מבצעים חישובים בשדה $\mathbb{Z}_p$ (נזכור ש $p$ חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.

שיטה אחת לבצע זאת היא ע"י ניחוש, אם $a\in \mathbb{Z}_p$ אז יש $p$ איברים שיכולים להיות הופכי: $\{0,1,\ldots,p-1\}$

(למעשה יש פחות, כי $0$ לעולם לא יהיה הופכי ו $1$ הופכי רק ב $\mathbb{Z}_2$ )

אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.

שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב $\mathbb{Z}_{101}$ ? בשיטה הזאת נצטרך לנסות 99 אפשרויות.

כדי להסביר איך מוצאים הופכי ב $\mathbb{Z}_p$ נצטרך להביא כמה הקדמות מתורת המספרים.

כמה מושגים בתורת המספרים

הגדרה: יהיו $a,b\in \mathbb{Z}$ אומרים ש $a$ מחלק את $b$ (ומסמנים $a|b$ ) אם קיים $c\in \mathbb{Z}$ כך ש $ac=b$ .

הגדרה: יהיו $a,b\in \mathbb{Z}$ המחלק המשותף המירבי של $a,b$ (מסומן $gcd(a,b)$ ) הוא המספר הגדול ביותר שמחלק גם את $a$ וגם את $b$ .

כלומר $gcd(a,b)=max\{g\in \mathbb{Z}\mid g|a\quad g|b\}$

ההגדרה הזאת בעייתית כאשר $a=b=0$ במצב זה אומרים ש $gcd(0,0)=0$ .

נשים לב שאם $p$ מספר ראשוני ו $1\geq a\geq p-1$ אז $gcd(a,p)=1$

משפט: יהיו $a,b\in \mathbb{Z}$ ו $g=gcd(a,b)$ אזי קיימים $m,n\in\mathbb{Z}$ כך ש $na+mb=g$ .

הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב $\mathbb{Z}_p$ , כי אם $0\neq a\in\mathbb{Z}_p$ אז $gcd(a,p)=1$ לכן קיימים $m,n$ כך ש $na+mp=1$ .

אם נפעיל $mod~p$ על שני צידי המשוואה הזאת נקבל $(na+mp)mod~p = 1mod~p$ שהופך ל $(na)mod~p = 1$ לכן $n~mod~p$ הוא הפכי מתאים ל $a$ .

כל זה טוב ויפה, אבל איך מוצאים את $n$ ?

חישוב ההפכי

עבור שני מספרים $a,b \in \mathbb{Z}$ כך ש $gcd(a,b)=1$ נתאר שיטה שבעזרתה ניתן למצוא את המספרים $n,m$ כך ש $na+mb=1$ .

נתחיל מהמקרה $a,b>0$

נניח ש $b>a$ , נסמן $r_1=b \quad r_2 = a$ .

(אם $a>b$ אז נסמן הפוך)

נחפש את המספר $q_2\in \mathbb{N}$ הגדול ביותר כך ש $r_1-q_2r_2>0$ .

ונסמן $r_1-q_2r_2 = r_3$ .

כעת נחפש את המספר הגדול ביותר $q_3\in \mathbb{N}$ כך ש $r_2-q_3r_3>0$

ונסמן $r_2-q_3r_3 = r_4$ .

נמשיך כך עד שנגיע לשלב $k$ שבו $r_k=1$ .

עד כאן החלק הקל, עכשיו צריך להתחיל חישוב אחורה $r_{k-2}-q_{k-1}r_{k-1} = r_k = 1$

אבל בשלב הקודם קיבלנו ש $r_{k-3} - q_{k-2}r_{k-2} = r_{k-1}$

לכן אפשר להציב

$r_{k-2}-q_{k-1}(r_{k-3} - q_{k-2}r_{k-2}) = 1$

שהופך ל: $(1+q_{k-1}q_{k-2})r_{k-2}-q_{k-1}r_{k-3} = 1$ $(\ast)$

אבל שוב, בשלב קודם ראינו ש $r_{k-4} - q_{k-3}r_{k-3} =r_{k-2}$ ואפשר להציב את התוצאה ב $r_{k-2}$ שמופיע בביטוי $(\ast)$ ולקבל ביטוי מהצורה

$xr_{k-4}+yr_{k-3}=1$

וכן הלאה עד שנגיע לביטוי מהצורה $mr_1+nr_2=1$

שזה בדיוק $mb+na=1$ .

אם $a,b<0$ אז מוצאים $n,m$ מתאימים עבור $|a|,|b|$

ואז $(-n)a+(-m)b=n|a|+m|b|=1$ אז פשוט לוקחים את $-n,-m$ .

דוגמא

מצא את ההפכי של ב $\mathbb{Z}_{101}$ .

@@ שורה 35: / שורה 35: @@
 <math>(na+mp)mod~p = 1mod~p</math>
 שהופך ל <math>(na)mod~p = 1</math>
 לכן <math>n~mod~p</math> הוא הפכי מתאים ל <math>a</math>.
+כל זה טוב ויפה, אבל איך מוצאים את <math>n</math>?
+== חישוב ההפכי ==
+עבור שני מספרים <math>a,b \in \mathbb{Z}</math> כך ש <math>gcd(a,b)=1</math>
+נתאר שיטה שבעזרתה ניתן למצוא את המספרים <math>n,m</math> כך ש <math>na+mb=1</math>.
+נתחיל מהמקרה <math>a,b>0</math>
+נניח ש <math>b>a</math>, נסמן <math>r_1=b \quad r_2 = a</math>.
+(אם <math>a>b</math> אז נסמן הפוך)
+נחפש את המספר <math>q_2\in \mathbb{N}</math> הגדול ביותר כך ש <math>r_1-q_2r_2>0</math>.
+ונסמן <math>r_1-q_2r_2 = r_3</math>.
+כעת נחפש את המספר הגדול ביותר <math>q_3\in \mathbb{N}</math> כך ש <math>r_2-q_3r_3>0</math>
+ונסמן  <math>r_2-q_3r_3 = r_4</math>.
+נמשיך כך עד שנגיע לשלב <math>k</math> שבו <math>r_k=1</math>.
+עד כאן החלק הקל,
+עכשיו צריך להתחיל חישוב אחורה
+<math>r_{k-2}-q_{k-1}r_{k-1} = r_k = 1</math>
+אבל בשלב הקודם קיבלנו ש <math>r_{k-3} - q_{k-2}r_{k-2} = r_{k-1}</math>
+לכן אפשר להציב
+<math>r_{k-2}-q_{k-1}(r_{k-3} - q_{k-2}r_{k-2}) = 1</math>
+שהופך ל:
+<math>(1+q_{k-1}q_{k-2})r_{k-2}-q_{k-1}r_{k-3} = 1</math> <math>(\ast)</math>
+אבל שוב, בשלב קודם ראינו ש
+<math>r_{k-4} - q_{k-3}r_{k-3} =r_{k-2}</math>
+ואפשר להציב את התוצאה ב
+<math>r_{k-2}</math>
+שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה
+<math>xr_{k-4}+yr_{k-3}=1</math>
+וכן הלאה עד שנגיע לביטוי מהצורה
+<math>mr_1+nr_2=1</math>
+שזה בדיוק
+<math>mb+na=1</math>.
+אם <math>a,b<0</math> אז מוצאים <math>n,m</math> מתאימים עבור <math>|a|,|b|</math>
+ואז <math>(-n)a+(-m)b=n|a|+m|b|=1</math> אז פשוט לוקחים את <math>-n,-m</math>.
+== דוגמא ==
+מצא את ההפכי של ב <math>\mathbb{Z}_{101}</math>.

הבדלים בין גרסאות בדף "משתמש:איתמר שטיין/הסבר הופכי"

גרסה מ־11:30, 11 ביולי 2012

כמה מושגים בתורת המספרים

חישוב ההפכי

דוגמא

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים