Pollard's kangaroo algorithm
গণনামূলক সংখ্যা তত্ত্ব এবং গণনামূলক বীজগণিতে, পোলার্ডের ক্যাঙ্গারু অ্যালগরিদম (এছাড়াও পোলার্ডের ল্যাম্বডা অ্যালগরিদম, নীচে নামকরণ দেখুন) হল বিচ্ছিন্ন লগারিদম সমস্যা সমাধানের জন্য একটি অ্যালগরিদম। অ্যালগরিদমটি 1978 সালে সংখ্যা তাত্ত্বিক জন এম. পোলার্ড দ্বারা একই সমস্যা সমাধানের জন্য তাঁর সুপরিচিত পোলার্ডের রো অ্যালগরিদমের মতো একই গবেষণাপত্রে চালু করা হয়েছিল। যদিও পোলার্ড একক মডুলো a প্রাইম p-এর গুণিতক গোষ্ঠীতে বিচ্ছিন্ন লগারিদম সমস্যার ক্ষেত্রে তাঁর অ্যালগরিদমের প্রয়োগ বর্ণনা করেছেন, এটি আসলে একটি সাধারণ বিচ্ছিন্ন লগারিদম অ্যালগরিদম-এটি যে কোনও সীমাবদ্ধ চক্রাকার গোষ্ঠীতে কাজ করবে। অ্যালগরিদম ধরুন ক্রমের একটি সীমাবদ্ধ চক্রাকার গোষ্ঠী যা উপাদান দ্বারা উত্পন্ন হয় এবং আমরা ভিত্তির উপাদানটির বিচ্ছিন্ন লগারিদম খুঁজে বের করার চেষ্টা করি। অন্য কথায়, একজন এমনটাই চায়। ল্যাম্বডা অ্যালগরিদম একজনকে কিছু বিরতিতে অনুসন্ধান করার অনুমতি দেয়। এবং সেট করে সম্ভাব্য লগারিদমের সম্পূর্ণ পরিসর অনুসন্ধান করা যেতে পারে। 1. মোটামুটি গড়ের ধনাত্মক পূর্ণসংখ্যার একটি সেট বেছে নিন এবং একটি ছদ্মবেশী মানচিত্র সংজ্ঞায়িত করুন। 2. একটি পূর্ণসংখ্যা বেছে নিন এবং 3 অনুসারে গোষ্ঠী উপাদানগুলির একটি ক্রম গণনা করুন। গণনা করুন লক্ষ্য করুনঃ 4। নিম্নলিখিত অনুসারে গোষ্ঠী উপাদানগুলির একটি দ্বিতীয় ক্রম গণনা করা শুরু করুনঃ এবং নিম্নলিখিত অনুসারে পূর্ণসংখ্যার একটি সংশ্লিষ্ট ক্রম। লক্ষ্য করুনঃ 5। নিম্নলিখিত শর্তগুলির মধ্যে যে কোনও একটি পূরণ হলে গণনা করা বন্ধ করুনঃ ক) কিছু ক্ষেত্রে। যদি ক্রম এবং "সংঘর্ষ" এইভাবে হয়, তাহলে আমাদের আছেঃ এবং তাই আমাদের কাজ শেষ। বি)। যদি এটি ঘটে, তবে অ্যালগরিদমটি খুঁজে পেতে ব্যর্থ হয়েছে। এবং/অথবা-এর পছন্দ পরিবর্তন করে পরবর্তী প্রচেষ্টা করা যেতে পারে। জটিলতা পোলার্ড অ্যালগরিদমের সময় জটিলতা দেয়, অনুমানের উপর ভিত্তি করে একটি সম্ভাব্য যুক্তি ব্যবহার করে যা ছদ্মবেশীভাবে কাজ করে। যেহেতু বিট ব্যবহার করে উপস্থাপন করা যেতে পারে, এটি সমস্যার আকারে সূচকীয় (যদিও এখনও সময় নেয় এমন তুচ্ছ ব্রুট-ফোর্স অ্যালগরিদমের তুলনায় উল্লেখযোগ্য উন্নতি)। একটি সাবএক্সপোনেনশিয়াল সময় বিচ্ছিন্ন লগারিদম অ্যালগরিদমের উদাহরণের জন্য, সূচক ক্যালকুলাস অ্যালগরিদম দেখুন। অ্যালগরিদম দুটি নামে সুপরিচিত। প্রথমটি হল "পোলার্ডের ক্যাঙ্গারু অ্যালগরিদম"। এই নামটি অ্যালগরিদম উপস্থাপনকারী কাগজে ব্যবহৃত একটি সাদৃশ্যের একটি রেফারেন্স, যেখানে অ্যালগরিদমটি একটি বন্য ক্যাঙ্গারু ফাঁদে ফেলার জন্য একটি নিয়ন্ত্রিত ক্যাঙ্গারু ব্যবহার করার ক্ষেত্রে ব্যাখ্যা করা হয়েছে। পোলার্ড ব্যাখ্যা করেছেন যে এই উপমাটি আরএসএ পাবলিক কী ক্রিপ্টোসিস্টেমের একটি প্রদর্শনী হিসাবে সায়েন্টিফিক আমেরিকান-এর একই সংখ্যায় প্রকাশিত একটি "আকর্ষণীয়" নিবন্ধ দ্বারা অনুপ্রাণিত হয়েছিল। নিবন্ধটি একটি পরীক্ষার বর্ণনা দিয়েছে যেখানে একটি ক্যাঙ্গারু "বিভিন্ন গতিতে অক্সিজেন খরচের পরিপ্রেক্ষিতে পরিমাপ করা হয়, যা একটি ট্রেডমিলে ক্যাঙ্গারু স্থাপন করে নির্ধারণ করা হয়"। দ্বিতীয়টি হল "পোলার্ডের ল্যাম্বডা অ্যালগরিদম"। পোলার্ডের আরেকটি বিচ্ছিন্ন লগারিদম অ্যালগরিদম, পোলার্ডের রো অ্যালগরিদমের নামের মতোই, এই নামটি অ্যালগরিদমের একটি দৃশ্যায়ন এবং গ্রীক অক্ষর ল্যাম্বডা (λ)-এর মধ্যে সাদৃশ্যকে বোঝায়। ল্যাম্বডা অক্ষরের ছোট স্ট্রোকটি ক্রমের সাথে মিলে যায়, কারণ এটি x এর ডানদিকে অবস্থান b থেকে শুরু হয়। তদনুসারে, দীর্ঘ স্ট্রোকটি ক্রমের সাথে মিলে যায়, যা প্রথম ক্রমের সাথে "সংঘর্ষ" করে (ঠিক একটি ল্যাম্বডা ছেদ করার স্ট্রোকের মতো) এবং তারপরে এটি অনুসরণ করে। পোলার্ড "ক্যাঙ্গারু অ্যালগরিদম" নামটির জন্য পছন্দ প্রকাশ করেছেন, কারণ এটি তাঁর রো অ্যালগরিদমের কিছু সমান্তরাল সংস্করণের সাথে বিভ্রান্তি এড়ায়, যাকে "ল্যাম্বডা অ্যালগরিদম" ও বলা হয়। আরও দেখুন ডাইনকিনের কার্ড ট্রিক ক্রুস্কাল কাউন্ট রেইনবো টেবিল রেফারেন্স আরও পড়া সংখ্যা তাত্ত্বিক অ্যালগরিদম কম্পিউটার বীজগণিত লগারিদম