88-112 לינארית 1 תיכוניסטים קיץ תשעב/העשרה/הסבר על חישוב הופכי

כאשר אנו מבצעים חישובים בשדה $\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\leq a\leq 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$.

(היות ו $gcd(a,b)=1$ מובטח לנו שנגיע מתישהוא ל $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-4} - q_{k-3}r_{k-3}$ ב $r_{k-2}$ שמופיע בביטוי $(\ast)$ ולקבל ביטוי מהצורה

$xr_{k-4}+yr_{k-3}=1$ עבור $x,y$ כלשהם

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

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

• אם $b<0$ או $a<0$ אז מוצאים $n',m'$ מתאימים עבור $|a|,|b|$ בשיטה שתוארה קודם

ואז $n'|a|+m'|b|=1$ ואז

אם $a<0$ לוקחים $n=-n'$ (אחרת $n=n'$)

אם $b<0$ לוקחים $m=-m'$ (אחרת $m=m'$)

• אם $a=0$ הסיכוי היחיד ש $gcd(a,b)=1$ זה אם $b=1$ או $b=-1$ וזה מקרה פשוט

כנ"ל אם $b=0$

דוגמא

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

נחשב

$101-3\cdot 27=20$

$27-20=7$

$20-2\cdot7 = 6$

$7-6=1$

עכשיו נחשב אחורה

$3\cdot 7-20=1 \Leftarrow 7-(20-2\cdot 7)=1$

$3\cdot 27 - 4\cdot 20=1 \Leftarrow 3 \cdot (27-20)-20=1$

$15\cdot 27 - 4\cdot 101=1 \Leftarrow 3\cdot 27 - 4\cdot(101-3\cdot 27)$.

לכן ההופכי של 27 ב $\mathbb{Z}_{101}$ הוא 15.