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

אלגוריתם תחשיב האינדקסים (Index calculus) הוא השיטה הידועה הטובה ביותר לחישוב לוגריתמים בדידיים בחבורות אריתמטיות מסוימות. שיטה זו לא ישימה בכל סוגי החבורות, אולם כאשר היא מתאימה, יעילותה תת-מעריכית. אף שבעיית הלוגריתם הבדיד ניתנת לניסוח בכל חבורה, לצורך הפשטות האלגוריתם מתואר כאן במסגרת הכללית של חבורה ציקלית כדלהלן: בהינתן החבורה הציקלית $\ G$ מסדר $\ n$ והאלמנטים $\ \alpha ,\beta \in G$, כאשר $\ \alpha$ הוא יוצר של $\ G$, מצא את השלם $\ y$ המקיים $\ \beta =\alpha ^{y}$. במקרה זה מסמנים $\ y={\mbox{log}}_{\alpha }\beta \,({\mbox{mod }}n)$. ניתן ליישם את האלגוריתם במספר חבורות הנפוצות בשימוש ביישומים מעשיים, כמו בחבורה $\ Z_{p}^{*}$ (החבורה הכפלית מודולו $\ p$ ראשוני) וכן החבורה הכפלית של השדה הסופי $\ \mathbb {F} _{2^{m}}$.

תיאור האלגוריתם

אלגוריתם Index calculus זקוק לתת-קבוצה $\ S$ קטנה ככל האפשר של אלמנטים ב-$\ G$, הנקראים גורמי בסיס (Factor base) שהם: השלם $\ -1$ וכן הראשוניים הקטנים החל מ-2 עד לגבול מסוים. מהיבט של יעילות רצוי שקבוצת גורמי הבסיס תהיה קטנה ככל האפשר, אולם בחישוב לוגריתמים גדולים קבוצה זו עלולה שלא להספיק. מבחינה מעשית קיים קונפליקט בין גודל $\ S$ לבין הרצון להגיע לביצועים מרביים. בשלב הראשון אוספים מספר גדול ככל האפשר של יחסי שוויון ליניאריים (באופן כזה שניתן לייצגם ביעילות בעזרת גורמים בקבוצה $\ S$). משנאספו די יחסים, מחשבים את הלוגריתמים של כל גורמי הבסיס, מידע זה נחוץ בשלב השני לחישוב לוגריתמים של אלמנטים בחבורה $\ G$. בשלב זה מנסים להכפיל את $\ \beta$ באלמנטים מאוסף היחסים באופן שניתן לייצוג כמכפלה של גורמי הבסיס (או חזקות שלהם), אם נמצא צירוף מתאים ניתן לחשב את $\ y$ בקלות, בפעולות אלגבריות פשוטות.

האלגוריתם

קלט: יוצר $\ \alpha$ של החבורה הציקלית $\ G$ מסדר $\ n$ והאלמנט $\ \beta \in G$.

פלט: הלוגריתם הבדיד $\ y={\mbox{log}}_{\alpha }\beta$.

1. בחירת קבוצת גורמי בסיס.

בוחרים תת-קבוצה של $\ t$ מספרים ראשוניים: $\ S=\left\{p_{1},p_{2},...,p_{t}\right\}$ כאשר ערכו של $\ t$ נקבע באופן כזה שחלק נכבד מהאלמנטים ב-$\ G$ יהיו ניתנים לייצוג ככפולה של גורמי בסיס $\ p_{i}$ מתוך $\ S$.

2. איסוף יחסים ליניאריים בעזרת לוגריתמים של אלמנטים ב-$\ S$.

2.1 בוחרים אלמנט אקראי $\ k$, כך ש-$\ 0\geq k\geq n-1$, ומחשבים את $\ \alpha ^{k}$.

2.2 מנסים לייצג את $\ \alpha ^{k}$ כמכפלה של אלמנטים ב-$\ S$:

