Barrett reduction
ماڈیولر ریاضی میں، بیریٹ کمی ایک تخفیف الگورتھم ہے جسے 1986 میں پی ڈی نے متعارف کرایا تھا۔ بیریٹ۔ کمپیوٹنگ کا ایک سادہ طریقہ تیز تقسیم الگورتھم کا استعمال کرنا ہوگا۔ بیریٹ ریڈکشن ایک الگورتھم ہے جو اس عمل کو بہتر بنانے کے لیے ڈیزائن کیا گیا ہے یہ فرض کرتے ہوئے کہ یہ مستقل ہے، اور ضرب کے ذریعے تقسیم کی جگہ لے لیتا ہے۔ تاریخی طور پر، اقدار کے لیے، مکمل پروڈکٹ پر بیریٹ کی کمی کو لاگو کرکے شمار کیا جاتا ہے۔ حال ہی میں، یہ دکھایا گیا تھا کہ مکمل پروڈکٹ غیر ضروری ہے اگر ہم آپریڈز میں سے کسی ایک پر پری کمپیوٹیشن انجام دے سکتے ہیں۔ عام خیال ہم کسی فنکشن کو انٹیجر کا تخمینہ کہتے ہیں اگر۔ ماڈیولس اور انٹیجر کے تخمینے کے لیے، ہم اس کی تعریف کرتے ہیں۔ کے عام انتخاب فرش، چھت، اور گول کرنے کے افعال ہیں۔ عام طور پر، بیریٹ ضرب دو عدد تخمینوں کی وضاحت سے شروع ہوتی ہے اور ایک معقول حد تک قریب تخمینہ کا حساب لگاتا ہے، جہاں ایک مقررہ مستقل، عام طور پر 2 کی طاقت ہے، جس کا انتخاب کیا جاتا ہے تاکہ ضرب اور تقسیم کو مؤثر طریقے سے انجام دیا جا سکے۔ یہ مقدمہ پی ڈی نے پیش کیا تھا۔ فلور فنکشن کیس کے لیے بیریٹ۔ کے لیے عمومی کیس این ٹی ایل میں پایا جا سکتا ہے۔ عدد تخمینہ کا نظریہ اور مونٹگمری ضرب اور بیریٹ ضرب کے درمیان خط و کتابت ہنو بیکر، ونسنٹ ہوانگ، میتھیاس جے کنوشر، بو ین یانگ، اور شانگ یی یانگ نے دریافت کیا تھا۔ سنگل ورڈ بیریٹ ریڈکشن بیریٹ کو ابتدائی طور پر مذکورہ بالا الگورتھم کا ایک انٹیجر ورژن سمجھا جاتا ہے جب اقدار مشین ورڈز میں فٹ ہوتی ہیں۔ ہم اور کے ساتھ فلور فنکشن کیس کے خیال کی وضاحت کرتے ہیں۔ غیر دستخط شدہ انٹیجرز کا حساب لگاتے وقت، واضح ینالاگ یہ ہوگا کہ تقسیم کا استعمال کرتے ہوئے: فنک کم کریں (ایک یوئنٹ) یوئنٹ {q: = a/n// ڈویژن واضح طور پر نتیجہ کا فرش واپس کرتا ہے۔ تاہم، تقسیم مہنگا ہو سکتا ہے اور، کرپٹوگرافک ترتیبات میں، کچھ سی پی یو پر مستقل وقت کی ہدایت نہیں ہو سکتی ہے، جس سے آپریشن کو ٹائمنگ اٹیک کا نشانہ بنایا جا سکتا ہے۔ اس طرح بیریٹ کی کمی ایک قدر کے ساتھ لگ بھگ ہوتی ہے کیونکہ تقسیم کرنا صرف ایک دائیں شفٹ ہے، اور اس لیے یہ سستا ہے۔ دیئے گئے غور کے لیے بہترین قدر کا حساب لگانے کے لیے: ایک عدد ہونے کے لیے، ہمیں کسی نہ کسی طرح گول کرنے کی ضرورت ہے۔ قریب ترین عدد کو گول کرنے سے بہترین تخمینہ ملے گا لیکن اس کے نتیجے میں اس سے بڑا ہو سکتا ہے، جو زیر بہاؤ کا سبب بن سکتا ہے۔ اس طرح غیر دستخط شدہ ریاضی کے لیے استعمال ہوتا ہے۔ اس طرح ہم مندرجہ بالا فنکشن کا تخمینہ مندرجہ ذیل کے ساتھ لگا سکتے ہیں: فنک کم کریں (a uint) uint {q: = (a * m)>> k// "> k" بٹس شفٹ کو k سے ظاہر کرتا ہے۔ a-q * n واپس کریں} تاہم، چونکہ، اس فنکشن میں q کی قیمت ایک بہت چھوٹی ہو سکتی ہے، اور اس طرح a کو عام طور پر درکار ہونے کے بجائے صرف اس کے اندر ہونے کی ضمانت دی جاتی ہے۔ ایک مشروط گھٹاؤ اسے درست کرے گا: اگر a> = n {a-= n} لوٹ a} ایک لفظ بیریٹ ضرب معلوم ہے تو فنک کم (a uint) uint {q: = (a * m)>> k a-= q * n۔ یہ ہمیں موصول ہونے سے پہلے پہلے سے حساب کرنے کی اجازت دیتا ہے۔ بیریٹ ضرب حساب لگاتا ہے، ساتھ کے اعلی حصے کا تخمینہ لگاتا ہے، اور تخمینہ کو گھٹاتا ہے۔ چونکہ کا ایک ضرب ہے، اس کے نتیجے میں حاصل ہونے والی قیمت کا نمائندہ ہے۔ بیریٹ اور مونٹگمری ضرب کے درمیان خط و کتابت یاد رکھیں کہ غیر دستخط شدہ مونٹگمری ضرب اس کے نمائندے کا حساب لگاتا ہے۔ درحقیقت یہ ویلیو اس کے برابر ہے۔ ہم اس دعوے کو درج ذیل طریقے سے ثابت کرتے ہیں۔ عام طور پر، انٹیجر تخمینوں کے لیے، ہمارے پاس ہے۔ بیریٹ ضرب کی حد ہم نے آؤٹ پٹ کو اس کے ساتھ بانڈ کیا۔ اسی طرح کی حدود دیگر قسم کے انٹیجر اپروکسیمیشن افعال کے لیے ہوتی ہیں۔ مثال کے طور پر، اگر ہم راؤنڈنگ ہاف اپ فنکشن کا انتخاب کرتے ہیں، تو ہمارے پاس ملٹی ورڈ بیریٹ ریڈکشن بیریٹ کا بنیادی محرک آر ایس اے کا نفاذ تھا، جہاں زیر بحث اقدار تقریبا یقینی طور پر مشین ورڈ کے سائز سے تجاوز کر جائیں گی۔ اس صورت حال میں، بیریٹ نے ایک الگورتھم فراہم کیا جو اوپر ایک لفظ کے ورژن کا تخمینہ لگاتا ہے لیکن کثیر الفاظ کی اقدار کے لیے۔ تفصیلات کے لیے ہینڈ بک آف اپلائیڈ کرپٹوگرافی کا سیکشن 14.3.3 دیکھیں۔ کثیر الجہتی کے لیے بیریٹ الگورتھم کثیر الجہتی تقسیم کے لیے بیریٹ الگورتھم کا استعمال کرنا بھی ممکن ہے، کثیر الجہتی کو الٹ کر اور X-adic ریاضی کا استعمال کرکے۔ یہ بھی دیکھیں کہ مونٹگمری کمی ایک اور اسی طرح کا الگورتھم ہے۔ حوالہ جات ذرائع کمپیوٹر ریاضی ماڈیولر ریاضی