Reading Time: 1 minute

অ্যালগরিদম টি দেখার আগে আমরা একটা সমস্যা দেখব ।

সমস্যাঃ মনে করো, তোমাকে বলা হল 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 নিলে অপর পাশে তার কমপ্লিমেন্টারি জিনিসগুলো এসে সব কম্বিনেশন ফীল আপ করে ।