$\ \alpha ^{k}=\prod _{i=1}^{t}p_{i}^{c_{i}}$, כאשר $\ (1)\qquad \qquad c_{i}\geq 0$

אם ניסיון זה עלה יפה, מחשבים את הלוגריתם של שני צידי משוואה (1) כדי לקבל יחס ליניארי מהצורה:

$\ (2)\qquad k\equiv \sum _{i=1}^{t}c_{i}{\mbox{ log}}_{\alpha }\,p_{i}\quad ({\mbox{mod }}n)$

2.3 חוזרים על שלבים 2.1 ו-2.2 כדי לאסוף $\ t+c$ יחסי שוויון המקיימים את משוואה (2). $\ c$ הוא שלם קטן, הנבחר באופן כזה שלמערכת של $\ t+c$ המשוואות יהיה פתרון יחיד, בסבירות גבוהה.

3. חישוב לוגריתמים של אלמנטים ב-$\ S$:

כאשר כל הפעולות מתבצעות מודולו $\ n$, פותרים את המערכת הליניארית של $\ t+c$ המשוואות (עם $\ t$ נעלמים) מהצורה של משוואה (2) שנאספו, כדי לקבל את הפתרון של $\ {\mbox{log}}_{\alpha }\,p_{i}$, כאשר $\ 1\geq i\geq t$.

4. חישוב $\ {\mbox{log}}_{\alpha }\beta$.

4.1 בוחרים שלם אקראי $\ k$ כך ש-$\ 0\geq k\geq n-1$, ומחשבים את $\ \beta \cdot \alpha ^{k}$.

4.2 מנסים לייצג את $\ \beta \cdot \alpha ^{k}$ כמכפלה של אלמנטים מתוך $\ S$:

$\ \beta \cdot \alpha ^{k}=\prod _{i=1}^{t}p_{i}^{d_{i}}$, כאשר $\ (3)\qquad d_{i}\geq 0$

אם ניסיון זה לא הצליח, חוזרים על שלב 4.1 עם $\ k$ אחר. אחרת מחשבים את הלוגריתם של שני צידי משוואה (3) ומחזירים את:

$\ {\mbox{log}}_{\alpha }\beta =(\sum _{i=1}^{t}d_{i}{\mbox{ log}}_{\alpha }\,p_{i}-k){\mbox{ mod }}n$.

יעילות

כאמור זמן הריצה של האלגוריתם תלוי בגודל $\ t$ של קבוצת גורמי הבסיס. הבחירה האופטימלית מתבססת על התפלגות המספרים החלקים (smooth numbers) בטווח $\ [1,p-1]$ במקרה של $\ Z_{p}^{*}$. והתפלגות הפולינומים החלקים (smooth polinomials) מעל $\ F_{2}[x]$ שהם ממעלה הנמוכה מ-$\ m$ במקרה של $\ \mathbb {F} _{2^{m}}$. פולינום נקרא חלק אם הגורמים שאינם ניתנים לצמצום (ראשוניים) המרכיבים אותו, הם ממעלה קטנה יחסית. אם $\ t$ נבחר באופן אופטימלי, אלגוריתם Index calculus מעל $\ Z_{p}^{*}$ ו-$\ \mathbb {F} _{2^{m}}$ מגיע לזמן ריצה של $\ L_{q}[1/2,c]$ כאשר $\ q=p$ או $\ 2^{m}$ בהתאמה, $\ c$ קבוע הגדול מאפס.

ישנן שתי גרסאות של האלגוריתם עם זמן ריצה אופטימלי. עבור $\ F_{2^{m}}$, אלגוריתם Coppersmith עם זמן ריצה של $\ L_{2^{m}}[1/3,c]$ עם קבוע $\ c>1.587$. עבור $\ Z_{p}^{*}$ ישנה גרסה של Index calculus הנקראת number field sieve, עם זמן ריצה של $\ L_{p}[1/3,1.923]$. קיימים כיום שיפורים נוספים.

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

ראו גם

• נפה ריבועית
• נפת שדה מספרים