نظام الأرقام المتبقية

الموسوعة الحرة

نظام الأعداد المتبقية ( RNS ) هو نظام عددي يُمثل الأعداد الصحيحة بقيمها بترددات معينة تُسمى " المعاملات". هذا التمثيل مسموح به بموجب نظرية الباقي الصينية ، التي تنص على أنه إذا كان M هو حاصل ضرب المعاملات، فإنه يوجد، في فترة طولها M ، عدد صحيح واحد فقط له أي مجموعة معينة من القيم المعيارية. يُطلق على استخدام نظام الأعداد المتبقية في العمليات الحسابية أيضًا اسم الحساب متعدد المعاملات .

يُستخدم الحساب متعدد الأنماط على نطاق واسع في العمليات الحسابية للأعداد الصحيحة الكبيرة، وخاصةً في الجبر الخطي ، لأنه يوفر سرعة حسابية أعلى من أنظمة العد التقليدية، حتى مع الأخذ في الاعتبار وقت التحويل بين هذه الأنظمة. وتشمل التطبيقات الأخرى للحساب متعدد الأنماط حساب القاسم المشترك الأكبر لكثيرات الحدود ، وحساب أساس غروبنر، والتشفير .

تعريف

يُعرَّف نظام الأعداد المتبقية بمجموعة من k عدد صحيح

{م1،م2،م3،...،مك}،{\displaystyle \{m_{1},m_{2},m_{3},\ldots ,m_{k}\},}

تُسمى هذه الأعداد بالمعاملات ، والتي يُفترض عمومًا أن تكون أولية فيما بينها (أي أن أي اثنين منها لهما قاسم مشترك أكبر يساوي واحدًا). ​​وقد تم تعريف أنظمة أعداد البواقي للمعاملات غير الأولية فيما بينها، ولكنها غير شائعة الاستخدام بسبب خصائصها الأقل جودة. [ 1 ]

يتم تمثيل العدد الصحيح x في نظام الأرقام الباقية بواسطة عائلة بواقيه (مفهرسة بواسطة معاملات مؤشرات المعاملات).

{x1،x2،x3،...،xك}{\displaystyle \{x_{1},x_{2},x_{3},\ldots ,x_{k}\}}

في ظل القسمة الإقليدية على المعاملات. أي

xأنا=xتعديل⁡مأنا،{\displaystyle x_{i}=x\operatorname {mod} m_{i},}

و

0≤xأنا<مأنا{\displaystyle 0\leq x_{i}<m_{i}}

لكل i

