حساب مقاسي: الفرق بين النسختين

تصفح التاريخ تفاعلياً

[نسخة منشورة]

→ التعديل السابق التعديل اللاحق ←

تم حذف المحتوى تمت إضافة المحتوى

مرئينص الويكي

مضمن

نسخة 23:46، 4 يناير 2014

الصفحة الأولى من الطبعة الأصلية من كتاب كارل فريدريش غاوس، **استفسارات حسابية**، الكتاب المؤسس للحسابيات النمطية.

في الرياضيات وبالتحديد في مجال النظرية الجبرية للأعداد ، الحسابيات النمطية (بالإنكليزية: modular arithmetics) هي مجموعة من الطرق التي تتيح حل بعض المسائل الخاصة بالأعداد الصحيحة و من ضمنها الطبيعية. وهي ترتكز على دراسة الباقي الحاصل من القسمة الإقليدية.

استعمالات

في الرياضيات الأساسية, هذا المفهوم قليل الاستعمال. التوظيف الأكثر استعمالا هو المبرهنة الجيرية للأعداد^[1], التي تتضمن مجالا أكثر توسعا, تتضمن مثلا مفاهيم الأعداد الجبرية ومبرهنة غالوا^[2].

في الرياضيات التطبيقية, لهذه العبارة استعمالات مكثفة في أساسيات الرياضيات في مختلف مجالات نظرية المعلوميات كالتشفير ونظرية الترميز والمعلوميات. لعدد من الأدوات وخوارزميات داخل هذا المجال نجد اختبار أولية عدد ما والتفكيك إلى جداء عوامل أولية^[3], استعمال مميزات مجموعة مثلا بالنسبة لتحويل فوريي المتقطع^[4] أو دراسة الخارج أو الخاصة بالأعداد الطبيعية, كما في الدوال الحدودية^[5].

حسب مختلف العلماء والمألفين وحسب مجال التطبيق, تعتبر هذه التمديدات, إما جزء من الحسابيات النمطية^[6] أو تطبيقات أو غير مصنفة. في صيغتها البسيطة, تحمل في بعض الأحيان حسابيات المنبه^[7]. المفهوم نظام نمطي مستعمل^[8] في الحسابيات النمطية في مجموعات أعداد غير الأعداد الطبيعية.

التاريخ

الأصول الأولى

الصفحة الأولى لطبعة 1621 ل Arithmetica لمؤلفه ديوفانتوس الاسكندري، المترجمة إلى اللاتينية من طرف كلود غاسبارد باشي دي ميزيرياك.

الظهور في أوروبا

الطرق المستعملة

مساهمات كارل فريدريش غاوس

القرن العشرون

التعمية

أوجوست كيركهوفس énonce un principe fondateur de la cryptologie moderne.

*Enigma*, une machine de chiffrement utilisée durant la Seconde Guerre mondiale, décrypté par un mathématicien : Marian Rejewski.

نظرية المعلومات

وسائل الحسابيات النمطية

التقارب والأعداد الطبيعية

المثال التاريخي حسابيات نمطية يرتكز على أعداد طبيعية. العدد n ثابت, الحياب النمطي n ترتكز على تحديد كل الأعداد الطبيعية لباقي قسمتها على n ; هذا يمكن أن يظهر جليا في مثال حسابيات المنبه, الذي يوافق حالة n=12 : العقرب الصغير يوجد في نفس الموضع في لحظتين تفصل بينهما اثنتا عشر ساعة, وبهذا تصير الساعة 1 كالساعة 13. للحصول على حساب من نوع هذه المجموعة, علينا التأكد من كون عمليـّـتي الجمع والضرب متكافئة مع تعريفهما.

بالنسبة لكارل فريدرش غاوس فقد أضاف تحليل بنية هذه المجموعة, والمسماة حلقة ل تقارب ورمزها Z/nZ. تهتم أولا بدراسة عملية الجمع, الذي يعرف بزمرة دائرية ذات المولد 1 ; ثم عملية الضرب, المستقل عن خصائص التطابق (congruency) . إذا كان هذا عددا أوليا, نحصل على حقل . هذه المقاربة تسهل عملية المبرهنة في مجال الحسابيات. المثالان التاريخيان من كتاب Disquisitiones arithmeticae تبع الرياضياتي الألماني غاوس هما مبرهنة ويلسون^[9] والبرهنة على مبرهنة فيرما الصغرى ^[10].

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

تلميحة تمهيدية للتطبيق

أساسيات

