ב-1971, המתמטיקאי האמריקאי דניאל שנקס פרסם שיטה לבעיה שלא הייתה קשורה כלל לכסף דיגיטלי. הרעיון היה פשוט מספיק כדי להיכנס לפסקה אחת וטוב מספיק כדי לשרוד חצי מאה: במקום לעבור את כל הדרך מקצה אחד, עוברים חצי מכל קצה ונפגשים באמצע.
הבעיה כאן היא זו מהשיעור הקודם בגרסה המועדפת: המפתח הציבורי Q ידוע, ידוע שהוא שווה ל-k פעמים G, וידוע ש-k נמצא בין אפס ל-N. למצוא את k בכוח גס יעלה N צעדים. השיטה של שנקס עולה בערך פי שניים מהשורש של N.
הטריק הוא לכתוב את k בצורה שונה. נקרא ל-m השורש הריבועי של N, מעוגל כלפי מעלה. כל מספר בין אפס ל-N ניתן לכתיבה כ-i כפול m ועוד j, כאשר i ו-j קטנים מ-m — זו אותה פירוק שאתה עושה כשאתה אומר ש-47 הוא ארבע עשרות ושבע יחידות, רק עם m במקום עשר.
מחליפים במשוואה, Q שווה ל-i כפול m ועוד j, הכל מוכפל ב-G. מעבירים את j לצד השני: Q פחות j כפול G שווה ל-i כפול הנקודה m כפול G. שים לב למה שקרה. בצד השמאלי יש רק דברים שתלויים ב-j; בצד הימני, רק דברים שתלויים ב-i. שני הצדדים הופרדו.
מכאן מגיע השם. הצעדים הקטנים הם ה-m ערכים של הצד השמאלי: מחשבים Q פחות j כפול G עבור כל j, ושומרים כל תוצאה בטבלה. הצעדים הגדולים הם ה-m ערכים של הצד הימני: מחשבים i כפול הנקודה mG, עבור כל i, ולכל אחד מחפשים בטבלה. כשערך מתאים, ה-i וה-j המתאימים חושפים את k, כי k הוא i כפול m ועוד j.
בביטים, החיסכון ברור. טווח של שבעים ביטים מכיל 2^69 מועמדים, והשורש הריבועי של זה הוא משהו בסביבות 2^34.5 — קצת יותר מעשרים וארבעה מיליארד צעדים מכל צד. מכונה שמבצעת כמה מיליארדי פעולות בשנייה עוברת את זה בדקות, לא באלפי שנים.
אבל החישוב לעיל הוא של הזמן, והשיטה גובה במטבע אחר. הטבלה של הצעדים הקטנים צריכה להתקיים כולה לפני שהצעדים הגדולים מתחילים. ישנם עשרים וארבעה מיליארד ערכים, וכל ערך שומר לפחות חלק מהקואורדינטה של הנקודה ואת הערך של j — משהו כמו שלושים בייט לשורה, אם נהיה נדיבים. זה יוצא קרוב לשבע מאות וחמישים ג'יגהבייט של זיכרון, עבור טווח של שבעים ביטים.
והזיכרון גדל באותו שורש כמו הזמן. שמונים ביטים דורשים כעשרים וארבעה טרהבייט; תשעים דורשים כמעט שמונה מאות. לשמור את זה בדיסק במקום בזיכרון לא פותר את הבעיה, כי כל צעד גדול מבצע חיפוש לכתובת בלתי צפויה, ודיסק לא אוהב גישה אקראית: השיטה מפסיקה להיות מוגבלת על ידי החישוב ומתחילה להיות מוגבלת על ידי זמן החיפוש.
יש גרסאות שמפחיתות את הטבלה על ידי שמירה רק של חלק מכל נקודה וקבלת בדיקה של חיוביים שגויים לאחר מכן. הן עוזרות על ידי גורם קבוע ולא משנות את טבע הבעיה: צעד קטן וצעד גדול היא שיטה שמחליפה זיכרון בזמן, וההחלפה הזו יש לה גבול פיזי שמגיע מהר.
כדי להימלט בדיוק מהגבול הזה חיפשו דרך אחרת — אחת שעולה את אותו שורש ריבועי בזמן וכמעט כלום בזיכרון. היא קיימת, יש לה שם של חיה והיא האלגוריתם שהפיל את האתגרים הגדולים ביותר שנפתרו אי פעם. בשיעור הבא, הקנגורואים של פולארד.