অ্যালগরিদম টি দেখার আগে আমরা একটা সমস্যা দেখব ।
সমস্যাঃ মনে করো, তোমাকে বলা হল a^x = b (mod n) এই সমীকরণটি দেয়া আছে । তোমাকে a,b এবং n দেয়া আছে । তোমাকে বলতে হবে x এর কোন মানের জন্য সমীকরণটি সত্য হয় ।
এই সমস্যাটি মূলত একটি Discrete Logarithm প্রবলেম । এই সমস্যা সমাধানের একটা অ্যাপ্রোচ হলো বেবি স্টেপ জায়ান্ট স্টেপ অ্যালগরিদম । অ্যালগরিদম টি এরকম
১. প্রথমে আমরা ইচ্ছামতো যে কোন ইচ্ছামতো একটা k এর মান চুজ করি ।
২. এখন আমরা ১ থেকে শুরু করে k পর্যন্ত ( 1<=i<=k-1) পর্যন্ত a ^ i (mod n) বার করি এবং লিস্টে সেভ করে রাখি ।
৩. এখন আমরা b * a^(-1),ba^(-k) %mod n, b * a ^(-2k) % mod n , b * a ^ (-3 * k) %mod n ……… , b * a^(-r * k) % mod n (যেখানে r * k > n)
এখন যদি আমাদের প্রবলেমের কোন সমাধান থাকে তাহলে অবশ্যই ২ এবং ৩ নম্বর লাইনে যেই মানগুলো পাওয়া গেছে তাদের মধ্যে অন্তত একটি মান হলেও কমন থাকবে ।
এখন মনে করি , a^r [ লাইন নাম্বার ২ থেকে] = b * a ^ (-mk) % (mod n) [ লাইন নাম্বার 3 থেকে] হলো , তাহলে এখন দেখি কি করা যায় ।
a^r = b * a ^(-mk) % (mod n)
=> a ^ (r+mk) = b % (mod n)
তাহলে x = r + mk এটাই আমাদের প্রবলেম এর একটা সলিউশন ।
এক্সামপ্লঃ আমাদের সমাধান করতে হবে 3^x = 9 .(mod 10^9+7)
আমরা মনে করি আমরা ধরলাম k = 4 [ k ইচ্ছামতো ধরা যায় ]
এখন n = 10^9 + 7
এখন, 3 = 3 (mod n)
3^2 = 9 (mod n)
3^3 = 27 (mod n)
তাহলে 3 নাম্বার স্টেপ ।
9 * 3 ^ (-1) = 3 (mod n);
9 * 3 ^ (-4) = 9 * 123456791 (mod n) = 111111112
9 * 3 ^( -8) = 9 * 137326628 (mod n) = 235939645
9 * 3 ^ (12) = 9 * 693053420 ( mod n) = 237480738
…… আমরা ইচ্ছা করের পরের ধাপ গুলা দেখিয়েছি । মূলত প্রথম ৩ নাম্বার স্টেপ এর প্রথমটাতেই আমাদের ডিজায়ার্ড মান চলে আসছে ।
so 3 ^ (1) = 9* 3 ^(-1) mod n
3^2 = 9 mod (n)
এটাই হলো আমাদের প্রবলেমটির সমাধান ।
পাদটীকাঃ
এটা কেনো কাজ করে ?
দেখি, a^x = b
=> a ^ (p) = b ^ a^(-q)
তাহলে আমাদের কাজ আসলে a^p আর b * a ^(-q) যাতে সমান হয় এমন কোন একটা কিছু বার করা । এজন্যই এই সমাধান কাজ করে । আর যে কোন k এর মানের কেনো হয় । কারণ আমাদের কাজ শুধু অলটাইপ কম্বিনেশন বার করা । যে কোন পর্যন্ত k নিলে অপর পাশে তার কমপ্লিমেন্টারি জিনিসগুলো এসে সব কম্বিনেশন ফীল আপ করে ।