ليكن M هو حاصل ضرب جميعمأنا{\displaystyle m_{i}}عددان صحيحان يكون الفرق بينهما من مضاعفات العدد M لهما نفس التمثيل في نظام البواقي العددي المحدد بواسطة m و i و s. بتعبير أدق، تنص نظرية الباقي الصينية على أن كل مجموعة من مجموعات البواقي الممكنة البالغ عددها M تمثل فئة بواقي واحدة فقط بتردد M. أي أن كل مجموعة من البواقي تمثل عددًا صحيحًا واحدًا فقط.X{\displaystyle X}في الفترة0،...،م-1{\displaystyle 0,\dots ,M-1}بالنسبة للأعداد الموقعة، يكون النطاق الديناميكي هو-⌊م/2⌋≤X≤⌊(م-1)/2⌋{\textstyle {-\lfloor M/2\rfloor }\leq X\leq \lfloor (M-1)/2\rfloor } (متىم{\displaystyle M}(إذا كان العدد زوجيًا، فإنه يُمثل عادةً بقيمة سالبة إضافية). [ 2 ]

العمليات الحسابية

لجمع وطرح وضرب الأعداد الممثلة في نظام عددي متبقٍ، يكفي إجراء نفس العملية المعيارية على كل زوج من البقايا. بتعبير أدق، إذا

[م1،...،مك]{\displaystyle [m_{1},\ldots ,m_{k}]}

هي قائمة المعاملات، ومجموع الأعداد الصحيحة x و y ، والتي تمثلها البواقي على التوالي.[x1،...،xك]{\displaystyle [x_{1},\ldots ,x_{k}]}و[y1،...،yك]،{\displaystyle [y_{1},\ldots ,y_{k}],}يمثل العدد الصحيح z بواسطة[z1،...،zك]،{\displaystyle [z_{1},\ldots ,z_{k}],}بحيث

zأنا=(xأنا+yأنا)تعديل⁡مأنا،{\displaystyle z_{i}=(x_{i}+y_{i})\operatorname {mod} m_{i},}

بالنسبة لـ i = 1، ...، k (كما هو معتاد، يرمز mod إلى عملية باقي القسمة التي تتضمن أخذ باقي قسمة العدد الإقليدي على المعامل الأيمن). يتم تعريف الطرح والضرب بشكل مماثل.

في سلسلة العمليات، ليس من الضروري تطبيق عملية باقي القسمة في كل خطوة. يمكن تطبيقها في نهاية الحساب، أو أثناء الحساب، لتجنب تجاوز سعة عمليات الجهاز.

ومع ذلك، فإن عمليات مثل مقارنة المقادير، وحساب الإشارة، واكتشاف تجاوز السعة، والتحجيم، والقسمة يصعب إجراؤها في نظام الأعداد المتبقية. [ 3 ]

مقارنة

إذا تساوى عددان صحيحان، فإن جميع بواقيهما تكون متساوية. والعكس صحيح، إذا كانت جميع البواقي متساوية، فإن العددين الصحيحين إما متساويان أو يختلفان بمضاعفات العدد M. ومن ثم، فإن اختبار التساوي أمر سهل.

على النقيض من ذلك، يُعدّ اختبار المتباينات ( س < ص ) صعبًا، ويتطلب عادةً تحويل الأعداد الصحيحة إلى تمثيلها القياسي. ونتيجةً لذلك، فإن هذا التمثيل للأعداد غير مناسب للخوارزميات التي تستخدم اختبارات المتباينات، مثل القسمة الإقليدية وخوارزمية إقليدس .

قسم

القسمة في أنظمة الأعداد المتبقية تُعدّ إشكالية. من ناحية أخرى، إذاب{\displaystyle B}هو عدد أولي مشترك معم{\displaystyle M}(إنهبأنا≠0{\displaystyle b_{i}\not =0}) ثم

ج=أ⋅ب-1تعديلم{\displaystyle C=A\cdot B^{-1}\mod M}

يمكن حسابها بسهولة بواسطة

جأنا=أأنا⋅بأنا-1تعديلمأنا،{\displaystyle c_{i}=a_{i}\cdot b_{i}^{-1}\mod m_{i},}

أينب-1{\displaystyle B^{-1}}هو المعكوس الضربي لـب{\displaystyle B}moduloم{\displaystyle M}، وبأنا-1{\displaystyle b_{i}^{-1}}هو المعكوس الضربي لـبأنا{\displaystyle b_{i}}moduloمأنا{\displaystyle m_{i}}.

التطبيقات

تُستخدم أنظمة الأعداد العشوائية في مجال الحساب الرقمي . فمن خلال تقسيم عدد صحيح كبير إلى مجموعة من الأعداد الصحيحة الأصغر، يمكن إجراء عملية حسابية كبيرة كسلسلة من العمليات الحسابية الأصغر التي يمكن تنفيذها بشكل مستقل ومتوازٍ.

انظر أيضاً

مراجع

  1. ↑ بارامي، بهروز (2010). الحساب الحاسوبي: الخوارزميات وتصميمات الأجهزة (  الطبعة الثانية). نيويورك، الولايات المتحدة الأمريكية: مطبعة جامعة أكسفورد . ISBN 978-0-19-532848-6أُرشف من المصدر الأصلي بتاريخ 4 أغسطس 2020. تم الاطلاع عليه بتاريخ 23 يناير 2021 .(xxv+641 صفحة)
  2. ↑ هونغ، سي واي؛ بارامي، ب. (1994-02-01). "طريقة تقريبية للكشف عن الإشارة لأعداد البواقي وتطبيقها على قسمة الأعداد المتبقية" (ملف PDF) . الحوسبة والرياضيات مع التطبيقات . 27 (4): 23-35 . doi : 10.1016/0898-1221(94)90052-3 .
  3. ↑ إيسوبوف، كونستانتين (2020-04-07) [2020-03-20، 2020-03-08، 2020-02-17]. "استخدام فترات الفاصلة العائمة للحسابات غير النمطية في نظام الأعداد المتبقية" . IEEE Access . 8 : 58603–58619 . Bibcode : 2020IEEEA...858603I . doi : 10.1109/ACCESS.2020.2982365 . ISSN 2169-3536 . 

للمزيد من القراءة