88-112 לינארית 1 תיכוניסטים קיץ תשעב/העשרה/הסבר על חישוב הופכי
כאשר אנו מבצעים חישובים בשדה [math]\displaystyle{ \mathbb{Z}_p }[/math] (נזכור ש [math]\displaystyle{ p }[/math] חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.
שיטה אחת לבצע זאת היא ע"י מעבר על כל האפשרויות, אם [math]\displaystyle{ a\in \mathbb{Z}_p }[/math] אז יש [math]\displaystyle{ p }[/math] איברים שיכולים להיות הופכי: [math]\displaystyle{ \{0,1,\ldots,p-1\} }[/math]
(למעשה יש פחות, כי [math]\displaystyle{ 0 }[/math] לעולם לא יהיה הופכי ו [math]\displaystyle{ 1 }[/math] הופכי רק ב[math]\displaystyle{ \mathbb{Z}_2 }[/math])
אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.
שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב [math]\displaystyle{ \mathbb{Z}_{101} }[/math]? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
כדי להסביר איך מוצאים הופכי ב [math]\displaystyle{ \mathbb{Z}_p }[/math] נצטרך להביא כמה הקדמות מתורת המספרים.
כמה מושגים בתורת המספרים
הגדרה: יהיו [math]\displaystyle{ a,b\in \mathbb{Z} }[/math] אומרים ש [math]\displaystyle{ a }[/math] מחלק את [math]\displaystyle{ b }[/math] (ומסמנים [math]\displaystyle{ a|b }[/math]) אם קיים [math]\displaystyle{ c\in \mathbb{Z} }[/math] כך ש [math]\displaystyle{ ac=b }[/math].
הגדרה: יהיו [math]\displaystyle{ a,b\in \mathbb{Z} }[/math] המחלק המשותף המירבי של [math]\displaystyle{ a,b }[/math] (מסומן [math]\displaystyle{ gcd(a,b) }[/math]) הוא המספר הגדול ביותר שמחלק גם את [math]\displaystyle{ a }[/math] וגם את [math]\displaystyle{ b }[/math].
כלומר [math]\displaystyle{ gcd(a,b)=max\{g\in \mathbb{Z}\mid g|a\quad g|b\} }[/math]
ההגדרה הזאת בעייתית כאשר [math]\displaystyle{ a=b=0 }[/math] במצב זה אומרים ש [math]\displaystyle{ gcd(0,0)=0 }[/math].
נשים לב שאם [math]\displaystyle{ p }[/math] מספר ראשוני ו [math]\displaystyle{ 1\leq a\leq p-1 }[/math] אז [math]\displaystyle{ gcd(a,p)=1 }[/math]
משפט: יהיו [math]\displaystyle{ a,b\in \mathbb{Z} }[/math] ו [math]\displaystyle{ g=gcd(a,b) }[/math] אזי קיימים [math]\displaystyle{ m,n\in\mathbb{Z} }[/math] כך ש [math]\displaystyle{ na+mb=g }[/math].
הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב [math]\displaystyle{ \mathbb{Z}_p }[/math], כי אם [math]\displaystyle{ 0\neq a\in\mathbb{Z}_p }[/math] אז
[math]\displaystyle{ gcd(a,p)=1 }[/math] לכן קיימים [math]\displaystyle{ m,n }[/math] כך ש [math]\displaystyle{ na+mp=1 }[/math].
אם נפעיל [math]\displaystyle{ mod~p }[/math] על שני צידי המשוואה הזאת נקבל [math]\displaystyle{ (na+mp)mod~p = 1mod~p }[/math] שהופך ל [math]\displaystyle{ (na)mod~p = 1 }[/math] לכן [math]\displaystyle{ n~mod~p }[/math] הוא הופכי מתאים ל [math]\displaystyle{ a }[/math].
כל זה טוב ויפה, אבל איך מוצאים את [math]\displaystyle{ n }[/math]?
חישוב ההופכי
עבור שני מספרים [math]\displaystyle{ a,b \in \mathbb{Z} }[/math] כך ש [math]\displaystyle{ gcd(a,b)=1 }[/math] נתאר שיטה שבעזרתה ניתן למצוא את המספרים [math]\displaystyle{ n,m }[/math] כך ש [math]\displaystyle{ na+mb=1 }[/math].
- נתחיל מהמקרה [math]\displaystyle{ a,b\gt 0 }[/math]
נניח ש [math]\displaystyle{ b\gt a }[/math], נסמן [math]\displaystyle{ r_1=b \quad r_2 = a }[/math].
(אם [math]\displaystyle{ a\gt b }[/math] אז נסמן הפוך)
נחפש את המספר [math]\displaystyle{ q_2\in \mathbb{N} }[/math] הגדול ביותר כך ש [math]\displaystyle{ r_1-q_2r_2\gt 0 }[/math].
ונסמן [math]\displaystyle{ r_1-q_2r_2 = r_3 }[/math].
כעת נחפש את המספר הגדול ביותר [math]\displaystyle{ q_3\in \mathbb{N} }[/math] כך ש [math]\displaystyle{ r_2-q_3r_3\gt 0 }[/math]
ונסמן [math]\displaystyle{ r_2-q_3r_3 = r_4 }[/math].
נמשיך כך עד שנגיע לשלב [math]\displaystyle{ k }[/math] שבו [math]\displaystyle{ r_k=1 }[/math].
(היות ו [math]\displaystyle{ gcd(a,b)=1 }[/math] מובטח לנו שנגיע מתישהוא ל [math]\displaystyle{ 1 }[/math])
עד כאן החלק הקל,
עכשיו צריך להתחיל חישוב אחורה
השלב האחרון שהגענו אליו היה
[math]\displaystyle{ r_{k-2}-q_{k-1}r_{k-1} = r_k = 1 }[/math]
אבל בשלב הקודם קיבלנו ש [math]\displaystyle{ r_{k-3} - q_{k-2}r_{k-2} = r_{k-1} }[/math]
לכן אפשר להציב
[math]\displaystyle{ r_{k-2}-q_{k-1}(r_{k-3} - q_{k-2}r_{k-2}) = 1 }[/math]
שהופך ל: [math]\displaystyle{ (1+q_{k-1}q_{k-2})r_{k-2}-q_{k-1}r_{k-3} = 1 }[/math] [math]\displaystyle{ (\ast) }[/math]
אבל שוב, בשלב קודם ראינו ש
[math]\displaystyle{ r_{k-4} - q_{k-3}r_{k-3} =r_{k-2} }[/math]
ואפשר להציב את [math]\displaystyle{ r_{k-4} - q_{k-3}r_{k-3} }[/math] ב [math]\displaystyle{ r_{k-2} }[/math] שמופיע בביטוי [math]\displaystyle{ (\ast) }[/math] ולקבל ביטוי מהצורה
[math]\displaystyle{ xr_{k-4}+yr_{k-3}=1 }[/math] עבור [math]\displaystyle{ x,y }[/math] כלשהם
וכן הלאה עד שנגיע לביטוי מהצורה [math]\displaystyle{ mr_1+nr_2=1 }[/math]
שזה בדיוק [math]\displaystyle{ mb+na=1 }[/math].
- אם [math]\displaystyle{ b\lt 0 }[/math] או [math]\displaystyle{ a\lt 0 }[/math] אז מוצאים [math]\displaystyle{ n',m' }[/math] מתאימים עבור [math]\displaystyle{ |a|,|b| }[/math] בשיטה שתוארה קודם
ואז [math]\displaystyle{ n'|a|+m'|b|=1 }[/math] ואז
אם [math]\displaystyle{ a\lt 0 }[/math] לוקחים [math]\displaystyle{ n=-n' }[/math] (אחרת [math]\displaystyle{ n=n' }[/math])
אם [math]\displaystyle{ b\lt 0 }[/math] לוקחים [math]\displaystyle{ m=-m' }[/math] (אחרת [math]\displaystyle{ m=m' }[/math])
- אם [math]\displaystyle{ a=0 }[/math] הסיכוי היחיד ש [math]\displaystyle{ gcd(a,b)=1 }[/math] זה אם [math]\displaystyle{ b=1 }[/math] או [math]\displaystyle{ b=-1 }[/math] וזה מקרה פשוט
כנ"ל אם [math]\displaystyle{ b=0 }[/math]
דוגמא
מצא את ההופכי של [math]\displaystyle{ 27 }[/math] ב [math]\displaystyle{ \mathbb{Z}_{101} }[/math].
נחשב
[math]\displaystyle{ 101-3\cdot 27=20 }[/math]
[math]\displaystyle{ 27-20=7 }[/math]
[math]\displaystyle{ 20-2\cdot7 = 6 }[/math]
[math]\displaystyle{ 7-6=1 }[/math]
עכשיו נחשב אחורה
[math]\displaystyle{ 3\cdot 7-20=1 \Leftarrow 7-(20-2\cdot 7)=1 }[/math]
[math]\displaystyle{ 3\cdot 27 - 4\cdot 20=1 \Leftarrow 3 \cdot (27-20)-20=1 }[/math]
[math]\displaystyle{ 15\cdot 27 - 4\cdot 101=1 \Leftarrow 3\cdot 27 - 4\cdot(101-3\cdot 27) }[/math].
לכן ההופכי של 27 ב [math]\displaystyle{ \mathbb{Z}_{101} }[/math] הוא 15.