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