Barrett reduction
মডুলার গাণিতিক ক্ষেত্রে, ব্যারেট রিডাকশন হল একটি রিডাকশন অ্যালগরিদম যা 1986 সালে পি. ডি. ব্যারেট। কম্পিউটিংয়ের একটি সরল উপায় হল একটি দ্রুত বিভাজন অ্যালগরিদম ব্যবহার করা। ব্যারেট রিডাকশন হল একটি অ্যালগরিদম যা স্থির ধরে নিয়ে এই ক্রিয়াকলাপকে অনুকূল করার জন্য ডিজাইন করা হয়েছে, এবং গুণ দ্বারা বিভাগগুলিকে প্রতিস্থাপন করে। ঐতিহাসিকভাবে, মানগুলির জন্য, সম্পূর্ণ পণ্যটিতে ব্যারেট হ্রাস প্রয়োগ করে গণনা করা হয়। সম্প্রতি, এটি দেখানো হয়েছে যে পুরো পণ্যটি অপ্রয়োজনীয় যদি আমরা অপারেন্ডগুলির মধ্যে একটিতে প্রাক-গণনা করতে পারি। সাধারণ ধারণা আমরা একটি ফাংশনকে একটি পূর্ণসংখ্যা আনুমানিক বলি যদি। একটি মডুলাস এবং একটি পূর্ণসংখ্যার আনুমানিক জন্য, আমরা হিসাবে সংজ্ঞায়িত করি। এর সাধারণ পছন্দগুলি হল মেঝে, ছাদ এবং বৃত্তাকার ফাংশন। সাধারণত, ব্যারেট গুণ দুটি পূর্ণসংখ্যার আনুমানিক উল্লেখ করে শুরু হয় এবং একটি যুক্তিসঙ্গতভাবে কাছাকাছি আনুমানিক গণনা করে, যেখানে একটি নির্দিষ্ট ধ্রুবক, সাধারণত 2 এর একটি শক্তি, বেছে নেওয়া হয় যাতে গুণ এবং ভাগ দক্ষতার সাথে সম্পাদন করা যায়। মামলাটি পি. ডি. দ্বারা উপস্থাপিত হয়েছিল। ফ্লোর-ফাংশন মামলার জন্য ব্যারেট। সাধারণ কেসটি এন. টি. এল-এ পাওয়া যাবে। হ্যানো বেকার, ভিনসেন্ট হোয়াং, ম্যাথিয়াস জে কানউইশার, বো-ইয়িন ইয়াং এবং শ্যাং-ই ইয়াং দ্বারা পূর্ণসংখ্যার আনুমানিক দৃশ্য এবং মন্টগোমেরি গুণ এবং ব্যারেট গুণের মধ্যে যোগাযোগ আবিষ্কৃত হয়েছিল। একক-শব্দের ব্যারেট হ্রাস ব্যারেট প্রাথমিকভাবে উপরের অ্যালগরিদমের একটি পূর্ণসংখ্যা সংস্করণ হিসাবে বিবেচিত হয় যখন মানগুলি যান্ত্রিক শব্দের সাথে খাপ খায়। আমরা এবং দিয়ে ফ্লোর-ফাংশন কেসের ধারণাটি ব্যাখ্যা করি। স্বাক্ষরহীন পূর্ণসংখ্যার জন্য গণনা করার সময়, সুস্পষ্ট এনালগটি এই দ্বারা বিভাজন ব্যবহার করা হবেঃ ফাংক হ্রাস (একটি ইউন্ট) ইউন্ট {q: = a/n// বিভাজন অন্তর্নিহিতভাবে ফলাফলের মেঝে প্রদান করে। যাইহোক, বিভাজন ব্যয়বহুল হতে পারে এবং, ক্রিপ্টোগ্রাফিক সেটিংসে, কিছু সিপিইউতে একটি ধ্রুবক-সময়ের নির্দেশ নাও হতে পারে, যা অপারেশনটিকে একটি সময় আক্রমণের বিষয় করে তোলে। এইভাবে ব্যারেট হ্রাস একটি মান সহ আনুমানিক কারণ দ্বারা বিভাজন কেবল একটি ডান-স্থানান্তর, এবং তাই এটি সস্তা। প্রদত্ত বিবেচনার জন্য সর্বোত্তম মান গণনা করার জন্যঃ একটি পূর্ণসংখ্যা হওয়ার জন্য, আমাদের কোনওভাবে বৃত্তাকার করতে হবে। নিকটতম পূর্ণসংখ্যায় বৃত্তাকার করা সর্বোত্তম অনুমান দেবে তবে এর চেয়ে বড় হতে পারে, যা নিম্নপ্রবাহের কারণ হতে পারে। এইভাবে স্বাক্ষরহীন গাণিতিকের জন্য ব্যবহার করা হয়। এইভাবে আমরা উপরের ফাংশনটিকে নিম্নরূপ দিয়ে আনুমানিক করতে পারিঃ 'ফাঙ্ক রিডিউস (আ উইনট) উইনট' {q: = (a * m)> 'k/'> 'k' 'দ্বারা বিটশিফটকে বোঝায়। একটি শর্তাধীন বিয়োগ এটিকে সংশোধন করবেঃ যদি a> = n {a-= n} রিটার্ন a} একক-শব্দের ব্যারেট গুণন জানা থাকে তবে func হ্রাস (a uint) uint {q: = (a * m)>> k a-= q * n। এটি আমাদের গ্রহণ করার আগে প্রাক-গণনা করার অনুমতি দেয়। ব্যারেট গুণন গণনা করে, সঙ্গে উচ্চ অংশ আনুমানিক করে এবং আনুমানিক বিয়োগ করে। যেহেতু এর গুণিতক, ফলস্বরূপ মানটি এর প্রতিনিধিত্ব করে। ব্যারেট এবং মন্টগোমেরি গুণনের মধ্যে যোগাযোগ স্মরণ করুন যে স্বাক্ষরহীন মন্টগোমেরি গুণন হিসাবে একটি প্রতিনিধি গণনা করে। প্রকৃতপক্ষে, এই মান সমান। আমরা নিম্নরূপ দাবিটি প্রমাণ করি। সাধারণত, পূর্ণসংখ্যার আনুমানিকতার জন্য, আমাদের আছে। ব্যারেট গুণনের পরিসীমা আমরা আউটপুটকে এর সাথে আবদ্ধ করি। অনুরূপ সীমা অন্যান্য ধরনের পূর্ণসংখ্যা আনুমানিক ফাংশনের জন্য থাকে। উদাহরণস্বরূপ, যদি আমরা রাউন্ডিং হাফ আপ ফাংশনটি বেছে নিই, তবে আমাদের কাছে মাল্টি-ওয়ার্ড ব্যারেট রিডাকশন ব্যারেটের প্রাথমিক অনুপ্রেরণা ছিল আরএসএ-র বাস্তবায়ন, যেখানে প্রশ্নযুক্ত মানগুলি প্রায় অবশ্যই একটি মেশিন শব্দের আকার অতিক্রম করবে। এই পরিস্থিতিতে, ব্যারেট একটি অ্যালগরিদম সরবরাহ করেছিলেন যা উপরের একক-শব্দের সংস্করণকে আনুমানিক করে কিন্তু বহু-শব্দের মানগুলির জন্য। বিস্তারিত তথ্যের জন্য হ্যান্ডবুক অফ অ্যাপ্লায়েড ক্রিপ্টোগ্রাফির 14.3.3 বিভাগটি দেখুন। বহুপদগুলির জন্য ব্যারেট অ্যালগরিদম বহুপদ বিভাজনের জন্য ব্যারেট অ্যালগরিদম ব্যবহার করা সম্ভব, বহুপদগুলিকে বিপরীত করে এবং এক্স-এডিক গাণিতিক ব্যবহার করে। আরও দেখুন মন্টগোমেরি হ্রাস আরেকটি অনুরূপ অ্যালগরিদম। তথ্যসূত্র উৎস কম্পিউটার গাণিতিক মডুলার গাণিতিক