תחשיב אינדקסים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
מ הנו מיותר, קו מפריד בטווח מספרים |
||
שורה 3:
==תיאור האלגוריתם==
אלגוריתם Index calculus זקוק ל[[תת קבוצה|תת-קבוצה]] <math>\ S</math> קטנה ככל האפשר של אלמנטים ב-<math>\ G</math>, הנקראים '''גורמי בסיס''' (Factor base) שהם: השלם <math>\ -1</math> וכן הראשוניים הקטנים החל מ-2 עד לגבול מסוים. מהיבט של יעילות רצוי שקבוצת גורמי הבסיס תהיה קטנה ככל האפשר, אולם בחישוב לוגריתמים גדולים קבוצה זו עלולה שלא להספיק. מבחינה מעשית קיים קונפליקט בין גודל <math>\ S</math> לבין הרצון להגיע לביצועים מרביים. בשלב הראשון אוספים מספר גדול ככל האפשר של [[שוויון|יחסי שוויון]] [[ליניארי
==האלגוריתם==
שורה 14:
:2. ''איסוף יחסים ליניאריים בעזרת לוגריתמים של אלמנטים ב-<math>\ S</math>''.
::2.1
::2.2
:::<math>\ \alpha^k = \prod_{i=1}^t p_i^{c_i}</math>, כאשר <math>\ (1) \qquad \qquad c_i \ge 0</math>
::אם ניסיון זה עלה יפה, מחשבים את הלוגריתם של שני צידי ''משוואה (1)'' כדי לקבל יחס ליניארי מהצורה:
:::<math>\ (2) \qquad k \equiv \sum_{i=1}^t
::2.3
:3. ''חישוב לוגריתמים של אלמנטים ב-<math>\ S</math>'':
שורה 25:
:4. ''חישוב <math>\ \mbox{log}_{\alpha} \beta</math>''.
::4.1
::4.2
:::<math>\ \beta \cdot \alpha^k = \prod_{i=1}^t p_i^{d_i}</math>, כאשר <math>\ (3) \qquad d_i \ge 0</math>
::אם ניסיון זה לא הצליח, חוזרים על שלב 4.1 עם <math>\ k</math> אחר. אחרת מחשבים את הלוגריתם של שני צידי ''משוואה (3)'' ומחזירים את:
:::<math>\ \mbox{log}_{\alpha} \beta = (\sum_{i=1}^t d_i \mbox{ log}_{\alpha} \, p_i-k) \mbox{ mod } n</math>.
שורה 37:
ישנן שתי גרסאות של האלגוריתם עם זמן ריצה אופטימלי. עבור <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 ניתן להרצה באופן מקבילי, חלק הארי של פעילות האלגוריתם מתמקד
== ראו גם ==
* [[נפה ריבועית]]
* [[נפת שדה מספרים]]
|