Index calculus

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

אלגוריתם 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 \ge k \ge n-1$ , ומחשבים את $\ \alpha^k$ .

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

$\ \alpha^k = \prod_{i=1}^t p_i^{c_i}$ , כאשר $\ (1) \qquad \qquad c_i \ge 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 \ge i \ge t$ .

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

4.1 בוחרים שלם אקראי $\ k$ כך ש- $\ 0 \ge k \ge 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 \ge 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. עבודה זו ניתנת לחלוקה בין מספר מעבדים או מחשבים במקביל.