HASH

[alice2109]

HASH

שלום
שאלה מתוך מבחן במבני נתונים אשמח לעזרה:
כל ילד צרפתי לומד בבית ספר יסודי את הבדיקה הפשוטה הבאה שאמורה לגלות
טעויות בכפל מספרים גדולים. הבדיקה מבוססת על Hashing בצורה הבאה: נתונים שני מספרים
X -ו Y שעלינו להכפיל. כדי לבדוק שהתוצאה ∗ = Z X Y שקיבלנו אכן נכונה, ניקח פונקציה h
hash ונכפיל ( ) ∗( ) h X h Y ונשווה ל ( )h Z . אם קיבלנו תשובות שונות, סימן שטעינו.
הפונקציה h היא פשוט סכום הספרות עד שנגיע לספרה אחת, כאשר 9 נחשב ל .0
Z =12193185172992 ואז Y = 98765432 , X =123456 :לדוגמה
h Z( ) = → 60 6 h X( ) = →21 3 h Y( ) = → 44 8
3×8 = 24 → 6 מתקיים ואכן

כדי להבין מדוע שיטה זו פועלת, שימו לב ש 9- אינו משפיע על חישוב הפונקציה h, למשל
." 9 לפי החוק" א"ז ,règle par 9 נקראת השיטה לכן .( h h (49 13 4 ) = = ( )

)א רשום/י נוסחה רקורסיבית עבור (h(XY .
h(x) = X mod 9 ש י/ הראה ב(
)ג הוכח /י את נכונות השיטה.

 

[אורי769]

הדרכה

למעשה מה שצריך להוכיח כאן זה שסכום הספרות הסופי של מספר זה השארית מודולו 9. זה תרגיל נחמד, שהוא מתמטי בעיקרו. השאלה אם למדת או את מכירה בכך שפעולת שארית מודולו n היא פעולה "שומרת" כפל וחיבור. כלומר
ZZ (a+b) mod n = ((a mod n)+(b mod n)) mod n
ZZ (a*b) mod n = ((a mod n)*(b mod n)) mod n
הטענות האלה אינן קשות במיוחד אבל חשוב להבין אותן (לתרגיל הזה... ולחיים בכלל).

ברגע שעוברים את המשוכה הזו אז נחזור להוכיח שסכום הספרות הסופי הוא השארית מודולו 9. נתחיל מהעובדה שכל חזקה של 10 מקיימת את הטענה הזו. זה קל. נמשיך מכך שכל כפולה של חזקה זה 10 מקיימת. זה נובע מהכפליות של המודולו שציינתי למעלה. לסיום נראה שעבור כל מספר X, השארית שלו מודולו 9 שווה לשארית של סכום הספרות שלו מודולו 9. זה נובע ממה שהוכחנו עד כה ומהכלל של החיבור שציינת קודם.
כלל הכפל שנזכר למעלה גם עונה על סעיף ג' בתרגיל.