رياضيات الحقول المنتهية
رياضيات الحقول المنتهية Finite field arithmetic، إذا الحساب في الحقول المنتهية مختلف عن الحساب القياسي الذي نتعامل به مع الأعداد السليمة. فهناك عدد محدد من العناصر في الحقل المنتهي, فكل عملية يتم اجراؤها في الحقل المنتهي تكون نتيجتها عنصر من هذا الحقل. هناك عدد غير منتهي من الحثول المنتهية, والتي تكون عناصرها بالضرورة من الشكل pn حيث p عدد أولي وn عدد حقيقي موجب. ندعوp بمميِّز الحقل, وn بُعد الحقل.
تستخدم الحقول المنتهية بالكثير من التطبيقات, مثل خوارزميات التشفير كما في خوارزمية Rijndael.
التمثيل الفعّال لكثيرات الحدود
الحقل المنتهي باعناصر pn يرمز له بالرمز GF(pn) ويدعى بحقل كالويس Galois Fiel وذلك تكريماً لـِ Évariste Galois الذي عثر نظرية الحقل المنتهي. GF(p) هي ببساطة حلقة من العناصر الحقيقية والتي هي نواتج باقي قسمة أي عدد على p, حيث p عدد أولي. لذلك نحن بامكاننا اجراء العمليات (جمع, طرح, ضرب) كما نجريها بالطريقة العادية, متبوعة باختصار الناتج عن طريق تطبيق ناتج باقي قسمته على p. فمن أجل الحالة GF(5), لدينا أربعة + ثلاثة =سبعة يتم اختزاله الى 2 وهوناتج باقي قسمةسبعة على 5. أما بالنسبة لعملية القسمة فيمكن اجراؤها بتطبيق عملية معاكس الضرب, والذي يمكن حسابه باستخدام خوارزمية اقليدس الممددة.
الجمع والطرح
يمكن انجاز الجمع والطرح وذلك بجمع وطرح كثيري الحدود مع بعضهما, ثم نقوم باختزال النتيجة بحساب باقي قسمة النتاتج على مميِّز الحقل المنتهي. مثلاً في الحقل المنتهي ذوالمميز 2, عمليتي الجمع والطرح متطابقتين, ويمكن انجاز أي منهما باستخدام العملية XOR. لذلك:
- كثير الحدود: (x6 + x4 + x + 1) + (x7 + x6 + x3 + x) = x7 + x4 + x3 + 1
- النظام الثنائي: {01010011 + {11001010 = {10011001
لاحظ أنه بالجمع النظامي لكثيرات الحدود يجب حتى تتضمن النتيجة الحد 2x6 ,ولكن بهذه الطريقة كانت النتيجة 0x6 بسبب اجراء عملية باقي القسمة على 2 للنتيجة. وهذا جدول يبين النتيجة طالما الجمع النظامي ,والنيجة طالما الجمع بطريقة الحقول المنتهية بالمميّز 2 في كثيرات الحدود:
| p1 | p2 | p1 + p2 (الجمع العادي) | p1 + p2 بصيغة GF(2n) |
| x3 + x + 1 | x3 + x2 | 2x3 + x2 + x + 1 | x2 + x + 1 |
| x4 + x2 | x6 + x2 | x6 + x4 + 2x2 | x6 + x4 |
| x + 1 | x2 + 1 | x2 + x + 2 | x2 + x |
| x3 + x | x2 + 1 | x3 + x2 + x + 1 | x3 + x2 + x + 1 |
| x2 + x | x2 + x | 2x2 + 2x | 0 |
ملاحظة: في تطبيقات فهم الحاسوب يتم اجراء هذه العمليات بالحقل المنتهي ذي المميز 2, ويدعى GF(2n ,وذلك يجعل هذا الحقل هوالخيار الشائع للتطبيقات.
الضرب
الحقل المنتهي لـِ Rijndael
الضرب العكسي
الحقول المنتهية البدائية
مثال برمجي
هذا جزء من برنامج بلغة C يقوم بجمع وطرح وضرب الأعداد في الحقل المنتهي لـِ Rijndael:
/* Add two numbers in a GF(2^8) finite field */
uint8_t gadd(uint8_t a, uint8_t b) {
return a ^ b;
/* Subtract two numbers in a GF(2^8) finite field */
uint8_t gsub(uint8_t a, uint8_t b) {
return a ^ b;
/* Multiply two numbers in the GF(2^8) finite field defined
* by the polynomial x^8 + x^4 + x^3 + x + 1 */
uint8_t gmul(uint8_t a, uint8_t b) {
uint8_t p = 0;
uint8_t counter;
uint8_t hi_bit_set;
for(counter = 0; counter < 8; counter++) {
if(b & 1)
p ^= a;
hi_bit_set = (a & 0x80);
a <<= 1;
if(hi_bit_set)
a ^= 0x11b; /* x^8 + x^4 + x^3 + x + 1 */
b >>= 1;
return p;
ملاحظة: هذا الكود ضعيف بتوقيت الهجمات (هجمات الاختراق) عند استخدامه بالتشفير.
وصلات خارجية
- A description of Rijndael's finite field
- Galois Field Arithmetic Library C++
