שינויים
יצירת דף עם התוכן "כאשר אנו מבצעים חישובים בשדה <math>\mathbb{Z}_p</math> (נזכור ש <math>p</math> חייב להיות ראשוני), אנו נדרשים ..."
כאשר אנו מבצעים חישובים בשדה <math>\mathbb{Z}_p</math> (נזכור ש <math>p</math> חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.
שיטה אחת לבצע זאת היא ע"י מעבר על כל האפשרויות,
אם <math>a\in \mathbb{Z}_p</math> אז יש <math>p</math> איברים שיכולים להיות הופכי: <math>\{0,1,\ldots,p-1\}</math>
(למעשה יש פחות, כי <math>0</math> לעולם לא יהיה הופכי ו <math>1</math> הופכי רק ב<math>\mathbb{Z}_2</math>)
אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.
שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב <math>\mathbb{Z}_{101}</math>? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
כדי להסביר איך מוצאים הופכי ב <math>\mathbb{Z}_p</math> נצטרך להביא כמה הקדמות מתורת המספרים.
== כמה מושגים בתורת המספרים ==
'''הגדרה''': יהיו <math>a,b\in \mathbb{Z}</math> אומרים ש <math>a</math> מחלק את <math>b</math> (ומסמנים <math>a|b</math>)
אם קיים <math>c\in \mathbb{Z}</math> כך ש <math>ac=b</math>.
'''הגדרה''': יהיו <math>a,b\in \mathbb{Z}</math> המחלק המשותף המירבי של <math>a,b</math> (מסומן <math>gcd(a,b)</math>) הוא המספר הגדול ביותר שמחלק גם את <math>a</math> וגם את <math>b</math>.
כלומר <math>gcd(a,b)=max\{g\in \mathbb{Z}\mid g|a\quad g|b\}</math>
ההגדרה הזאת בעייתית כאשר <math>a=b=0</math> במצב זה אומרים ש <math>gcd(0,0)=0</math>.
נשים לב שאם <math>p</math> מספר ראשוני ו <math>1\leq a\leq p-1</math> אז <math>gcd(a,p)=1</math>
'''משפט''': יהיו <math>a,b\in \mathbb{Z}</math> ו <math>g=gcd(a,b)</math> אזי קיימים <math>m,n\in\mathbb{Z}</math> כך ש <math>na+mb=g</math>.
הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב <math>\mathbb{Z}_p</math>, כי אם <math>0\neq a\in\mathbb{Z}_p</math> אז
<math>gcd(a,p)=1</math> לכן קיימים <math>m,n</math> כך ש <math>na+mp=1</math>.
אם נפעיל <math>mod~p</math> על שני צידי המשוואה הזאת נקבל
<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>gcd(a,b)=1</math> מובטח לנו שנגיע מתישהוא ל <math>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-4} - q_{k-3}r_{k-3}</math> ב <math>r_{k-2}</math>
שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה
<math>xr_{k-4}+yr_{k-3}=1</math>
עבור <math>x,y</math> כלשהם
וכן הלאה עד שנגיע לביטוי מהצורה
<math>mr_1+nr_2=1</math>
שזה בדיוק
<math>mb+na=1</math>.
* אם <math>b<0</math> או <math>a<0</math> אז מוצאים <math>n',m'</math> מתאימים עבור <math>|a|,|b|</math> בשיטה שתוארה קודם
ואז <math>n'|a|+m'|b|=1</math> ואז
אם <math>a<0</math> לוקחים <math>n=-n'</math> (אחרת <math>n=n'</math>)
אם <math>b<0</math> לוקחים <math>m=-m'</math> (אחרת <math>m=m'</math>)
* אם <math>a=0</math> הסיכוי היחיד ש <math>gcd(a,b)=1</math> זה אם <math>b=1</math> או <math>b=-1</math> וזה מקרה פשוט
כנ"ל אם <math>b=0</math>
== דוגמא ==
מצא את ההופכי של <math>27</math> ב <math>\mathbb{Z}_{101}</math>.
נחשב
<math>101-3\cdot 27=20</math>
<math>27-20=7</math>
<math>20-2\cdot7 = 6</math>
<math>7-6=1</math>
עכשיו נחשב אחורה
<math>3\cdot 7-20=1 \Leftarrow 7-(20-2\cdot 7)=1</math>
<math>3\cdot 27 - 4\cdot 20=1 \Leftarrow 3 \cdot (27-20)-20=1</math>
<math>15\cdot 27 - 4\cdot 101=1 \Leftarrow 3\cdot 27 - 4\cdot(101-3\cdot 27)</math>.
לכן ההופכי של 27 ב <math>\mathbb{Z}_{101}</math> הוא 15.
שיטה אחת לבצע זאת היא ע"י מעבר על כל האפשרויות,
אם <math>a\in \mathbb{Z}_p</math> אז יש <math>p</math> איברים שיכולים להיות הופכי: <math>\{0,1,\ldots,p-1\}</math>
(למעשה יש פחות, כי <math>0</math> לעולם לא יהיה הופכי ו <math>1</math> הופכי רק ב<math>\mathbb{Z}_2</math>)
אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.
שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב <math>\mathbb{Z}_{101}</math>? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
כדי להסביר איך מוצאים הופכי ב <math>\mathbb{Z}_p</math> נצטרך להביא כמה הקדמות מתורת המספרים.
== כמה מושגים בתורת המספרים ==
'''הגדרה''': יהיו <math>a,b\in \mathbb{Z}</math> אומרים ש <math>a</math> מחלק את <math>b</math> (ומסמנים <math>a|b</math>)
אם קיים <math>c\in \mathbb{Z}</math> כך ש <math>ac=b</math>.
'''הגדרה''': יהיו <math>a,b\in \mathbb{Z}</math> המחלק המשותף המירבי של <math>a,b</math> (מסומן <math>gcd(a,b)</math>) הוא המספר הגדול ביותר שמחלק גם את <math>a</math> וגם את <math>b</math>.
כלומר <math>gcd(a,b)=max\{g\in \mathbb{Z}\mid g|a\quad g|b\}</math>
ההגדרה הזאת בעייתית כאשר <math>a=b=0</math> במצב זה אומרים ש <math>gcd(0,0)=0</math>.
נשים לב שאם <math>p</math> מספר ראשוני ו <math>1\leq a\leq p-1</math> אז <math>gcd(a,p)=1</math>
'''משפט''': יהיו <math>a,b\in \mathbb{Z}</math> ו <math>g=gcd(a,b)</math> אזי קיימים <math>m,n\in\mathbb{Z}</math> כך ש <math>na+mb=g</math>.
הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב <math>\mathbb{Z}_p</math>, כי אם <math>0\neq a\in\mathbb{Z}_p</math> אז
<math>gcd(a,p)=1</math> לכן קיימים <math>m,n</math> כך ש <math>na+mp=1</math>.
אם נפעיל <math>mod~p</math> על שני צידי המשוואה הזאת נקבל
<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>gcd(a,b)=1</math> מובטח לנו שנגיע מתישהוא ל <math>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-4} - q_{k-3}r_{k-3}</math> ב <math>r_{k-2}</math>
שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה
<math>xr_{k-4}+yr_{k-3}=1</math>
עבור <math>x,y</math> כלשהם
וכן הלאה עד שנגיע לביטוי מהצורה
<math>mr_1+nr_2=1</math>
שזה בדיוק
<math>mb+na=1</math>.
* אם <math>b<0</math> או <math>a<0</math> אז מוצאים <math>n',m'</math> מתאימים עבור <math>|a|,|b|</math> בשיטה שתוארה קודם
ואז <math>n'|a|+m'|b|=1</math> ואז
אם <math>a<0</math> לוקחים <math>n=-n'</math> (אחרת <math>n=n'</math>)
אם <math>b<0</math> לוקחים <math>m=-m'</math> (אחרת <math>m=m'</math>)
* אם <math>a=0</math> הסיכוי היחיד ש <math>gcd(a,b)=1</math> זה אם <math>b=1</math> או <math>b=-1</math> וזה מקרה פשוט
כנ"ל אם <math>b=0</math>
== דוגמא ==
מצא את ההופכי של <math>27</math> ב <math>\mathbb{Z}_{101}</math>.
נחשב
<math>101-3\cdot 27=20</math>
<math>27-20=7</math>
<math>20-2\cdot7 = 6</math>
<math>7-6=1</math>
עכשיו נחשב אחורה
<math>3\cdot 7-20=1 \Leftarrow 7-(20-2\cdot 7)=1</math>
<math>3\cdot 27 - 4\cdot 20=1 \Leftarrow 3 \cdot (27-20)-20=1</math>
<math>15\cdot 27 - 4\cdot 101=1 \Leftarrow 3\cdot 27 - 4\cdot(101-3\cdot 27)</math>.
לכן ההופכי של 27 ב <math>\mathbb{Z}_{101}</math> הוא 15.
