אלגוריתם רו של פולרד ללוגריתם הבדיד – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 204:
===שיפורים===
בגלל הפופולריות של עקומים אליפטיים בקריפטוגרפיה, נעשה מאמץ לשפר את אלגוריתם רו של פולרד בין היתר על ידי [[עיבוד מקבילי]]. נניח שזמינים <math>M</math> מחשבים לצורך פתרון הבעיה. הדרך הנאיבית היא להריץ את האלגוריתם על כל מחשב בנפרד עם נקודות התחלה אקראיות שונות, עד שאחד מהם יגלה התנגשות. שיטה זו אינה מנצלת את פוטנציאל המקביליות כי השיפור בביצועים הוא בפקטור <math>\sqrt{M}</math> לכל היותר. פול ואן-אורשוט ומייקל ויינר הציעו גרסה מקבילית של אלגוריתם רו שמניבה שיפור בביצועים בפקטור של <math>M</math>{{הערה|Paul C. van Oorschot, Michael J. Wiener, [http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf "Parallel Collision Search with Cryptanalytic Applications"] Journal of Cryptology January 1999, Volume 12, Issue 1, pp 1–28}}. הרעיון הוא לאפשר לכל הסדרות <math>\{X_i\}_{i\ge 0}</math> של כל המעבדים להתנגש
אם הפרופורציה של הנקודות המובחנות ב-<math>\langle P\rangle</math> היא <math>\theta</math> הסיכויים לקבל התנגשות הם בערך <math>1/\theta</math> לכן מספר פעולות כפל נקודות בעקום הצפוי מכל מעבד עד שמתקבלת התנגשות אחת הוא
|