মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
কোর্স: কম্পিউটার বিজ্ঞান > অধ্যায় 2
পাঠ 6: মৌলিক সংখ্যা যাচাই- ভূমিকা
- মৌলিক সংখ্যা যাচাই সংক্রান্ত চ্যালেঞ্জ
- ট্রায়েল ডিভিশন
- কম্পিউটার মেমোরি কি?
- অ্যালগোরিদমিক কর্মক্ষমতা
- লেভেল 3: চ্যালেঞ্জ
- সিয়েভ অফ ইরাটোসথেন্স
- লেভেল 4: সিয়েভ অফ ইরাটোসথেন্স
- সিয়েভ ব্যবহার করে মৌলিক সংখ্যা যাচাই পরীক্ষা
- লেভেল 5: সিয়েভ ব্যবহার করে ট্রায়েল ডিভিশন
- মৌলিক সংখ্যার তত্ত্ব
- মৌলিক সংখ্যার ঘনত্ব সংক্রান্ত চক্র
- মৌলিক সংখ্যার মধ্যে থাকা ফাঁকা স্থান
- স্থান কালের ট্রেডঅফ
- সার-সংক্ষেপ (এরপরে কি?)
© 2023 Khan Academyব্যবহারের শর্তাদিগোপনীয়তার নীতিমালাকুকি নোটিশ
সার-সংক্ষেপ (এরপরে কি?)
উৎপাদকে বিশ্লেষণ করা কেন কঠিন একটি কাজ, অথচ মৌলিক সংখ্যা তৈরি করা সহজ? আমরা এখান থেকে কোথায় যেতে পারি? এটি তৈরি করেছে ব্রিট ক্রুজ
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।
ভিডিও ট্রান্সক্রিপ্ট
## আগামী ও গ্রামীণফোন এর সহযোগিতায় অনূদিত ## অভিনন্দন আমরা শিক্ষণীয় ভিডিওতে বিভিন্ন বিষয়ের জেনেছি বেশ কিছু নতুন বিষয়ে পরিচিত হয়েছি তাই অন্য বিষয়ে মনোযোগ দেয়ার, আগে এখানে আমাদের গুরুত্ব দেয়া উচিত এখন এই অনুশীলনীটিতে শেখার কি আছে? বেশ, আমরা RSA সাংকেতিকরণ সম্পর্কে জেনেছি এবং RSA দুটি বিষয়ের উপর নির্ভর করে এক, মৌলিক উৎপাদক বিশ্লেষণ করা কঠিন। তাহলে যদি দুটি বড় মৌলিক সংখ্যা গুন করি, P1 এবং P2 এবং আমি তোমাকে N দিচ্ছি, আমি বিশ্বাস করতে পারি যে, এই মৌলিক সংখ্যাগুলো খুঁজে পেতে তোমার অনেক সময় লাগবে হয়ত তোমার সারাজীবন লেগে যাবে । এবং দুই, RSA এর সেই বড় মৌলিক সংখ্যা প্রয়োজন যা আমি সহজে পেয়েছিলাম, মানে হল আমি একটি বড় মৌলিক সংখ্যা সহজেই পেতে পারি তাহলে চল, প্রথম সমস্যায় ফিরে যাই মৌলিক সংখ্যার উৎপাদকে বিশ্লেষণে সমস্যা বেশ, মৌলিক সংখ্যার উৎপাদকে বিশ্লেষণে কি সমস্যা? বা মৌলিক সংখ্যা কেন একে জটিল ? এটা খুঁজে পেতে একটি সমস্যা নিয়ে শুরু করি। X দেয়া আছে, X মৌলিক বা যৌগিক সংখ্যা, এখন আমরা এই সমস্যার জন্য কিছু সমাধান পেলাম এবং তা করতে গিয়ে, আমরা বুঝতে পারলাম যে এই সমস্যাটি কম্পিউটারের গণনার ক্ষেত্রে ব্যয়বহুল তা হল, এই সমস্যার কোন সমাধান নেই। যখন আমাদের ইনপুট সংখ্যা বৃদ্ধি পাবে, সমাধানের সময় বা এলগরিদমের ধাপ সংখ্যা ও বৃদ্ধি পাবে। এবং এটা কত বৃদ্ধি পাবে? এখনি এটা বোঝা উচিত, কারণ মৌলিক সংখ্যা উপপাদ্য দিয়েও এটা নির্ণয় করা যায় যদিও আসলে এটা লেখ চিত্রের মাধ্যমে চিন্তা করা যেত। যেখানে উলম্ব অক্ষে আমাদের এলগরিদম ধাপের সংখ্যা আছে তাহলে তুমি একে শুধু সময় হিসেবে দেখতে পার এবং X- অক্ষে ইনপুটের পরিমাণ আছে এবং যখন ইনপুট বৃদ্ধি পায় তখন সময় ও বৃদ্ধি পায়। এবং আমাদের যে সমস্যা আছে তা হল এর বক্র রেখা গ্রহণযোগ্য নয় কারণ, যখন N, ২০ সংখ্যায় যাবে আমরা আর এই সমস্যার সমাধান করতে পারবনা এবং আমরা আমাদের এলগরিদমে যদি শত সংখ্যার লম্বা ইনপুট দেই, আমরা সবাই জানি যে এটা কাজ করবে না এক্ষেত্রে এটা নষ্ট হয়ে যাবে। তাহলে আমাদের এখনকার এই পদ্ধতি অনুযায়ী যদি ইনপুট হিসেবে বড় মৌলিক সংখ্যা দেই তাহলে এটা পরীক্ষা করা কার্যত অসম্ভব। এখন প্রথম কথায় ফিরে যাই, উৎপাদকে বিশ্লেষণ এই অনুশীলনের শিক্ষা অনুযায়ী, উৎপাদকে বিশ্লেষণ, প্রাইমালিটি পরীক্ষা থেকে কঠিন হবে । কারণ এখানে কোন সংখ্যার উৎপাদকে বিশ্লেষণ নির্ণয় করতে হলে আরও কয়েকটি ধাপ প্রয়োজন, মনে করে দেখ, উৎপাদকে বিশ্লেষণে কোন ইনপুট N এর ক্ষেত্রে সবগুলো মৌলিক উৎপাদক কে নির্নয় করতে হয় অন্যদিকে প্রাইমালিটি পরীক্ষার ক্ষেত্রে, আমরা শুধু একটি ভাজক খুঁজি এবং এটার একটা সুন্দর অবশিষ্ট হল, কিছু কিছু ব্যবহারকারী প্রথম ভাজক পাবার পরে সহজেই একে পুনরাবৃত্ত করে এই প্রাইমালিটি
পরীক্ষাকে মৌলিক সংখ্যার উৎপাদকে বিশ্লেষণ এ রূপান্তর করেছে। তাহলে এই প্রাইমালিটি পরীক্ষা হল আসল মৌলিক সংখ্যার উৎপাদকে বিশ্লেষণের এলগরিদমের মধ্যকার একটি প্রক্রিয়া তাহলে আমরা যদি এই লেখ চিত্রে ফিরে যাই এলগরিদম এরকম কিছু একটা হবে যখন ইনপুট বৃদ্ধি পাবে আমাদের উৎপাদকে বিশ্লেষণ এলগরিদম এই প্রাইমালিটি পরীক্ষা রেখার উপরে চলে যাবে এবং বুঝতে হবে যে কোন পরিস্থিতিতে আমাদের গণনা সম্পর্কিত সীমাবদ্ধতা থাকতে পারে, এবং তা হল প্রাইমিটিভ পরীক্ষার ধাপ সংখ্যা যা যে কোন পরিস্থিতিতে গণনার ক্ষমতার উপর নির্ভর করে। এবং যে পরিমাণ সময় আমাদের হাতে আছে তার উপর নির্ভর করে একে অনুভুমিক রেখা ভাবা যায়। বা এই লেখ চিত্রের শীর্ষবিন্দু ভাবতে পার এই রেখার উপরে কোন কিছু সমাধান করা সম্ভব নয়, এবং এই অনুশীলনে আমরা রোভারের কম্পিউটার নিয়ে কাজ করছি যা ধীর গতির তাই আমরা প্রাইমালিটি পরীক্ষা সম্পন্ন করতে পারছি না যাই হোক, আমাদের যদি, মনে করি ১০০০ কম্পিউটার ১ বছর ধরে চলত তাহলে এটা হয়ত অনুভূমিক রেখা কে অন্য শীর্ষবিন্দুতে নিয়ে যেতে পারত তাহলে এটা বড় সংখ্যা নিয়ে কাজ করত কিন্তু তুমি দেখতে পাচ্ছ যে আমরা সবসময় কোন একটি সীমায় আটকে যাই যখন ইনপুট অনেক বড় হয় এবং সমস্যাটির আর সমাধান করা যায় না এখন এটি মজার কয়েকটি প্রশ্ন আসে। যাই হোক, আমি দুই কে পরবর্তীতে বিশ্লেষণ করব আমি অবশ্যই ২ কে চিহ্নিত করব এবং পরবর্তী ধাপে যাব। প্রথমে, এই ক্রমবৃদ্ধি রেখার ব্যাপারে এখনো যথাযথ জানি না। তুমি যদি আমাদের কোন এলগরিদম দাও, তাহলে এলগরিদমের বর্ণনা অনুযায়ী লেখচিত্রে ক্রমবৃদ্ধি রেখা আঁকা সম্ভব, এলগরিদমটি যেমনই হোক না কেন এবং আমরা যে যন্ত্রই ব্যবহার করি না কেন। এটা করতে পারলে আমরা বৃদ্ধি প্রাপ্ত বিভিন্ন আকার নিয়ে কাজ করতে পারি, যা আমাদের ধারনা দিবে যে একটি সমস্যা কে কিভাবে সমাধান করা যায় এবং এভাবে, আমরা একটি এলগরিদমকে চালনা করার পুর্বেই এর কর্মকান্ড সম্পর্কে বুঝতে পারব। তুমি হয়ত তোমার এলগরিদম টি কাগজে লিখে আমার হাতে দিবে এবং আমি দেখে বলতে পারব যে “আমি জানি এই এলগরিদম প্রয়োজনীয় এই ইনপুটের আকার অনুযায়ী সমাধান করা সম্ভব নয়” এবং এটা আমাদেরকে সময় সম্পর্কিত জটিলতার ক্ষেত্রে একটি গুরুত্তপূর্ণ শিক্ষা দিচ্ছে । এবং তুমি যদি কখনো শুনতে পাও যে এগুলোও বহুমাত্রিক সময়ে পাওয়া যায় তাহলে এগুলোই সময় জটিলতার বিভিন্ন প্রকাশ। এটা অবাক হওয়ার মত যে, RSA এর ক্ষেত্রে আমি দ্বিতীয় যে বিষয়টি উল্লেখ করেছিলাম, তা হল আমরা কিভাবে এই র্যান্ডম মৌলিক সংখ্যাগুলো পেয়েছি? দ্রুত চিন্তা করলে, শতসংখ্যা বিশিষ্ট বড় মৌলিক সংখ্যা উৎপন্ন করতে, আমাদেরকে এই নিচের নির্দেশগুলো পালন করতে হবে একটি র্যান্ডম সংখ্যা নেই, পরীক্ষা করি যে এটি মৌলিক কিনা, যদি এটি মৌলিক হয়, তাহলে আমাদের কাজ শেষ না হলে, আবার চেষ্টা কর যতক্ষন পর্যন্ত মৌলিক সংখ্যা না পাওয়া যায় এখন এই পদ্ধতির তিনটি ধাপের মধ্যে দ্বিতীয় ধাপটি গুরুত্বপূর্ণ, পরীক্ষা বলে এটি মৌলিক কিনা। আমরা যদি এই ধাপটি না করতে পারলে এটি কাজ করবে না তাহলে এখন কিভাবে কাজ করছে ? আসলে, এটা সমস্যাটির সংজ্ঞার সূক্ষ্ম পরিবর্তনের উপর নির্ভর করে বা আরো নির্দিষ্ট করে বললে, র্যান্ডম ব্যবহারের উপর ভিত্তি করে কাজ করছে । এবং এটা আমাদের র্যান্ডম এলগরিদম সম্পর্কে আরেকটি বিষয় শিক্ষা দেয় । এখন তোমার যদি এ ব্যাপারে আরো প্রশ্ন থাকে তাহলে নিচে এগুলো লিখ যেন আমরা নতুন ভিডিও এর পরিকল্পনা করতে পারি। উদাহরন স্বরূপ, আমাদের বর্তমান পরীক্ষামূলক প্রাইমালিটি পরীক্ষার জন্য আরো গভীর গাণিতিক সমীকরন নিয়ে কাজ করতে হবে। এবং এ বিষয়ে তোমার চিন্তাগুলো আমাদের জানাও। ## আগামী ও গ্রামীণফোন এর সহযোগিতায় অনূদিত ##