אלגוריתם רו של פולרד ללוגריתם הבדיד
בעיית הלוגריתם הבדיד

ביטחון מערכות הצפנה מודרניות רבות מסתמך על ההשערה שקשה לפתור את בעיית הלוגריתם הבדיד (דיסקרטי) בחבורות מסוימות. בהסתמך על בעיה זו ניתן להכין פונקציה חד-כיוונית שהיא הבסיס להצפנה אסימטרית. הדוגמאות אולי החשובות ביותר הן פרוטוקול דיפי-הלמן וחתימה דיגיטלית DSA הפופולריים שמסתמכים על השערה זו, למרות שלא קיימת הוכחה מתמטית.
בעיית הלוגריתם הבדיד המסומנת בקיצור DLP היא כדלקמן:
בעיית דיפי-הלמן בקיצור DHP, היא בעיה דומה שהועלתה לראשונה על ידי ויטפילד דיפי ומרטין הלמן במאמר המפורסם שלהם שבו הציגו לראשונה את הצפנת מפתח ציבורי ופרוטוקול שיתוף מפתח המבוסס על הבעיה הבאה: נתון המספר הראשוני  p ויוצר  \alpha  של החבורה  \mathbb {Z} _{p}^{*} וכן נתונים  \alpha ^{x} ו- \alpha ^{y} (מודולו  p). מצא את  \alpha ^{xy} מודולו  p. בעיה זו נחשבת גם היא לבעיה קשה אם כי לא הוכח האם היא קשה לפחות כבעיית הלוגריתם הבדיד. מאידך, כל דרך לפתרון בעיית הלוגריתם הדיקסרטי יכולה לשמש לפתרון בעיית דיפי-הלמן.
לדוגמה אם נתון המספר הראשוני  p=97 החבורה  \mathbb {Z} _{97}^{*} היא חבורה ציקלית מסדר  n=96. יוצר אפשרי אחד של חבורה זו יכול להיות  \alpha =5. (קל לראות שאם מעלים את 5 בחזקת כל המספרים מ-1 עד 96 (מודולו 97) מתקבלים כל האלמנטים של החבורה בלי יוצא מן הכלל לא בהכרח לפי סדר עולה). אם נבחר  x=32 בחשבון פשוט מתקבל  5^{32}\equiv 35{\text{ (mod }}97) לכן  \log _{5}35=32 בחבורה  \mathbb {Z} _{97}^{*}. וכן, אם  y=17 אז  5^{17}\equiv 83{\text{ (mod }}97). אם נתונים האלמנטים  5^{32}\equiv 35 ו- 5^{17}\equiv 83 (מודולו 97) בעיית דיפי-הלמן היא לגלות את  5^{32\cdot 17}\equiv 61{\text{ (mod }}97) (כשהאלמנטים  x ו- y אינם ידועים).
הבעיה נקראת לוגריתם בדיד כיוון שהיא עוסקת בקבוצה סופית מודולו שלם כלשהו הנקרא מודולוס. ראוי לציין שאף-על-פי שקל לחשב לוגריתמים באופן כללי, אין הדבר נכון לגבי לוגריתם בדיד מכיוון שהתנהגות התוצאה נראית אקראית על פניה ולא ניתן לבצע קירוב. הסיבה שהבסיס הוא יוצר היא כדי שהחבורה תהיה ציקלית כך שכל אלמנט בחבורה ניתן לייצוג כחזקה של היוצר. הדרישה שהחבורה תהיה ציקלית אינה הכרחית, הגדרה כללית יותר של הבעיה, הנקראת בקיצור GDLP, היא מציאת אלמנט  x המקיים  \alpha ^{x}=\beta , בהנחה שקיים, עבור האלמנטים  \alpha ,\beta \in G (כאשר  \alpha  אינו בהכרח יוצר). החבורה החיבורית הנוצרת על ידי עקום אליפטי כאשר הפעולה היא חיבור נקודות בעקום היא דוגמה לחבורה שבה בעיית הלוגריתם הבדיד קשה. אחת הדרכים לפתור את הבעיה היא בעצם חישוב איזומורפיזם בין חבורות. אפילו אם שתי חבורות איזומורפיות זו לזו, אלגוריתם יעיל לפתרון בעיית הלוגריתם הבדיד בחבורה אחת, אינו בהכרח יעיל בחבורה השנייה. למשל כל חבורה כפלית ציקלית מסדר  n איזומורפית לחבורה החיבורית הציקלית  \mathbb {Z} _{n}. על כל פנים, בעוד שקיים אלגוריתם יעיל לחישוב לוגריתמים בחבורה החיבורית מעל המספרים השלמים מודולו מספר ראשוני, כלומר מציאת שלם המקיים  ax\equiv b{\text{ (mod }}n), לא ניתן ליישמו לפתרון הלוגריתם הבדיד בחבורה הכפלית.
הדרך הישירה והפשוטה ביותר לפתרון בעיית הלוגריתם הבדיד היא שיטת כוח גס, סריקת כל החזקות של  \alpha  בזה אחר זה מ-1 עד  n עד שמתקבל  \beta  וסיבוכיותה היא מסדר גודל  O(n). היא אינה יעילה מהיבט קריפטוגרפי כיוון שאם  n גדול (נניח באורך  n\geq 2^{128} סיביות) התקפה כזו אינה פרקטית. שיטה מעט יותר טובה נקראת "צעד-קטן צעד-גדול" והיא מבוססת על העובדה שאם  \beta =\alpha ^{x} אפשר לכתוב את  x בצורה:  x=im+j (לפי כלל החילוק המודולרי) כאשר  j<m ו- m=\left\lceil {\sqrt {n}}\right\rceil . לכן  \alpha ^{x}=\alpha ^{im}\alpha ^{j} לאחר העברת אגפים מתקבל  \beta (\alpha ^{-m})^{i}=\alpha ^{j}. מהאמור עולה שאם מכינים טבלה המכילה את הזוגות ( j,\alpha ^{j}) עבור כל המספרים מ-1 עד  m, הממויינת לפי האלמנט השני, מובטח שיימצא אלמנט אחד (אם קיים פתרון) השווה ל- \beta (\alpha ^{-m})^{i}. היות שהטבלה היא בסדר גודל של השורש הריבועי של סדר החבורה וחיפוש בטבלה ממויינת אינו קשה, יוצא שסיבוכיות השיטה היא  O({\sqrt {n}}) אך היא דורשת סיבוכיות מקום בסדר גודל של  O({\sqrt {n}}) ועל כן אם  n גדול מאוד (נניח  n\geq 2^{128}) היא אינה פרקטית.