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

נוספו 1,095 בתים ,  לפני 6 שנים
לדוגמה אם נתונה קבוצה <math>A=\{0,1,...,a-1\}</math> עם <math>a</math> אלמנטים והקבוצה <math>B=\{0,1,...,b-1\}</math> עם <math>b</math> אלמנטים ונתון מספר ראשוני <math>p\ge a</math> והפונקציה <math>g</math> שממפה אלמנטים מ-<math>Z_p</math> לקבוצה <math>B</math> (מסיבות של יעילות רצוי ש-<math>g</math> תהיה השארית מחילוק ב-<math>b</math> אם <math>b=2^k</math>, אין צורך לבצע חילוק בפועל אלא נוטלים את <math>k</math> הסיביות הפחות משמעותיות של האלמנט). בוחרים שני אלמנטים <math>m</math> ו-<math>n</math> מתוך <math>Z_p</math> כאשר <math>m\ne0</math>. אז הפונקציה <math>h_{m,n}(x)=((mx+n)\text{ mod }p)\text{ mod }b</math> היא אוניברסלית.
 
כדי להימנע מפעולת הצמצום המודלורי שהיא פעולה לא יעילה במונחי מיחשוב אפשר לבצע את הטריק הבא: אם <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> מתקיים:
כדי להימנע מצמצום מודולי שהוא פעולה יחסית איטית במחשב, 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> אוניברסלית.
:<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)>p</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> אוניברסלית.
 
<!-- לדוגמה, בהינתן ראשוני <math>p</math> הגדול מ-<math>N</math> והמחלקה <math>\mathcal{H}</math> שממפה ערכים מ-<math>\{0,1,...,p-1\}</math> ל-<math>\{0,1,...,N-1\}</math> שמכילה עבור כל <math>a\in \{0,1,...,p-1\}</math> את הפונקציה: