Modular Arithmetic কি সেটা জানার জন্য এই লিঙ্কে দেখে আসি।
আলোচনার শুরুতে কিছু জিনিস ক্লিয়ার করা উচিত...
১) "%" এই চিহ্ন দিয়ে সি,সি++,জাভা সহ বেশিরভাগ ল্যাংগুয়েজে ভাগশেষ অপারেটর বুঝায়।
উদাঃ
5 % 2 = 1
5 % (-2) = 1
(-5) % 2 = -1
(-5) % (-2) = -1
এই গুলো code লিখে নিজে নিজে চেক করে নিই।
২) "mod" ও ভাগশেষই প্রকাশ করে কিন্তু একটু সমস্যা আছে , সমস্যাটা হল যদি X mod m করি এবং m>0 তাহলে এর result কখনই 0 ≤ m ≤ m-1 এর বাইরে কোনো মান হবে না।
উদাঃ
5 mod 2 = 1
(-5) mod 2 = 1 (not -1)
অতএব, mod 2 = {0 , 1}
mod 3 = {0 , 1 , 2}
mod n = {0 , 1 , 2 , ... , n-1}
৩) a ≡ b (mod m)
উদাঃ
5 ≡ 2 (mod 3)
5 mod 3 = 2 and 2 mod 3 = 2
এখানে চিত্রে সংখ্যারেখা দিয়ে দেখানো হল। -2, 2, 5 এদের জন্য (mod 3) এর মান 2 ।
৪) a ≡ b (mod m) হলে আমরা ab ≡ 1 (mod m) ... কেন?? এর উত্তর পাবার জন্য নিজে ট্রাই করি ওই সংখ্যারেখার মাধ্যমে...
5*2 ≡ 1 (mod 3) , এখানে আমরা আরেকটা কথা বলে রাখি , 5 হল (2 mod 3) এর Modular Multiplicative Inverse। এর ব্যাখ্যা নিচে দেওয়া আছে আপাতত মনে রাখি।
৫) X mod m = R হলে , X = q*m + R ; এখানে , q যেকোনো একটি সংখ্যা।
উদাঃ
5 mod 2 = 1
5 = 2*2 + 1 ; where , q = 2, m = 2 and R = 1.
এখন আমাদের কাজ হবে কোনো সংখ্যা দিলেই অইটা mod দিয়ে কেটে ছোট করে দেওয়া। :P
এখন তোমার অনেক পাজি একটা ছোট ভাই আছে। সে একদিন বলল- "ভাইয়া, তুমি নাকি বড় কোনো সংখ্যাকে কেটে ছোট করতে পার?" তুমি কিঞ্চিত হাসি দিয়ে বললা- "হ্যা,পারি।(মনে মনে ভাবতেছো আমি করবো নাকি রে পাগলা এটা তো আমার কম্পিউটার করে দিবে...মুহা হা হা...)" তারপর তোমাকে সে 2^50 mod 4 বের করে দিতে বলল। এখন তোমার মুখ শুকিয়ে গেল...এতো বড়টা ছোট করবো কেম্নে?(-_-)
এখানেই আসবে Big MOD এর concept । :D
আমি এই বেপারে কিছুই বলবো না কারণ এর উপর শাফায়েত ভাই যা লিখছে তারপর এর উপর কিছু বলার থাকে না।
এখানেই লিঙ্ক দেওয়া হল। এরপর আরেকটা জিনিস থেকে যায় তা হচ্ছে যদি সংখ্যা power অথবা গুণ আকারে না থেকে ডিরেক্ট 10^18 এর চাইতে বড় দেয় তখন কিভাবে mod করবো। এটার solutionও এই লিঙ্কে আছে। :D
আমার আর কোনো কাজ নাই শুধু লিঙ্ক দিয়ে বেড়াইতেছি। (-_-)
একটা কাজ পাইছি !! Modular Multiplicative Inverse নিয়ে বকবক করতে পারবো... :P
আগে দেখে নিই এটা কেনো লাগবে। - এটা লাগবে মূলত তুমি যখন a/b mod m বের করতে যাবা।
কারণ, a*b mod m এর জন্য সূত্র আছে(শাফায়েত ভাই এর ব্লগে দেখ) কিন্তু a/b এর জন্য তেমন কোনো সূত্র নাই।
তুমি যখন Combination করতে গিয়ে n! / ((n-r)! * r!) এর মান বের করতে যাবা তখন সমস্যায় পরবা। n এর মান ছোট হইলে সমস্যা নাই কিন্তু প্রব্লেম গুলাতে n এর মান ছোট দেয় না, বরং অনেক বড় মান দিয়ে সেটা m (কোন একটা সংখ্যা) দিয়ে mod করতে বলা হয়। যেহেতু a/b mod m এর জন্য কোনো সূত্র নাই তাই তোমাকে একটা পথ খুজে বের করতে হবে এইটা করার জন্য। এর জন্য তোমার জানা লাগবে Fermat's little theorem নামে একটা theorem . এই theorem অনুযায়ী ,
যদি p একটি প্রাইম নাম্বার, a যেকোন integer হয় এবং a যদি p দিয়ে বিভাজ্য না হয়, তাহলে লিখা যায়,
2^(17-1) ≡ 1 (mod 17)
or, 2^16 ≡ 1 (mod 17) --- (1)
Now, 2^50 = 2^(16 * 3 + 2) [ 50 = 16 * 3 +2 , উপরের ৫ নং থেকে প্রাপ্ত ]
= (2^16)^3 * 2^2
আলোচনার শুরুতে কিছু জিনিস ক্লিয়ার করা উচিত...
১) "%" এই চিহ্ন দিয়ে সি,সি++,জাভা সহ বেশিরভাগ ল্যাংগুয়েজে ভাগশেষ অপারেটর বুঝায়।
উদাঃ
5 % 2 = 1
5 % (-2) = 1
(-5) % 2 = -1
(-5) % (-2) = -1
এই গুলো code লিখে নিজে নিজে চেক করে নিই।
২) "mod" ও ভাগশেষই প্রকাশ করে কিন্তু একটু সমস্যা আছে , সমস্যাটা হল যদি X mod m করি এবং m>0 তাহলে এর result কখনই 0 ≤ m ≤ m-1 এর বাইরে কোনো মান হবে না।
উদাঃ
5 mod 2 = 1
(-5) mod 2 = 1 (not -1)
অতএব, mod 2 = {0 , 1}
mod 3 = {0 , 1 , 2}
mod n = {0 , 1 , 2 , ... , n-1}
৩) a ≡ b (mod m)
উদাঃ
5 ≡ 2 (mod 3)
5 mod 3 = 2 and 2 mod 3 = 2
এখানে চিত্রে সংখ্যারেখা দিয়ে দেখানো হল। -2, 2, 5 এদের জন্য (mod 3) এর মান 2 ।
৪) a ≡ b (mod m) হলে আমরা ab ≡ 1 (mod m) ... কেন?? এর উত্তর পাবার জন্য নিজে ট্রাই করি ওই সংখ্যারেখার মাধ্যমে...
5*2 ≡ 1 (mod 3) , এখানে আমরা আরেকটা কথা বলে রাখি , 5 হল (2 mod 3) এর Modular Multiplicative Inverse। এর ব্যাখ্যা নিচে দেওয়া আছে আপাতত মনে রাখি।
৫) X mod m = R হলে , X = q*m + R ; এখানে , q যেকোনো একটি সংখ্যা।
উদাঃ
5 mod 2 = 1
5 = 2*2 + 1 ; where , q = 2, m = 2 and R = 1.
এখন আমাদের কাজ হবে কোনো সংখ্যা দিলেই অইটা mod দিয়ে কেটে ছোট করে দেওয়া। :P
এখন তোমার অনেক পাজি একটা ছোট ভাই আছে। সে একদিন বলল- "ভাইয়া, তুমি নাকি বড় কোনো সংখ্যাকে কেটে ছোট করতে পার?" তুমি কিঞ্চিত হাসি দিয়ে বললা- "হ্যা,পারি।(মনে মনে ভাবতেছো আমি করবো নাকি রে পাগলা এটা তো আমার কম্পিউটার করে দিবে...মুহা হা হা...)" তারপর তোমাকে সে 2^50 mod 4 বের করে দিতে বলল। এখন তোমার মুখ শুকিয়ে গেল...এতো বড়টা ছোট করবো কেম্নে?(-_-)
এখানেই আসবে Big MOD এর concept । :D
আমি এই বেপারে কিছুই বলবো না কারণ এর উপর শাফায়েত ভাই যা লিখছে তারপর এর উপর কিছু বলার থাকে না।
এখানেই লিঙ্ক দেওয়া হল। এরপর আরেকটা জিনিস থেকে যায় তা হচ্ছে যদি সংখ্যা power অথবা গুণ আকারে না থেকে ডিরেক্ট 10^18 এর চাইতে বড় দেয় তখন কিভাবে mod করবো। এটার solutionও এই লিঙ্কে আছে। :D
আমার আর কোনো কাজ নাই শুধু লিঙ্ক দিয়ে বেড়াইতেছি। (-_-)
একটা কাজ পাইছি !! Modular Multiplicative Inverse নিয়ে বকবক করতে পারবো... :P
আগে দেখে নিই এটা কেনো লাগবে। - এটা লাগবে মূলত তুমি যখন a/b mod m বের করতে যাবা।
কারণ, a*b mod m এর জন্য সূত্র আছে(শাফায়েত ভাই এর ব্লগে দেখ) কিন্তু a/b এর জন্য তেমন কোনো সূত্র নাই।
তুমি যখন Combination করতে গিয়ে n! / ((n-r)! * r!) এর মান বের করতে যাবা তখন সমস্যায় পরবা। n এর মান ছোট হইলে সমস্যা নাই কিন্তু প্রব্লেম গুলাতে n এর মান ছোট দেয় না, বরং অনেক বড় মান দিয়ে সেটা m (কোন একটা সংখ্যা) দিয়ে mod করতে বলা হয়। যেহেতু a/b mod m এর জন্য কোনো সূত্র নাই তাই তোমাকে একটা পথ খুজে বের করতে হবে এইটা করার জন্য। এর জন্য তোমার জানা লাগবে Fermat's little theorem নামে একটা theorem . এই theorem অনুযায়ী ,
যদি p একটি প্রাইম নাম্বার, a যেকোন integer হয় এবং a যদি p দিয়ে বিভাজ্য না হয়, তাহলে লিখা যায়,
a^(p-1) ≡ 1 (mod p)
উদাঃ2^(17-1) ≡ 1 (mod 17)
or, 2^16 ≡ 1 (mod 17) --- (1)
Now, 2^50 = 2^(16 * 3 + 2) [ 50 = 16 * 3 +2 , উপরের ৫ নং থেকে প্রাপ্ত ]
= (2^16)^3 * 2^2
≡ (1)^3 * 4 (mod 17) [From eqn (1) ]
so,2^50 ≡ 4 (mod 17)
সুতরাং, উক্ত theorem টা ১০০ ভাগ খাটি। :D
আমরা a^(p-1) ≡ 1 (mod p)
= a * a^(p-2) ≡ 1 (mod p) , ও লিখতে পারি ।
এখন দেখ এই সমীকরণটি উপরের ৪ নং এর সমীকরণের সাথে মিলে। অর্থাৎ, আমরা বলতে পারি, a এর
Modular Multiplicative Inverse হচ্ছে a^(p-2)।
এখনই হয়ত অনেকে বুঝে গেছে বাকি কি কাজ করতে হবে। যারা বুঝি নাই তারা একটু খেয়াল করি উক্ত সমীকরণটি , যদি আমাকে (a/b)%m বের করতে বলে, আমাকে (b mod m) এর Modular Multiplicative Inverse বের
করতে হবে। অর্থাৎ , BigMOD(b, m-2, m) ফাংশনটি কল করলেই খেলা শেষ। :D
এই ফাংশন আমাকে যা রিটার্ন করবে, তাই হচ্ছে Modular Multiplicative Inverse of (b mod m)।
উক্ত ধারণার উপর প্রব্লেমঃ
374 - Big Mod
10127 - Ones
1067 - Combinations
1054 - Efficient Pseudo Code
DCP-23: Another Bigmod Problem
No comments:
Post a Comment