אלגוריתם רו של פולרד ללוגריתם הבדיד – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ פונצקיית -> פונקציית, ניסוח |
|||
שורה 3:
==היסטוריה==
[[קובץ:Rho shape-01.png|300px|ממוזער|שמאל|צורת האות היוונית "רו" של מיפוי אקראי]]
אלגוריתם רו הומצא על ידי המתמטיקאי הבריטי [[ג'ון פולרד]] והתפרסם במאמר "שיטת מונטה קרלו לחישוב אינדקסים" ב[[כתב עת מדעי|כתב העת המדעי]] "Mathematics of Computation" ביולי 1978{{הערה|Pollard, J. M. (1978). [https://pdfs.semanticscholar.org/e164/b11488ba143de0ee94887db924a0574d2361.pdf Monte Carlo methods for index computation (mod p)]. "Mathematics of Computation" . 32 (143): 918–924}}. בדומה ל[[אלגוריתם רו של פולרד]] ל[[פירוק לגורמים]] הוא נקרא בשם זה בשל העובדה שב[[מיפוי אקראי]] (או [[הילוך מקרי]]) בקבוצה סופית, נוצר מעין "מעגל" אליו מחובר "שובל" קצר וצורתו דומה במקצת לאות [[אלפבית יווני|היוונית]] [[רו|<math>\rho</math>]] (כמתואר בתרשים משמאל), כלומר בהינתן פונקציה אקראית לאחר מספר מוגבל של ערכים מגיעים לנקודה בה הערכים מתחילים לחזור על עצמם במעגל אין סופי. הרעיון של פולרד ניתן להרחבה לכל סוג של חבורה ציקלית, כמו [[חבורה אבלית]] מעל [[הצפנה מבוססת עקום אליפטי|עקום אליפטי]] הידועה בפופולריות שלה בהצפנה המודרנית ולמעשה לא ידוע על אלגוריתם שמציג סיבוכיות טובה יותר לפתרון בעיית הלוגריתם הבדיד בעקום אליפטי. בחבורה ציקלית מעל מספר ראשוני קיים אלגוריתם [[תחשיב אינדקסים]] עם זמן ריצה [[סיבוכיות|תת-מעריכי]] והוא נחשב ליעיל ביותר הידוע כיום למספרים גדולים אך אינו בר ביצוע בעקום אליפטי.
ב-1980 פיתח ריצ'רד ברנט גרסה משופרת יותר של אלגוריתם רו של פולרד לפירוק לגורמים שניתן ליישום גם לפתרון בעיית הלוגריתם הבדיד ומציע שיפור בפקטור של רבע ביעילותו לעומת הגרסה של פולרד{{הערה|Brent, Richard P. (1980), [http://maths-people.anu.edu.au/~brent/pub/pub051.html "An Improved Monte Carlo Factorization Algorithm"], BIT, 20: 176–184}}. מאוחר יותר פולרד וברנט פיתחו ושיפרו את האלגוריתם אף יותר{{הערה|Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (2001). [http://cacr.uwaterloo.ca/hac/about/chap3.pdf "Chapter 3 - Number-Theoretic Reference Problems"] (PDF). "Handbook of Applied Cryptography".}}.
| |||