פונקציית גיבוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←שימושים: הפניה לערך מורחב |
←שימושים: הוספת נקודה בין משפטים |
||
שורה 36:
כלומר ההסתברות שתהיה התנגשות (שהפונקציה <math>h</math> תמפה שני ערכים לאותה כניסה) נמוכה או שווה ל-<math>1/N</math> וכן אומרים שהפונקציה <math>h</math> 'כמעט אוניברסלית' אם היא מקיימת <math>\textstyle \Pr[h(x)=h(y)]\le \frac{2}{N}</math>.
לדוגמה אם נתונה קבוצה <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>
היא פונקציית גיבוב אוניברסלית.
| |||