تعتبر الحسابيات النمطية نظاما حسابيا للأعداد الصحيحة يعتمد على تكرار الأعداد بشكل نمطي لدى بلوغها قيمة نمطية (modulus) معينة ، و هي تـُـخـْـتـَـزَل بالتعبير خطأ رياضيات (خطأ في التحويل. أبلغ الخادوم («https://wikimedia.org/api/rest_») عن: «Cannot get mml. upstream connect error or disconnect/reset before headers. reset reason: connection termination»): {\displaystyle \mod } . مرتبط بذلك الرياضياتيون يتكلمون عن " تطابق " (congruency) .

على فرض لدينا عدد صحيح موجب $n\!$ وعدد صحيح $a\!$ فإننا بقسمة $a\!$ على $n\!$ نحصل على عدد صحيح $q\!$ هو ناتج القسمة وعدد صحيح $r\!$ هو باقي القسمة بحيث يحققان العلاقة التالية:

$a=qn+r\quad 0\leq r<n;\quad q=\lfloor a/n\rfloor$

حيث الصيغة $\lfloor x\rfloor$ تعني أكبر عدد صحيح أصغر أو يساوي $x\!$

يرمز إلى عملية حساب باقي القسمة ب mod حيث نكتب $r=a\mod n\!$ وبالتالي:

$a=\lfloor a/n\rfloor \times n+(a\mod n)$

أمثلة:

${\mathcal {}}5\mod 7=5$

${\mathcal {}}0\mod 7=0$

${\mathcal {}}7\mod 7=0$

${\mathcal {}}11\mod 7=4$

${\mathcal {}}-11\mod 7=3$

نقول عن عددين صحيحين $a\!$ و $b\!$ بانهما متوافقان ببقية $n\!$ إذا تحقق $(a\mod n)=(b\mod n)$ ونرمز لذلك بـ $a\equiv b\mod n$

خصائص عملية حساب باقي القسمة

$a\equiv b\mod n$ فقط إذا كان، $n|(a-b)\!$
$a\equiv b\mod n\Rightarrow b\equiv a\mod n$
$a\equiv b\mod n\wedge b\equiv c\mod n\Rightarrow a\equiv c\mod n$

خصائص الحسابيات النمطية

xy mod m=(x mod m)(y mod m) mod m

(x+y) mod m=((x mod m)+ (y mod m) ) mod m

x^4 mod m= (x^2 mod m)(x^2 mod m) mod m

125^6 mod 187=(125^2 mod 187)^3 mod 87

انظر أيضا

حقل منته
- مبرهنة الباقي الصيني
نظرية الأعداد
- زمرة دائرية
- مبرهنة أويلر
- مبرهنة فيرما الصغرى، حالة خاصة من مبرهنة أويلر
- مبرهنة لاغرانج (نظرية الزمر)
رمز لوجوندر

مراجع

^ قالب:Samuel1
^ A. Fröhlich, Galois Module structure of Algebraic integers, Springer-Verlag, Berlin, 1983.
^ Chantal David Cryptographie à clé publique et factorisation Université Concordia Quebec pp. 11-17
^ J-M Muller J-C Bajard Calcul arithmétique des ordinateurs Traité Hermes CNRS 2004 lire pp. 142-150 et pp. 181-201
^ Pascal Giorgi Arithmétique modulaire entière en base polynomiale Séminaire de l'université de Perpignan 2005 lire
^ Thomas Plantard L'arithmétique modulaire pour la cryptographie Université de Montpelier 2005 lire
^ Simon Singh Histoire des codes secrets p. 324-329
^ Pascal Paillier Low-cost double-size modular exponentiation or how to stretch your cryptoprocessor GEMPLUS, ENST Lecture notes in computer science Springer, Berlin 1973
^ كارل فريدرش غاوس, Carl Friedrich Gauß: Recherches arithmétiques, 1801 Traduction M. Poullet-Delisle Ed. Courcier p56 1807
^ كارل فريدرش غاوس, Carl Friedrich Gauß: Recherches arithmétiques, 1801 Traduction M. Poullet-Delisle Ed. Courcier p. 34 1807

وصلات خارجية

قالب:بوابة رياضيات

قالب:وصلة مقالة مختارة قالب:وصلة مقالة مختارة

[1] قالب:Samuel1

[2] A. Fröhlich, Galois Module structure of Algebraic integers, Springer-Verlag, Berlin, 1983.

[3] Chantal David Cryptographie à clé publique et factorisation Université Concordia Quebec pp. 11-17

[4] J-M Muller J-C Bajard Calcul arithmétique des ordinateurs Traité Hermes CNRS 2004 lire pp. 142-150 et pp. 181-201

[5] Pascal Giorgi Arithmétique modulaire entière en base polynomiale Séminaire de l'université de Perpignan 2005 lire

[6] Thomas Plantard L'arithmétique modulaire pour la cryptographie Université de Montpelier 2005 lire

[7] Simon Singh Histoire des codes secrets p. 324-329

[8] Pascal Paillier Low-cost double-size modular exponentiation or how to stretch your cryptoprocessor GEMPLUS, ENST Lecture notes in computer science Springer, Berlin 1973

[9] كارل فريدرش غاوس, Carl Friedrich Gauß: Recherches arithmétiques, 1801 Traduction M. Poullet-Delisle Ed. Courcier p56 1807

[10] كارل فريدرش غاوس, Carl Friedrich Gauß: Recherches arithmétiques, 1801 Traduction M. Poullet-Delisle Ed. Courcier p. 34 1807

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ سطر 30: / سطر 30: @@
 ===القرن العشرون===
 ====التعمية====
+[[ملف:Kerkhoffs.jpg|right|thumb|[[أوجوست كيركهوفس]] énonce un principe fondateur de la [[cryptologie]] moderne.]]
+[[ملف:Enigma.jpg|thumb|''[[Enigma (machine)|Enigma]]'', une machine de chiffrement utilisée durant la [[Seconde Guerre mondiale]], décrypté par un [[mathématicien]] : [[Marian Rejewski]].]]
 ====نظرية المعلومات ====