אלגוריתם רו של פולרד ללוגריתם הדיסקרטי – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
שורה 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".}}.