תחשיב אינדקסים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 36:
::ואז מחשבים את <math>\ y</math>:
:::<math>\ y = (\sum_{i=1}^t d_i \mbox{ log}_{\alpha} p_i-k) \mbox{ mod } n</math>
==יעילות==
כאמור זמן הריצה של האלגוריתם תלוי בגודל t של קבוצת גורמי הבסיס. הבחירה האופטימלית מתבססת על התפלגות [[מספר חלק|המספרים החלקים]] (smooth) בטווח <math>\ [1, p-1]</math> במקרה של <math>\ Z^*_p</math>. והתפלגות [[פולינום חלק|הפולינומים החלקים]] (smooth polinomials) מעל <math>\ F_2[x]</math> שהם ממעלה הנמוכה מ-<math>\ m</math> במקרה של <math>\ \mathbb{F}_{2^m}</math>. פולינום נקרא חלק אם הגורמים שאינם ניתנים לצמצום (ראשוניים) המרכיבים אותו, הם ממעלה קטנה יחסית. אם <math>\ t</math> נבחר באופן אופטימלי, אלגוריתם Index calculus מעל <math>\ Z^*_p</math> ו-<math>\ \mathbb{F}_{2^m}</math> מגיע לזמן ריצה של <math>\ L_q[1/2, c]</math> כאשר <math>\ q = p</math> או <math>\ 2^m</math> בהתאמה, <math>\ c</math> קבוע הגדול מאפס.
ישנם שני גרסאות לאוגוריתם עם זמן ריצה אופטימלי. עבור <math>\ F_{2^m}</math>, אלגוריתם Coppersmith עם זמן ריצה של <math>\ L_{2^m}[1/3,c]</math> עם קבוע <math>\ c > 1.587</math>. עבור <math>\ Z^*_p</math> ישנה גרסה של Index calculus הנקראת number field sieve, עם זמן ריצה של <math>\ L_p[1/3, 1.923]</math>. קיימים כיום שיפורים נוספים.
אלגוריתם Index calculus ניתן להרצה באופן מקבילי, חלק הארי של פעילות האלגוריתם מתמקד במציאת הרלציות בשלב 2. עבודה זו ניתן לחלק בין מספר מחשבים במקביל.
[[קטגוריה:תורת החבורות]]
| |||