תחשיב אינדקסים

אלגוריתם תחשיב האינדקסים (Index calculus) הוא השיטה היעילה הידועה לחישוב לוגריתם בדידי בחבורות אריתמטיות מתאימות. לוגריתם בדידי אומר: נתונה חבורה ציקלית (קבוצה שבה אלמנט אחד מייצר את כולם) G מסדר n, יוצר α ואלמנט β ב‑G; מי המספר y כך ש‑β = α^y (מודול n).

השיטה מיושמת בחבורות כמו Z*_p (הכפל המודולו p ראשוני) ובחבורה הכפלית של שדה סופי F_{2^m}.

הרעיון המרכזי הוא לבחור קבוצה קטנה של "גורמי בסיס" (Factor base) S, מספרים קטנים, למשל פרים עד גבול מסוים. בוחרים הרבה חזקות אקראיות של α ומנסים לפרקן (לייצג) כמכפלה של גורמי הבסיס. כל פירוק מוצלח נותן יחס ליניארי בין החזקות:

k ≡ Σ c_i·log_α p_i (מודול n).

אוספים מספיק יחסים (כ־t+c משוואות עבור t גורמי בסיס) ואז פותרים מערכת ליניארית מודולו n כדי למצוא log_α p_i לכל p_i ב‑S. לאחר מכן מנסים למצוא k כך ש‑β·α^k יתפרק גם הוא על גורמי הבסיס; אם כן מחשבים

log_α β = (Σ d_i·log_α p_i − k) (מודול n).

אם הפירוק נכשל מנסים k אחרים. העבודה העיקרית היא מציאת היחסים, שניתן לחלק בקלות בין מחשבים.

זמן הריצה תלוי בגודל קבוצת גורמי הבסיס. עבור Z*_p ו‑F_{2^m} זמן הריצה הוא תת‑מעריכי מהצורה L_q[1/2,c] (כאשר q = p או 2^m). ישנן גרסאות מהירות יותר: אלגוריתם Coppersmith עבור F_{2^m} (זמן L[1/3,c]) וגרסת Number Field Sieve עבור Z*_p (L[1/3,1.923]). האלגוריתם ניתן להרצה מקבילית, כי שלב איסוף היחסים ניתן לחלוקה בין מעבדים.

תחשיב האינדקסים היא שיטה למציאת "לוגריתם בדידי". לוגריתם בדידי אומר כמה פעמים מרימים את המספר α בחזקה כדי לקבל את β. חבורה ציקלית היא קבוצה שבה אלמנט אחד מייצר את כל שאר האיברים על ידי חזקות.

המהלך קצר: בוחרים קבוצה קטנה של "גורמי בסיס". אלה הם מספרים קטנים שמשמשים כחלקים לבניית מספרים אחרים. מייצרים הרבה חזקות של α ומנסים לפרקן באמצעות גורמי הבסיס. כל פירוק נותן משוואה פשוטה שקושרת את החזקות.

אוספים מספיק משוואות ופותרים אותן כדי לדעת כמה שווה הלוגריתם של כל גורם בסיס. אז מנסים לפרק גם את β (או β כפול α^k) על אותם הבסיסים. אם זה מצליח, מחשבים את הלוגריתם של β בעזרת המספרים שמצאנו.

המהירות תלויה בגודל קבוצת גורמי הבסיס. העבודה הגדולה היא למצוא פירוקים, והיא ניתנת לחלוקה למחשבים רבים. יש גרסאות מהירות עוד יותר בשם Coppersmith ו‑Number Field Sieve.