মূল বিষয়বস্তু
কোর্স: কম্পিউটার বিজ্ঞান > অধ্যায় 2
পাঠ 5: মডুলার পাটিগণিতদ্রুত সূচকীয় মডুলার
আমরা দ্রুত কীভাবে A^B mod C নির্ণয় করতে পারি যেখানে B এর ঘাত হল 2 ?
মডুলার গুণনের নিয়ম:
যেমন: A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
আমরা এটি ব্যবহার করে 7^256 mod 13 কে দ্রুত হিসাব করতে পারি
7^1 mod 13 = 7
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
এই সমীকরণে 7^1 mod 13 এর মান বসিয়ে পাই।
7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10
7^2 mod 13 = 10
7^2 mod 13 = 10
7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13
এই সমীকরণে 7^2 mod 13 এর মান বসিয়ে পাই।
7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
7^4 mod 13 = 9
7^4 mod 13 = 9
7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13
এই সমীকরণে 7^4 mod 13 এর মান বসিয়ে পাই।
7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3
7^8 mod 13 = 3
আমরা এভাবেই মানগুলো সমীকরণে বসাতে থাকি।
... 5 টি ধাপের পর আমরা পাই:
7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
এটি দিয়ে আমরা A^B mod C দ্রুত হিসাব করার একটি পদ্ধতি পাই যেখানে B এর ঘাত হল 2।
কিন্তু, আমাদের দ্রুত সূচকীয় মডুলারের জন্য আরেকটি পদ্ধতি দরকার যেখানে B এর ঘাত 2 নয়।
যেকোনো B এর জন্য আমরা কীভাবে দ্রুত A^B mod c নির্ণয় করতে পারি?
ধাপ 1: বাইনারিতে লেখার জন্য B কে 2 এর ঘাতে বিভক্ত কর
সব থেকে ডানের সংখ্যা নিয়ে শুরু কর, ধরি k=0 এবং সকল সংখ্যার জন্য:
- যদি সংখ্যাটি 1 হয়, তাহলে আমাদের 2^k এর একটি অংশ দরকার হবে, অন্যথায় নয়
- k এর সাথে 1 যোগ কর এবং বামদিকে পরের সংখ্যাটি নাও
ধাপ 2: দুইয়ের ঘাতের mod C হিসাব কর ≤ B
5^1 mod 19 = 5
5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
ধাপ 3: হিসাব করা mod C এর মানগুলো যোগ করার জন্য মডুলার গুণের বৈশিষ্ট্য ব্যবহার কর
5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
নোট:
আরও সরল করার পদ্ধতি রয়েছে, কিন্তু তা এই প্রবন্ধের আলোচনায় সম্ভব নয়। লক্ষ্য করা উচিত যে, ক্রিপ্টোগ্রাফিতে মডুলার সূচকীয় পদ্ধতি ব্যবহার করার সময়, ব্যবহৃত সূচক B > 1000 বিটস হতে পারে।
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।