War Thunder, בהיותו משחק שבראשית דרכו התמקד בכלים של מלחמת העולם השנייה וכלל את כלי המדינות אשר השתתפו, כולל גם מספר כלים השייכים לבעלות ברית של אותן מדינות, או מדינות קשורות כגון: ישנם כמה כלים פינים במשחק המיוצגים על ידי מדינות קרובות אליה או בעלות קשר היסטורי, גרמניה ושוודיה, כך גם כלים אוסטרלים מיוצגים תחת הדגל הבריטי וכלים ישראלים מיוצגים תחת דגל צרפת, בריטניה וארצות הברית, תלוי במקור הכלי.
רשימת מדינות.
לדוגמאות:
אלגוריתם רו של פולרד ללוגריתם הדיסקרטי
בתורת המספרים ובקריפטוגרפיה, אלגוריתם רו של פולרד ללוגריתם הדיסקרטי (באנגלית: Pollard’s rho algorithm for discrete logarithms) הוא אלגוריתם הסתברותי לחישוב לוגריתם בדיד בחבורה ציקלית סופית מסדר ראשוני עם זמן ריצה דומה לשיטת כוח גס גנרית הנקראת אלגוריתם צעד-קטן צעד-גדול אך עם צריכת זיכרון שולית ביחס אליה. האלגוריתם פותר את בעיית הלוגריתם הבדיד בהסתברות גבוהה, בסיבוכיות בסדר גודל של formula_1 כאשר formula_2 הוא סדר החבורה. לצורך אלגוריתם פולרד ההנחה היא שסדר החבורה הוא מספר ראשוני, שאם לא כן, אפשר בשילוב עם אלגוריתם פוליג-הלמן לפתור את בעיית הלוגריתם הבדיד בזמן ריצה שהוא בסדר גודל formula_3 כאשר formula_4 הוא הגורם הראשוני הגדול ביותר של formula_2.
היסטוריה.
אלגוריתם רו הומצא על ידי המתמטיקאי הבריטי ג'ון פולרד והתפרסם במאמר "שיטת מונטה קרלו לחישוב אינדקסים" בכתב העת המדעי "Mathematics of Computation" ביולי 1978. בדומה לאלגוריתם רו של פולרד לפירוק לגורמים הוא נקרא בשם זה בשל העובדה שבמיפוי אקראי (או הילוך מקרי) בקבוצה סופית, נוצר מעין "מעגל" אליו מחובר "שובל" קצר וצורתו דומה במקצת לאות היוונית formula_6 (כמתואר בתרשים משמאל), כלומר בהינתן פונקציה אקראית לאחר מספר מוגבל של ערכים מגיעים לנקודה בה הערכים מתחילים לחזור על עצמם במעגל אין סופי. הרעיון של פולרד ניתן להרחבה לכל סוג של חבורה ציקלית, כמו חבורה אבלית מעל עקום אליפטי הידועה בפופולריות שלה בהצפנה המודרנית ולמעשה לא ידוע על אלגוריתם שמציג סיבוכיות טובה יותר לפתרון בעיית הלוגריתם הבדיד בעקום אליפטי. בחבורה ציקלית מעל מספר ראשוני קיים אלגוריתם תחשיב אינדקסים עם זמן ריצה תת-מעריכי והוא נחשב ליעיל ביותר הידוע כיום למספרים גדולים אך אינו בר ביצוע בעקום אליפטי.
ב-1980 פיתח ריצ'רד ברנט גרסה משופרת יותר של אלגוריתם רו של פולרד לפירוק לגורמים שניתן ליישום גם לפתרון בעיית הלוגריתם הבדיד ומציע שיפור בפקטור של רבע ביעילותו לעומת הגרסה של פולרד. מאוחר יותר פולרד וברנט פיתחו ושיפרו את האלגוריתם אף יותר.
בעיית הלוגריתם הבדיד.
ביטחון מערכות הצפנה מודרניות רבות מסתמך על ההשערה שקשה לפתור את בעיית הלוגריתם הבדיד (דיסקרטי) בחבורות מסוימות. בהסתמך על בעיה זו ניתן להכין פונקציה חד-כיוונית שהיא הבסיס להצפנה אסימטרית. הדוגמאות אולי החשובות ביותר הן פרוטוקול דיפי-הלמן וחתימה דיגיטלית DSA הפופולריים שמסתמכים על השערה זו, למרות שלא קיימת הוכחה מתמטית.
בעיית הלוגריתם הבדיד המסומנת בקיצור DLP היא כדלקמן:
בעיית דיפי-הלמן בקיצור DHP, היא בעיה דומה שהועלתה לראשונה על ידי ויטפילד דיפי ומרטין הלמן במאמר המפורסם שלהם שבו הציגו לראשונה את הצפנת מפתח ציבורי ופרוטוקול שיתוף מפתח המבוסס על הבעיה הבאה: נתון המספר הראשוני formula_4 ויוצר formula_8 של החבורה formula_9 וכן נתונים formula_10 ו-formula_11 (מודולו formula_4). מצא את formula_13 מודולו formula_4. בעיה זו נחשבת גם היא לבעיה קשה אם כי לא הוכח האם היא קשה לפחות כבעיית הלוגריתם הבדיד. מאידך, כל דרך לפתרון בעיית הלוגריתם הדיקסרטי יכולה לשמש לפתרון בעיית דיפי-הלמן.
לדוגמה אם נתון המספר הראשוני formula_15 החבורה formula_16 היא חבורה ציקלית מסדר formula_17. יוצר אפשרי אחד של חבורה זו יכול להיות formula_18. (קל לראות שאם מעלים את 5 בחזקת כל המספרים מ-1 עד 96 (מודולו 97) מתקבלים כל האלמנטים של החבורה בלי יוצא מן הכלל לא בהכרח לפי סדר עולה). אם נבחר formula_19 בחשבון פשוט מתקבל formula_20 לכן formula_21 בחבורה formula_16. וכן, אם formula_23 אז formula_24. אם נתונים האלמנטים formula_25 ו-formula_26 (מודולו 97) בעיית דיפי-הלמן היא לגלות את formula_27 (כשהאלמנטים formula_28 ו-formula_29 אינם ידועים).
הבעיה נקראת לוגריתם בדיד כיוון שהיא עוסקת בקבוצה סופית מודולו שלם כלשהו הנקרא מודולוס. ראוי לציין שאף-על-פי שקל לחשב לוגריתמים באופן כללי, אין הדבר נכון לגבי לוגריתם בדיד מכיוון שהתנהגות התוצאה נראית אקראית על פניה ולא ניתן לבצע קירוב. הסיבה שהבסיס הוא יוצר היא כדי שהחבורה תהיה ציקלית כך שכל אלמנט בחבורה ניתן לייצוג כחזקה של היוצר. הדרישה שהחבורה תהיה ציקלית אינה הכרחית, הגדרה כללית יותר של הבעיה, הנקראת בקיצור GDLP, היא מציאת אלמנט formula_28 המקיים formula_31, בהנחה שקיים, עבור האלמנטים formula_32 (כאשר formula_8 אינו בהכרח יוצר). החבורה החיבורית הנוצרת על ידי עקום אליפטי כאשר הפעולה היא חיבור נקודות בעקום היא דוגמה לחבורה שבה בעיית הלוגריתם הבדיד קשה. אחת הדרכים לפתור את הבעיה היא בעצם חישוב איזומורפיזם בין חבורות. אפילו אם שתי חבורות איזומורפיות זו לזו, אלגוריתם יעיל לפתרון בעיית הלוגריתם הבדיד בחבורה אחת, אינו בהכרח יעיל בחבורה השנייה. למשל כל חבורה כפלית ציקלית מסדר formula_2 איזומורפית לחבורה החיבורית הציקלית formula_35. על כל פנים, בעוד שקיים אלגוריתם יעיל לחישוב לוגריתמים בחבורה החיבורית מעל המספרים השלמים מודולו מספר ראשוני, כלומר מציאת שלם המקיים formula_36, לא ניתן ליישמו לפתרון הלוגריתם הבדיד בחבורה הכפלית.
הדרך הישירה והפשוטה ביותר לפתרון בעיית הלוגריתם הבדיד היא שיטת כוח גס, סריקת כל החזקות של formula_8 בזה אחר זה מ-1 עד formula_2 עד שמתקבל formula_39 וסיבוכיותה היא מסדר גודל formula_40. היא אינה יעילה מהיבט קריפטוגרפי כיוון שאם formula_2 גדול (נניח באורך formula_42 סיביות) התקפה כזו אינה פרקטית. שיטה מעט יותר טובה נקראת "צעד-קטן צעד-גדול" והיא מבוססת על העובדה שאם formula_43 אפשר לכתוב את formula_28 בצורה: formula_45 (לפי כלל החילוק המודולרי) כאשר formula_46 ו-formula_47. לכן formula_48 לאחר העברת אגפים מתקבל formula_49. מהאמור עולה שאם מכינים טבלה המכילה את הזוגות (formula_50) עבור כל המספרים מ-1 עד formula_51, הממויינת לפי האלמנט השני, מובטח שיימצא אלמנט אחד (אם קיים פתרון) השווה ל-formula_52. היות שהטבלה היא בסדר גודל של השורש הריבועי של סדר החבורה וחיפוש בטבלה ממויינת אינו קשה, יוצא שסיבוכיות השיטה היא formula_1 אך היא דורשת סיבוכיות מקום בסדר גודל של formula_1 ועל כן אם formula_2 גדול מאוד (נניח formula_42) היא אינה פרקטית.
תיאור כללי.
אלגוריתם רו של פולרד מנסה לייצר "סדרה פסידו-אקראית" של אלמנטים מהחבורה בהתבסס על רעיון מונטה קרלו וחיפוש אחר התנגשויות, כלומר שני אלמנטים זהים בסדרה. אם נמצאה התנגשות הדבר מוביל לפתרון בעיית הלוגריתם הבדיד בהסתברות גבוהה. שני רעיונות מרכזיים של פולרד הם פונקציה איטרטיבית אקראית קלה לחישוב, איתה מכינים את הסדרה הפסאודו-אקראית ואלגוריתם מציאת מחזוריות שמנסה למצוא בה התנגשות בזמן הקצר ביותר ללא שימוש בטבלאות. לצורך הפשטות נניח שנתונה חבורה ציקלית formula_57 מסדר formula_2 ראשוני.
תחילה מחלקים את formula_57 לשלוש קבוצות בגודל זהה בקירוב formula_60, בחלוקה לוגית בהתבסס על כלל מנחה קל לבדיקה. אפשר למשל לחלק לפי משקלו של כל אלמנט באופן הבא הקבוצה formula_61 תכיל את כל האלמנטים: formula_62, הקבוצה formula_63 את האלמנטים formula_64 והשלישית formula_65. דרך אחרת יותר יעילה היא לחלק לפי הערך של formula_66 הסיביות הכי פחות משמעותיות של כל formula_67 כאשר formula_66 תלוי במספר החלוקות (במקרה זה מספיק לבחון את שתי הסיביות האחרונות). מספר החלוקות שרירותי וניתן לשינוי, אך יש צורך לשים לב לכמה היבטים חשובים בנוגע לחלוקה למשל formula_69.
מחשבים סדרה פסידו-אקראית של אלמנטים מהחבורה לפי הכלל הבא. בוחרים אלמנט התחלתי formula_70 ועבור כל formula_71 מחשבים:
בנוסף מתוך הסדרה האמורה מכינים שתי רשימות של שלמים formula_73 וכן formula_74 כאשר formula_75 ו-formula_76 ועבור כל formula_71 מחשבים את
וכן
הערכים של formula_80 ו-formula_81 מחושבים כך שעבור כל formula_82 מתקיים formula_83. אם formula_84 כאשר formula_85 זה אומר שנמצאה "התנגשות". כדי למצוא התנגשות ביעילות האלגוריתם מנצל טכניקה המיוחסת לרוברט פלויד (לפי דונלד קנות') שנקראת מציאת מחזוריות או "שיטת הצב והארנב" שהיא שיטה יעילה לאיתור מחזוריות של פונקציה איטרטיבית אקראית על עצמה מהצורה formula_86. מנסים באופן רקורסיבי לאתר את הנקודה בה הסדרה מתחילה לחזור על עצמה. מבצעים בכל איטרציה שתי הליכות, הליכה איטית והליכה מהירה. בהליכה איטית מחשבים מתוך הערכים מהאיטרציה הקודמת את השלשה החדשה (formula_87) ובהליכה מהירה את formula_88 ומשווים בין formula_67 ל-formula_90, אם הם שווים אותרה מחזוריות הפונקציה וזה אומר שמנקודה זו ואילך המסלול יחזור על עצמו במעגל אין סופי. סיבוכיות הטכניקה הזו זהה לשיטה הישירה המסתמכת על חיפוש בטבלאות ומבזבזת זיכרון רב. אם נמצאה התאמה המשמעות היא ש-formula_91 ולכן formula_92. אם לוקחים לוגריתם בבסיס formula_8 של שני האגפים במשוואה האחרונה מתקבל