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

כדי להימנע מפעולת הצמצום המודלורי שהיא פעולה לא יעילה במונחי מיחשוב אפשר לבצע את הטריק הבא: אם <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> אוניברסלית.