תחשיב אינדקסים – הבדלי גרסאות

כאמור זמן הריצה של האלגוריתם תלוי בגודל <math>\ t</math> של קבוצת גורמי הבסיס. הבחירה האופטימלית מתבססת על התפלגות [[מספר חלק|המספרים החלקים]] (smooth numbers) בטווח <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> קבוע הגדול מאפס.

 

 

אלגוריתם Index calculus ניתן להרצה באופן מקבילי, חלק הארי של פעילות האלגוריתם מתמקד במציאת יחסים לינאריים בשלב 2. עבודה זו ניתנת לחלוקה בין מספר מעבדים או מחשבים במקביל.