איתמר שטיין (שיחה | תרומות) (←חישוב ההפכי) |
איתמר שטיין (שיחה | תרומות) (←כמה מושגים בתורת המספרים) |
||
(10 גרסאות ביניים של אותו משתמש אינן מוצגות) | |||
שורה 1: | שורה 1: | ||
כאשר אנו מבצעים חישובים בשדה <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>a\in \mathbb{Z}_p</math> אז יש <math>p</math> איברים שיכולים להיות הופכי: <math>\{0,1,\ldots,p-1\}</math> | ||
שורה 23: | שורה 23: | ||
ההגדרה הזאת בעייתית כאשר <math>a=b=0</math> במצב זה אומרים ש <math>gcd(0,0)=0</math>. | ההגדרה הזאת בעייתית כאשר <math>a=b=0</math> במצב זה אומרים ש <math>gcd(0,0)=0</math>. | ||
− | נשים לב שאם <math>p</math> מספר ראשוני ו <math>1\ | + | נשים לב שאם <math>p</math> מספר ראשוני ו <math>1\leq a\leq p-1</math> אז <math>gcd(a,p)=1</math> |
שורה 35: | שורה 35: | ||
<math>(na+mp)mod~p = 1mod~p</math> | <math>(na+mp)mod~p = 1mod~p</math> | ||
שהופך ל <math>(na)mod~p = 1</math> | שהופך ל <math>(na)mod~p = 1</math> | ||
− | לכן <math>n~mod~p</math> הוא | + | לכן <math>n~mod~p</math> הוא הופכי מתאים ל <math>a</math>. |
כל זה טוב ויפה, אבל איך מוצאים את <math>n</math>? | כל זה טוב ויפה, אבל איך מוצאים את <math>n</math>? | ||
+ | |||
== חישוב ההופכי == | == חישוב ההופכי == | ||
שורה 44: | שורה 45: | ||
− | נתחיל מהמקרה <math>a,b>0</math> | + | * נתחיל מהמקרה <math>a,b>0</math> |
נניח ש <math>b>a</math>, נסמן <math>r_1=b \quad r_2 = a</math>. | נניח ש <math>b>a</math>, נסמן <math>r_1=b \quad r_2 = a</math>. | ||
שורה 59: | שורה 60: | ||
נמשיך כך עד שנגיע לשלב <math>k</math> שבו <math>r_k=1</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-2}-q_{k-1}r_{k-1} = r_k = 1</math> | ||
שורה 73: | שורה 80: | ||
שהופך ל: | שהופך ל: | ||
<math>(1+q_{k-1}q_{k-2})r_{k-2}-q_{k-1}r_{k-3} = 1</math> <math>(\ast)</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} =r_{k-2}</math> | ||
− | ואפשר להציב את | + | |
− | <math>r_{k-2}</math> | + | ואפשר להציב את <math>r_{k-4} - q_{k-3}r_{k-3}</math> ב <math>r_{k-2}</math> |
שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה | שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה | ||
<math>xr_{k-4}+yr_{k-3}=1</math> | <math>xr_{k-4}+yr_{k-3}=1</math> | ||
+ | עבור <math>x,y</math> כלשהם | ||
וכן הלאה עד שנגיע לביטוי מהצורה | וכן הלאה עד שנגיע לביטוי מהצורה | ||
שורה 89: | שורה 98: | ||
− | אם <math> | + | * אם <math>b<0</math> או <math>a<0</math> אז מוצאים <math>n',m'</math> מתאימים עבור <math>|a|,|b|</math> בשיטה שתוארה קודם |
− | ואז <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. |
גרסה אחרונה מ־18:02, 12 ביולי 2012
כאשר אנו מבצעים חישובים בשדה (נזכור ש
חייב להיות ראשוני), אנו נדרשים לפעמים לחשב הופכי לאיבר מסוים בשדה.
שיטה אחת לבצע זאת היא ע"י מעבר על כל האפשרויות,
אם אז יש
איברים שיכולים להיות הופכי:
(למעשה יש פחות, כי לעולם לא יהיה הופכי ו
הופכי רק ב
)
אפשר פשוט לנסות את כל האפשרויות עד שמוצאים הופכי.
שיטה זו טובה לשדות קטנים, אבל מה עושים אם רוצים למצוא הופכי ב ? בשיטה הזאת נצטרך לנסות 99 אפשרויות.
כדי להסביר איך מוצאים הופכי ב נצטרך להביא כמה הקדמות מתורת המספרים.
כמה מושגים בתורת המספרים
הגדרה: יהיו אומרים ש
מחלק את
(ומסמנים
)
אם קיים
כך ש
.
הגדרה: יהיו המחלק המשותף המירבי של
(מסומן
) הוא המספר הגדול ביותר שמחלק גם את
וגם את
.
כלומר
ההגדרה הזאת בעייתית כאשר במצב זה אומרים ש
.
נשים לב שאם מספר ראשוני ו
אז
משפט: יהיו ו
אזי קיימים
כך ש
.
הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב , כי אם
אז
לכן קיימים
כך ש
.
אם נפעיל על שני צידי המשוואה הזאת נקבל
שהופך ל
לכן
הוא הופכי מתאים ל
.
כל זה טוב ויפה, אבל איך מוצאים את ?
חישוב ההופכי
עבור שני מספרים כך ש
נתאר שיטה שבעזרתה ניתן למצוא את המספרים
כך ש
.
- נתחיל מהמקרה
נניח ש , נסמן
.
(אם אז נסמן הפוך)
נחפש את המספר הגדול ביותר כך ש
.
ונסמן .
כעת נחפש את המספר הגדול ביותר כך ש
ונסמן .
נמשיך כך עד שנגיע לשלב שבו
.
(היות ו מובטח לנו שנגיע מתישהוא ל
)
עד כאן החלק הקל,
עכשיו צריך להתחיל חישוב אחורה
השלב האחרון שהגענו אליו היה
אבל בשלב הקודם קיבלנו ש
לכן אפשר להציב
שהופך ל:
אבל שוב, בשלב קודם ראינו ש
ואפשר להציב את ב
שמופיע בביטוי
ולקבל ביטוי מהצורה
עבור
כלשהם
וכן הלאה עד שנגיע לביטוי מהצורה
שזה בדיוק
.
- אם
או
אז מוצאים
מתאימים עבור
בשיטה שתוארה קודם
ואז ואז
אם לוקחים
(אחרת
)
אם לוקחים
(אחרת
)
- אם
הסיכוי היחיד ש
זה אם
או
וזה מקרה פשוט
כנ"ל אם
דוגמא
מצא את ההופכי של ב
.
נחשב
עכשיו נחשב אחורה
.
לכן ההופכי של 27 ב הוא 15.