הבדלים בין גרסאות בדף "פונקציית גיבוב"

מ
קישורים פנימיים
מ (הוספת פרק הערות שוליים **)
מ (קישורים פנימיים)
כדי להימנע מפעולת הצמצום המודלורי שהיא פעולה לא יעילה במונחי מיחשוב אפשר לבצע את הטריק הבא: אם <math>p=2^j-1</math> עבור <math>j</math> כלשהו (למשל <math>2^{11}-1</math> הוא מספר ראשוני), אם <math>x</math> ניתן לייצוג על ידי <math>2j</math> סיביות אזי קיימים <math>x_1,x_2<2^j</math> כך שמתקיים <math>x= 2^jx_1+x_2</math> במילים אחרות <math>x_1</math> הוא <math>j</math> הסיביות המשמעותיות ביותר של <math>x</math> ו-<math>x_2</math> הוא <math>j</math> הסיביות הפחות משמעותיות. היות ש-<math>2^j\equiv 1 \ (\text{ mod }p)</math> מתקיים:
:<math>x\equiv x_1+x_2 \ (\text{ mod }p)</math>
פועל יוצא הוא שהערך <math>x</math> אותו מעוניינים למפות מצטמצם מודולו <math>p</math> למספר בגודל <math>j+1</math> סיביות. כי כדי לחשב את <math>x(\text{mod }p)</math> מספיק לחשב את <math>x_1+x_2</math>, לבצע בדיקה אם הוא גדול מ-<math>p</math> ולכל היותר יידרש חיסור אחד של <math>p</math>. לסיכום אם <math>b</math> הוא [[חזקה של 2]], כל התהליך מצטמצם לכפל אחד, שתי פעולות חיבור, הזזה (shift) ופעולה לוגית אחת ואין צורך במודולו כלל.
 
דרך אחרת להימנע מחילוק הוצעה על ידי Dietzfelbinger. נוטלים את הסיביות המשמעותיות של התוצאה. לדוגמה אם <math>k=32</math>, אם התוצאה בגודל 64 סיביות, נוטלים רק את 32 הסיביות המשמעותיות, או בניסוח אחר: <math>h_{m,n}(x)=(mx+n) \gg k</math> כאשר <math>\gg</math> הוא הזזה לימין (shift right), אזי הפונקציה <math>h_{m,n}(x)</math> אוניברסלית.