رياضيات الحقول المنتهية

رياضيات الحقول المنتهية Finite field arithmetic، إن الحساب في الحقول المنتهية مختلف عن الحساب القياسي الذي نتعامل به مع الأعداد الصحيحة. فهناك عدد محدد من العناصر في الحقل المنتهي, فكل عملية يتم اجراؤها في الحقل المنتهي تكون نتيجتها عنصر من هذا الحقل. هناك عدد غير منتهي من الحثول المنتهية, و التي تكون عناصرها بالضرورة من الشكل pⁿ حيث p عدد أولي و n عدد حقيقي موجب. ندعو p بمميِّز الحقل, و n بُعد الحقل.

تستخدم الحقول المنتهية بالعديد من التطبيقات, مثل خوارزميات التشفير كما في خوارزمية Rijndael.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 التمثيل الفعّال لكثيرات الحدود

الحقل المنتهي باعناصر pⁿ يرمز له بالرمز GF(pⁿ) و يدعى بحقل كالويس Galois Fiel وذلك تكريماً لـِ Évariste Galois الذي وجد نظرية الحقل المنتهي. GF(p) هي ببساطة حلقة من العناصر الحقيقية والتي هي نواتج باقي قسمة أي عدد على p, حيث p عدد أولي. لذلك نحن بامكاننا اجراء العمليات (جمع, طرح, ضرب) كما نجريها بالطريقة العادية, متبوعة باختصار الناتج عن طريق تطبيق ناتج باقي قسمته على p. فمن أجل الحالة GF(5), لدينا 4 + 3 = 7 يتم اختزاله الى 2 و هو ناتج باقي قسمة 7 على 5. أما بالنسبة لعملية القسمة فيمكن اجراؤها بتطبيق عملية معاكس الضرب, و الذي يمكن حسابه باستخدام خوارزمية اقليدس الممددة.

 الجمع و الطرح

يمكن انجاز الجمع و الطرح و ذلك بجمع و طرح كثيري الحدود مع بعضهما, ثم نقوم باختزال النتيجة بحساب باقي قسمة النتاتج على مميِّز الحقل المنتهي. مثلاً في الحقل المنتهي ذو المميز 2, عمليتي الجمع و الطرح متطابقتين, و يمكن انجاز أي منهما باستخدام العملية XOR. لذلك:

كثير الحدود: (x⁶ + x⁴ + x + 1) + (x⁷ + x⁶ + x³ + x) = x⁷ + x⁴ + x³ + 1

النظام الثنائي: {01010011} + {11001010} = {10011001}

لاحظ أنه بالجمع النظامي لكثيرات الحدود يجب أن تتضمن النتيجة الحد 2x⁶ ,و لكن بهذه الطريقة كانت النتيجة 0x⁶ بسبب اجراء عملية باقي القسمة على 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(2ⁿ ,و ذلك يجعل هذا الحقل هو الخيار الشائع للتطبيقات.

 مثال برمجي

هذا جزء من برنامج بلغة 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++