משהו אחר לשם שינוי...

[yossiea]

משהו אחר לשם שינוי...

פסק זמן קט, מהעיסוק במתן ציונים לכל המכללות למיניהם. שאלה ליודעי ח"ן (חכמה נסתרה)

סתם.. שאלה פשוטה במתמטיקה. האם מישהו במקרה יכול להסביר למפגר כמוני את הביטוי הבא: x = -m^(-1) mod b עבור שלמים כלשהם b, m. כאשר b<m, באריטמתטיקה מודולרית. (Ctrl+left shift כדי לראות את זה נכון

). טוב. אני הסקתי מתוך המעט שאני יודע שבאריתמטיקה מודולרית אם מתקבלת תוצאה שלילית כלשהי הופכים אותה לחיובית בחיבור עם המודולוס. אז בביטוי הזה חשבתי ככה, קודם למצוא את ה-inverse של m ביחס ל-b, אח"כ להפוך את הסימן של התוצאה ואז רק אם מתקבל מספר אפשר לחבר עם המודולוס. לדוגמא אם: m=12345, b=601. התוצאה שמתקבלת מחישוב Euclid(m,b) היא: 601*4786 + -233*12345 = 1 ולכן בשלב זה: x = -233 כעת השאלה (לפי הביטוי) האם להפוך סימן קודם: x=233 ואז כיוון ש- x<b, אין צורך בחישוב נוסף) וזו תהיה התוצאה. או קודם לחבר עם המודולוס: -233 + 601 = 368 ואז x=368. השאלה היא איזה משניהם הוא הערך הנכון. האם x=233 או x=368? ומה במקרה הזה? m=17043,b=248 אז Euclid נותן: 115*17043 + -7903*248 = 1 נראה לי שהתוצאה צריכה להיות: x = -115 + 248 = 133 כיוון שאחרי הפיכת סימן x נהיה שלילי אני צריך לחבר עם המודולוס וזה נותן 133. (ההבדל בין שני השאלות הוא תוצאת Euclid שבראשונה היא שלילית בשנייה חיובית). לחדד את השאלה האם הפיכת הסימן בביטוי לעיל היא בעצם חיבור עם המודולו כנהוג באיתמטיקה מודולרית או הפיכת סימן רגילה (כמו אריתמטיקה רגילה)? קשה לי להסיק מהביטוי עצמו מה הנכון. בכל אופן בשני המקרים זה נכון שהערכים הללו קשורים הדדית ואפשר לשחק עם הסימן, זה מעניין כי יוצא באמת ש: -368 = 233 (mod 601) -233 = 368 (mod 601) וכן -115 = 133 (mod 248) -133 = 115 (mod 248) טוב אולי זה שאלה שמתאימה יותר לפורום למתמטיקה. בשבילי בכל אופן זה קשור מאוד ל"מדעי מחשב".

 

[vinney]

לדעתי - 368

ז"א - תוצר של מודולו חייב להיות חיובי. הרי מודולו זה שארית החלוקה, שארית לא יכולה להיות שלילית. אז גם אם B וM הם שלמים, טווח של המודולו הוא בN. חש דוגמא מאוד דומה (לדעתי) באתר "חשבון מודולרי" בויקיפדיה.

 

[DadleFish]

שארית יכולה להיות שלילית,

הנה, פה.

 

[vinney]

יש לי בעיה עם המאמר הזה...

למרות שהוא מתייחס דווקא ל"COMPUTING", שזה נושא הפורום הזה, בין היתר, מודולו זאת פונקציה מתמטית, וככזאת, מגבלות שפה/חישוביות לא אמורות לחול עליה. בהגדרת השארית במאמר, אם תשים לב, יש ערך מוחלט. יחד עם זאת שורה מתחת הם אומרים שהיא יכולה להיות שלילית, זאת הרי סתירה. קצת פישי, הייתי עורך את זה טיפה יותר טוב במקום העורכים של ויקי...

אבל הבנתי את הכוונה שלך, אז איך לדעתך צריך לפתור את הבעיה של יוסי?

 

[DadleFish]

אני מצטרף לדעתך לגבי ה-368.

ההערה שלי הייתה כללית לגבי יכולת השארית להיות שלילית. לגבי המאמר - שים לב שהערך המוחלט לא מגדיר את r אלא הופך אותו לחיובי למטרת האילוץ שלו לתחום שבין 0 לבין n-1. כמו שכתוב שם, ואני תומך בהגדרה הזו, יש כל מיני דרכים להגדיר שארית, והם נותנים שם נוסחה "פופולרית". כך למשל לפי המספרים שיוסי נתן, השארית של m%b צריכה להיות:

r=12345-601*floor(12345/601)=12345-601*20=-325​

 

[yossiea]

אני מקבל...

קראתי את שני הכתבות של ויקי... ראיתי בעוד כמה מקומות ששארית יכולה להיות שלילית. סתם לדוגמא, אני לא יודע אם זה דוגמא טובה, במחשבון של ווינדוס אפשר בהחלט לקבל שארית שלילית. ודוגמא יותר טובה, הקומפיילר של Micro$oft מאפשר בהחלט שארית שלילית (זה בדוק): -12345 % 601 = -325 אבל לדאבוני כל זה לא עונה לשאלה שלי. אני אמנם מעוניין לקבל תשובה חיובית בסיכומו של דבר, אבל בתהליך, האם אין מצב ביניים כלשהו שאני יקבל ערך שלילי? והאם להתייחס למספר -233 בדוגמא שלי כאל 368 מראש. או שאפשר לקבל את זה כמספר תקף. לפי הנחה שבחשבון מודולרי אפשר לקבל תוצאה שלילית. המשמעות של התושבה שלכם היא שלא יכול להיות מצב של ערך שלילי. אז איך אני מתייחס למצב שאני צריך להפוך סימן של מספר שכבר מסומן?. מה שנקרא הפוך על הפוך. זה קצת מוזר... אבל הסתבכתי עם זה, אם כי בניסויים מעשיים שעשיתי דוקא הצלחתי להגיע לערך הנכון בלי לדעת את החוקיות. למשל התשובה הנכונה לביטוי הבא היא 1 -72639^-1 mod 10 = 1 מדוע ומה החוקיות, זה קצת קשה לי להגדיר. למותר לציין שלמטרה שלשמה אני צריך את זה (קריפטוגרפיה) יש צורך כמובן בערך חיובי בלבד ועל כן ברור שצריך להפוך את התשובה (בסוף התהליך) למספר חיובי כלשהו. עם זה אין לי בעייה.

 

[vinney]

ערך שלילי תלוי ישירות

במחלק. אם המחלק שלילי - הערך של השארית יהיה שלילי. אם המחלק חיובי - השארית תהיה חיובית.