ישנן מספר חבורות בהן בעיית הלוגריתם הבדיד ותאומה בעיית דיפי-הלמן קשות לפתרון. העדיפות היא לחבורה ציקלית מסדר ראשוני והסיבות הן ראשית משום שידוע שאם סדר החבורה אינו ראשוני אפשר לצמצם את בעיית הלוגריתם הבדיד לבעיה בתת-חבורות שלה שהן יותר קטנות ולכן הפתרון קל יותר. שנית, קל למצוא יוצר בחבורה מסדר ראשוני כי כל איברי החבורה הם יוצרים. בנוסף, קל יותר למצוא הופכי כפלי של מעריך כלשהו דבר שרצוי במבנים קריפטוגרפיים מסוימים ובעיקר הסיבה היא שזה הגיוני להשתמש בחבורה מסדר ראשוני כי אם הסדר ראשוני אפשר להוכיח שפלט הפונקציה formula_103 הוא כמעט אקראי בהשוואה להתפלגות אחידה מעל formula_8.
למרות זאת, החבורה הכפלית formula_127 עם ראשוני formula_128 נפוצה בישומים מעשיים למרות שסדר החבורה הזו אינו ראשוני. ההשערה היא שבעיית הלוגריתם הבדיד בחבורה זו קשה גם היא בתנאי שמשתמשים בתת-חבורה מתאימה של formula_127. האיבר formula_130 הוא שארית ריבועית מודולו formula_128 אם קיים איבר formula_132 המקיים formula_133. כך שקבוצת כל השאריות הריבועיות היא תת-חבורה של formula_127. מחצית מהאיברים של החבורה formula_127 הם שאריות ריבועיות מודולו formula_128. אם formula_128 הוא מספר ראשוני "חזק", כלומר formula_138 כאשר formula_29 ראשוני אז מספר האיברים בתת-החבורה המכילה את כל השאריות הריבועיות מודולו formula_128 הוא formula_141 והיות ש-formula_29 ראשוני תת-חבורה זו ציקלית. יתרה מזו כל האיברים בתת-חבורה זו הם יוצרים שלה. כדי למצוא יוצר, פשוט בוחרים איבר אקראי כלשהו formula_1 שהתנאי הוא שלא יהיה שקול ל-formula_144 (מודולו formula_128) ואז מציבים formula_146 מודולו formula_128.
דוגמה לבעיית דיפי-הלמן במספרים קטנים.
נתון הראשוני formula_148 החבורה הציקלית formula_149 מסדר formula_150 והיוצר formula_151. אם נבחר formula_152 וכן formula_153. אם נתונים האיברים formula_154 ו-formula_155 (מודולו 97), בעיית דיפי-הלמן היא לגלות את formula_156 (כאשר formula_1 ו-formula_47 לא ידועים), יש לשים לב שאת החזקה מצמצמים מודולו ההסדר של החבורה 96.
עקום אליפטי.
חבורה אחרת שבה ההשערה היא שבעיית הלוגריתם הבדיד קשה היא אוסף הנקודות על עקום אליפטי. היתרון שלו הוא שבניגוד לחבורה כפלית לא ידוע על אלגוריתם שמסוגל לפתור את בעיית הלוגריתם הבדיד בזמן ריצה תת-מעריכי בחבורת העקום האליפטי. בקצרה, יהי formula_159 מספר ראשוני ונתונה משוואה ממעלה שלישית formula_160 בשני נעלמים formula_1 ו-formula_47 מהצורה:
כאשר formula_164 הם קבועים המקיימים את התנאי formula_165 (תנאי זה הכרחי כדי להבטיח שלא יהיו בעקום קצוות חדים) נניח ש-formula_166 מייצג את כל הזוגות formula_167 המקיימים את המשוואה האמורה, אז העקום האליפטי הוא formula_168. במילים, אוסף כל הנקודות המקיימות את המשוואה האמורה עם נקודה מיוחדת הנקראת "הנקודה באין סוף" המסומנת ב-formula_169. קיים כלל חיבור מסובך שמאפשר לחבר שתי נקודות בעקום כדי לקבל נקודה שלישית שגם היא בעקום; formula_170 או חיבור נקודה בעצמה formula_171. למרבה ההפתעה אפשר להוכיח שקבוצת הנקודות בעקום formula_160 יחד עם כלל החיבור יוצרים חבורה אבלית. שהיא חבורה סגורה תחת כלל החיבור כשהנקודה באין סוף משמשת כאיבר יחידה. לכל נקודה יש נקודה הופכית וכן חוקי האסוציאטיביות והקומוטטיביות מתקיימים בה.
בעיית הלוגריתם הבדיד בעקום אליפטי היא כדלקמן. נתון עקום אליפטי formula_173 ונתונה נקודה כלשהי formula_174 הנקראת נקודת הבסיס וכן הנקודה formula_175 מצא שלם formula_176 המקיים formula_177. השלם formula_176 נקרא הלוגריתם הבדיד של הנקודה formula_179 בבסיס הנקודה formula_180 או בקיצור formula_181. הקבוצה formula_182 היא תת-חבורה ציקלית המכילה את אוסף כל הנקודות שהן כפולות של formula_180 כלומר formula_184 עד שמגיעים לנקודה באין סוף (נניח שנמצא שלם formula_185 כך שמתקיים formula_186) הנקודה formula_179 נמצאת אי שם בחבורה זו כאשר השלם formula_188 מייצג את מספר הפעמים שהיה צריך לחבר את הנקודה formula_180 כדי להגיע ל-formula_179:
האלגוריתם הטוב ביותר הידוע כיום לפתרון בעיית הלוגריתם הבדיד בעקום אליפטי (אם לא מביאים בחשבון אלגוריתם קוונטי) היא גרסה מקבילית של אלגוריתם רו של פולרד ללוגריתמים.
אלגוריתמים.
באופן כללי נתונה חבורה הציקלית formula_8 עם היוצר formula_2 והאיבר formula_194 הבעיה היא מציאת השלם formula_1 המקיים formula_196 (בתת-החבורה הנוצרת על ידי formula_2 או בחבורה formula_8 אם formula_2 הוא יוצר שלה), המסומנת בקיצור formula_200 מודולו הסדר של formula_2 שנקרא לעיתים הבסיס. אותה אפשר לפתור בכמה דרכים. הפתרון הנאיבי ביותר הוא שיטת כוח גס, כלומר אפשר לחשב את כל החזקות של formula_2 לפי סדר formula_203 עד שמתקבל formula_47. סיבוכיות הפתרון היא מסדר גודל formula_205. קיימים מספר אלגוריתמים שלהם סיבוכיות טובה יותר והם מתחלקים לשתי קטגוריות. אלגוריתם "גנרי" שפועל על כל חבורה ואלגוריתם שפועל רק על חבורה ספציפית. לצורך הדיון אפשר להתעלם מהחבורה formula_8 ולהתייחס ישירות לתת-החבורה formula_207 שהיא מסדר formula_29 שההנחה היא שהוא מספר ראשוני ידוע. להלן רשימת האלגוריתמים הידועים לפתרון בעיית הלוגריתם הבדיד וכן בעיית דיפי-הלמן.
אלגוריתם צעד-קטן צעד-גדול.
אלגוריתם צעד-קטן/צעד-גדול של דויד שנקס הוא אלגוריתם כוח גס רקורסיבי שעושה שימוש בזיכרון כדי לפתור את בעיית הלוגריתם הבדיד בחבורה ציקלית מסדר formula_29 בזמן ריצה של formula_218. הרעיון הוא פשוט. בהינתן תת-חבורה ציקלית formula_207 ואיבר formula_194, אפשר לדמיין את החבורה כמעגל של האיברים formula_221.
ידוע ש-formula_222 חייב להיות היכן שהוא בתוך המעגל, במקום לחשב ולאחסן בזיכרון את כל האיברים של המעגל עד שנמצא formula_1 שזה אינו מעשי, "מסמנים" נקודות במעגל במרווחים קבועים (או מדלגים במרחק קבוע) לפי formula_224. במילים אחרות מחשבים ומאחסנים בטבלה ממוינת בזיכרון את האיברים:
שלב זה נקרא "צעד-גדול". כעת היות ש-formula_226 נמצא באחד מהמרווחים, מובטח שאחד מ-formula_185 האיברים
יהיה שווה לאחת מהנקודות שאוחסנו בטבלה בזיכרון, שלב זה נקרא "צעד-קטן". נניח ש-formula_229 עבור formula_14 ו-formula_231 כלשהם, אפשר בקלות לפתור את הלוגריתם על ידי formula_232 או formula_233.
האלגוריתם דורש formula_210 העלאות בחזקה בחבורה formula_8, כל פעולה כזו מתבצעת בזמן של formula_236 פעולות בסיסיות, אם משתמשים באלגוריתם יעיל לחישוב חזקות בחבורה. אך יש צורך לאחסן בזיכרון formula_237 איברים בערך. למעשה ברקורסיה, למעט האיבר הראשון לחישוב כל איבר נדרשת פעולת כפל אחת: formula_238 באופן דומה כל formula_239 ניתן לחישוב כ-formula_240. מיון ניתן לביצוע בזמן של formula_241 וחיפוש בינארי מתבצע בזמן של formula_242.
פירוט מהלכי האלגוריתם.
קלט: תת-חבורה formula_10, האיבר formula_194 וסדר החבורה formula_29.
פלט: formula_200.
דוגמה במספרים קטנים.
בחבורה formula_259 מסדר formula_260, אם formula_261 ו-formula_153 כדי לחשב את הלוגריתם הבדיד של 17 בבסיס 2 תחילה מחשבים את formula_263 ואז מכינים טבלה עם זוגות הערכים הבאים (מודולו 29) ממוינת לפי הערך השני:
ואז מחשבים את הערכים הבאים עם המונה formula_264:
בחיפוש מהיר מסתבר שהערך האחרון שהתקבל זהה למעשה לכניסה הרביעית בטבלה לכן formula_266 מודולו 29.
לוגריתם בדיד בקריפטוגרפיה.
בלוגריתם בדיד, בדומה לפירוק לגורמים, ישנן שתי פעולות הופכיות שאינן סימטריות בכוח החישוב הדרוש לביצוען. לדוגמה, כפל ופירוק לגורמים הם פעולות הפוכות, בעוד שכפל היא פעולה קלה במונחי מחשוב, הרי שפירוק לגורמים קשה הרבה יותר ממנה. כן הדבר בלוגריתמים, העלאה בחזקה מודולרית (מודולו שלם formula_85) קלה הרבה יותר ממציאת החזקה מודולו formula_85. חוסר הסימטריה הזה נקרא פונקציה חד-כיוונית, והיא מנוצלת היטב בעיקר בהצפנה אסימטרית. דוגמאות הן: פרוטוקול דיפי-הלמן להעברת מפתח, צופן אל-גמאל, חתימה דיגיטלית של אל-גמאל ואלגוריתם חתימה דיגיטלית DSA.
כדי להתמודד עם האיום של האלגוריתמים המנויים לעיל, ההנחה היא כיום שראשוני formula_128 בגודל 2048 סיביות מספק מרווח ביטחון סביר. תקן DSA מגדיר למשל מספר רמות אבטחה לאלגוריתם חתימה דיגיטלית כשהמרבית היא, p ראשוני בסדר גודל של 3072 סיביות.
החבורות שיש בהן עניין מבחינה קריפטוגרפית הן; החבורה הכפלית formula_270 מעל שדה ראשוני גדול, החבורה הכפלית formula_271 מעל שדה סופי מורחב formula_272 כאשר formula_273 ו-formula_274 וכן החבורה הכפלית formula_275 מעל שדה בינארי formula_276 עם מציין 2. כן יש עניין מיוחד בחבורה formula_277 כאשר formula_278 שלם פריק, קבוצת הנקודות בעקום אליפטי המוגדר מעל שדה סופי ועקום היפר-אליפטי מעל שדה סופי.
מרכז אירופה
מרכז אירופה הוא כינוי קיבוצי לקבוצת מדינות באירופה, השוכנות בין מזרח אירופה למערב אירופה. במהלך המלחמה הקרה, שחילקה את אירופה למזרח ולמערב, חולק מרכז אירופה לשני צידי מסך הברזל.
מדינות מרכז אירופה הן:
סה"כ מספר התושבים במדינות מרכז אירופה הוא כ-160 מיליון איש. השטח של האזור הוא למעלה ממיליון קמ"ר.
ויקימינים