Pada tahun 1971, matematikawan Amerika Daniel Shanks menerbitkan sebuah metode untuk sebuah masalah yang tidak ada hubungannya dengan uang digital. Idenya cukup sederhana untuk dijelaskan dalam satu paragraf dan cukup baik untuk bertahan setengah abad: alih-alih menempuh seluruh perjalanan dari satu ujung, tempuh setengah dari setiap ujung dan bertemu di tengah.
Masalahnya, di sini, adalah dari pelajaran sebelumnya dalam versi yang menguntungkan: kunci publik Q diketahui, diketahui bahwa nilainya adalah k kali G, dan diketahui bahwa k berada di antara nol dan N. Menemukan k dengan kekuatan brute force akan memakan biaya N langkah. Metode Shanks memakan biaya sekitar dua kali akar dari N.
Triknya adalah menulis k dengan cara yang berbeda. Sebut m sebagai akar kuadrat dari N, dibulatkan ke atas. Setiap angka antara nol dan N dapat ditulis sebagai i kali m ditambah j, dengan i dan j lebih kecil dari m — ini adalah dekomposisi yang sama yang Anda lakukan saat mengatakan bahwa 47 adalah empat puluhan dan tujuh satuan, hanya saja dengan m menggantikan sepuluh.
Menggantikan dalam persamaan, Q sama dengan i kali m ditambah j, semuanya dikalikan dengan G. Pindahkan j ke sisi lain: Q dikurangi j kali G sama dengan i kali titik m kali G. Perhatikan apa yang terjadi. Di sisi kiri hanya ada hal-hal yang bergantung pada j; di sisi kanan, hanya hal-hal yang bergantung pada i. Kedua sisi telah dipisahkan.
Dari sinilah nama itu berasal. Langkah-langkah bayi adalah m nilai dari sisi kiri: hitung Q dikurangi j kali G untuk setiap j, dan simpan setiap hasil dalam tabel. Langkah-langkah raksasa adalah m nilai dari sisi kanan: hitung i kali titik mG, untuk setiap i, dan cari setiap satu di tabel. Ketika sebuah nilai cocok, i dan j yang sesuai mengungkapkan k, karena k adalah i kali m ditambah j.
Dalam bit, penghematannya jelas. Sebuah interval tujuh puluh bit memiliki 2^69 kandidat, dan akar kuadratnya adalah sekitar 2^34,5 — sedikit lebih dari dua puluh empat miliar langkah di setiap sisi. Sebuah mesin yang melakukan beberapa miliar operasi per detik dapat menyelesaikan ini dalam hitungan menit, bukan milenium.
Namun, perhitungan di atas adalah untuk waktu, dan metode ini membebankan biaya dalam mata uang lain. Tabel langkah-langkah bayi harus ada sepenuhnya sebelum langkah-langkah raksasa dimulai. Ada dua puluh empat miliar entri, dan setiap entri menyimpan setidaknya sebagian dari koordinat titik dan nilai j — sekitar tiga puluh byte per baris, dengan perkiraan yang murah hati. Ini mendekati tujuh ratus lima puluh gigabyte memori, untuk interval tujuh puluh bit.
Dan memori tumbuh dengan akar yang sama seperti waktu. Delapan puluh bit memerlukan sekitar dua puluh empat terabyte; sembilan puluh memerlukan hampir delapan ratus. Menyimpan ini di disk alih-alih memori tidak menyelesaikan masalah, karena setiap langkah raksasa melakukan pencarian ke alamat yang tidak terduga, dan disk tidak menyukai akses acak: metode ini tidak lagi dibatasi oleh perhitungan dan menjadi dibatasi oleh waktu pencarian.
Ada versi yang mengurangi tabel dengan hanya menyimpan sebagian dari setiap titik dan menerima untuk memeriksa positif palsu setelahnya. Mereka membantu dengan faktor konstan dan tidak mengubah sifat masalah: langkah bayi dan langkah raksasa adalah metode yang menukar memori dengan waktu, dan pertukaran ini memiliki batas fisik yang cepat tercapai.
Untuk menghindari batas ini, dicari jalan lain — yang memerlukan akar kuadrat yang sama dalam waktu dan hampir tidak memerlukan memori. Metode ini ada, memiliki nama hewan, dan merupakan algoritma yang telah mengatasi tantangan terbesar yang pernah diselesaikan. Pada pelajaran berikutnya, kanguru Pollard.