مقاله کامل ميدان گالوا

Low complexity sequential Normal Basis Multiplier Over GF(2m)
مقدمه:
در ابتدا اشاره‌اي كوتاه و جزئي به ميدانهاي گالوا (Galois field) داريم. ميدانهاي گالوا GF(p) مجموعه‌اي از p عنصر است كه جمع و تفريق، ضرب و تقسيم روي آن اعمال مي‌شود. بدون آنكه از آن مجموعه خارج شويم يعني ميدانها روي اين اعمال بسته هستند.[2]
ثابت مي‌شود براي هر عدد اول p و هر عدد صحيح ميداني خواهيم داشت از مرتبه pm را بصورت GF(pm) نمايش داده مي‌شود. اين ميدان براي هرچند جمله‌اي مولد يكتا است.
در واقع GF(pm) يك بردار m بعدي است روي GF(p). هرمجموعه mتايي كه نسبت به هم بطورخطي مستقل باشند را مي‌توان به عنوان پايه‌هاي GF(pm) در نظر گرفت. مثلاً اگر a ريشة چندجمله‌اي ساده نشدني مولد باشد مجموعه يك پايه براي GF(pm) خواهد بود.
پايه‌هاي مكمل (Complementary Basis):
پايه‌هاي و را روي GF(pm) در نظر بگيريد. درپايه فوق مكمل يا ارگان (dual) يكديگر خواهند بود اگر:

كه در آن
بعد از اين تعريف به پايه‌هاي نرمال (Normal Basis)NB مي‌رسيم. قبل از تعريف انواع NB ذكر قضيه Davenport ضروري بنظر مي‌رسد:
هر ميدان گالوا GF(pm) شامل يك عنصر اصلي است كه يك NB روي آن مي‌باشد. بنابراين قضيه مشخص شد كه اولاً هر ميدان گالوا GF(pm) داراي حداقل يك NB خواهد بود و ثانياً يك NB بفرم مي‌باشد. [1]
حال به تعريف دو نوع از NB مي‌پردازيم.
در عمل بيشتر از دو نوع NB استفاده مي‌كنيم: 1ـ ONB of type I 2ـ (ONB) optimal NB of type II
ONB of type I:
نوع اول ONB به وسيله ريشه‌هاي چندجمله‌اي ساده نشدني AOP al-one polynomialy بوجود مي‌آيند. يك AOP از درجه m به فرم زير مي‌باشد:
P(Z) = Zm+Zm-1+…+Z+1
AOP ساده نشدني است اگر m+1 اول باشد و p ريشه اصلي (primitive element) در ماژول m+1 باشد در اينصورت ريشه‌هاي معادله بالا يعني j=0,1,…m-1 و و ONB of type II را تشكيل مي‌دهند [3]
ONB of type II:
با يك مثال ONB of type II را بيان مي‌كنيم:
به ميدان GF(25) كه توسط چند جمله‌اي ساده نشدني ساخته شده، توجه كنيد. ريشه F(Z) مي‌باشد يعني فرض مي‌كنيم در اينصورت مجموعه ONB of type II خواهد بود.
در قسمت بعدي با استفاده از ماتريس حاصلضرب تعريف دقيقتري از ONB خواهيم ديد.
اگر NB براي GF(2m) روي GF(2) باشد، هر عنصر GF(2m) مثل قابل بيان است به فرم .
مهمترين مزيت استفاده از NB براي بيان عناصر مختلف GF(pm)، نشان دادن اين قضيه است كه: توان دوم هر عنصر A=GF(pm) به راحتي با يك واحد شيفت و بسمت راست بدست مي‌آيد. [4]

از آنجاييكه عمليات محاسباتي ميدانهاي گالوا بطور گسترده‌اي در كدهاي كنترل خطا و رمزنگاري مورد استفاده قرار مي‌گيرد، لذا پياده‌سازي سخت‌افزاري آنها با پيچيدگي كمتر مطلوب و مقرون به صرفه است. اين پيچيدگي به نمايش عناصر ميدان بستگي دارد به اين معنا كه اگر از روش
مناسبي براي بيان عناصر ميدان استفاده نكنيم ممكن است اين عمليات قابل پياده‌سازي سخت‌افزاري نباشد. بهترين و راحتترين روشها براي نمايش عناصر ميدان استفاده از NB است. [5]
ضرب كننده‌هاي NB هم مانند ساير ضرب كننده‌ها دو نوع سري و موازي دارند.
در ضرب كننده‌هاي موازي 2m ورودي دريافت مي‌شود و m بيت خروجي همزمان با هم پس از تأخير زماني گيتهاي مختلف مدار (اگر از مدار تركيبي استفاده كرده باشيم) و يا تاخير زماني دستيابي به حافظه (اگر از روش مدار تربيتي استفاده كرده باشيم) بدست خواهد آمد. كاملاً مشخص است كه چنين سيستمي احتياج به گيتهاي بيشتري دارد و بالطبع جاي بيشتري هم اشغال مي‌كند. و لذا چنين ضرب كننده‌اي در مصارف رمزنگاري هيچ كاربرديندارد چون در چنين كاربردهايي مقدار m بسيار زياد است (بطور مثال 4000).
دو نوع مختلف ضرب كننده سريال داريم. اگر خروجي بصورت parallel توليد شود SMPO و اگر بصورت سريال توليد شود SMSO خواهد بود.
1ـ SMSO: Sequential Multiplier Serial Catput
دو عنصر و را در نظر بگيريد A,B=GF(2m) حال اگر حاصلضرب A.B را C نام‌گذاري كنيم، خواهيم داشت. [3]

به بيان‌برداري

در واقع (Multiplicatio matrix) M
يك ماتريس مربعي m×m است كه درايه‌هاي آن را تشكيل مي‌دهد.
در ؟؟؟ ثابت شده است كه

كه در آن
براي اطلاعات بيشتر راجع به ماتريس M. منبع [6] پيشنهاد مي‌گردد.
تعداد يكهاي ماتريس M را با CN نمايش مي‌دهند كه نشان دهنده تعداد گيتها و بالطبع تاخير زماني ضرب كننده NB مي‌باشد. پرواضح است كه
. اگر از پايه‌هاي نرمال بهينه ONB (type I or II) استفاده كرده باشيم CN=2m-1.
در [5] نشان داده شده است كه اگر U(A,B) براي ساختن Cm-1 پياده‌سازي شود براي بدست آوردن ديگر عناصر C كافي است يك شيفت مناسب در وروديها بدهيم. يعني و اين همان چيزي است كه در بالا ناگفته شد.
Figure 1.a
دياگرام اين ضرب كننده را در شكل (1-a) فوق مشاهده مي‌كنيد. در حالت كلي تعداد گيتهاي AND و تعداد گيتهاي XOR به ترتيب برابر است با CN-1,CN و تأخير زماني بحراني هم خواهد بود كه در آن TA، TX هم تاخير زماني يك واحد گيت AND و گيت XOR مي‌باشد.
2ـ SMPO:
در اين ضرب كننده m بيت خروجي بعد از m، clock همزمان با سيم توليد مي‌شود در شكل 2-a مثالي از يك SMPO مشاهده مي‌كنيد. به عنوان يك مثال به GF(25) كه به وسيله F(Z)=Z5+Z2+1 درست شده است را در نظر بگيريد، ريشه F(Z) است. لذا ONB of type II به صورت تشكيل مي‌شود:
در اينصورت Ci يعني عنصر iام حاصلضرب از رابطه زير محاسبه مي‌گردد:

در واقع ترم اول يعني b0a1 داراي c0، ترم دوم يعني را براي c1 و نهايتاً ترم آخر يعني را براي c4 پياده‌سازي مي‌كنند. در اين نوع ضرب كننده تعداد گيتهاي AND، XOR به ترتيب برابر است با m، cn و تاخير زماني مسير بحراني هم برابر خواهد بود كه p ماكزيمم تعداد aI هاست كه قبل از آنكه با bI ضرب شود با XOR, aj مي‌شود. در واقع p ماكزيمم تعداد يكها در هر سطر يا در هر ستون ماتريس M مي‌باشد.
در ONB، P=2 خواهد بود. لذا تاخير زماني مسيربحراني برابر TA+2Tx مي‌شود. در ادامه به ارائه دو ساختار جديد SMPO مي‌پردازيم و در انتها نشان داده مي‌شود كه تعداد پارامترهاي اين دو ساختار نسبت به ساختارهاي موجود حال حاضر بهتر است.
ابتدا به فرمول‌بندي اين ضرب كننده‌ها مي‌پردازيم.

براي مقادير زوج m

قضيه:
3 عنصر A و B و C كه C=A.B را درنظر بگيريد. A.B.C GF(2m)

براساس همين قضيه، الگوريتم اين ضرب كننده به صورت زير بدست مي‌آيد.

for t=1 to m {
D = D2 + Fm-1 (xy)
x = x2 , y=y2 ,
}
C=D
F
نكته مهمي كه در اين الگوريتم وجود دارد اين است كه Fm-1 را يك تابع ثابت درنظر گرفته با وروديهاي متفاوت (برخلاف چيزي كه در صفحه پيش گفتيم) در واقع لذا اين نكته استفاده شده كه:
يعني بجاي آنكه از m تابع استفاده شود از يك تابع ثابت با وروديهاي متفاوت استفاده شده به همين دليل است كه در خط چهارم Y,X را به توان 2 رسانديم. دقت داشته باشيد كه توان دوم در هر ؟؟؟ يعني يك شيفت به سمت راست
پس از اين مقدمات رياضي به ساختار اين ضرب كننده مي‌پردازيم.
Figure 3-a
براي شروع ابتدا y,x بطور سريال داخل رجيسترها load مي‌شوند. داخل D هم صفر قرار مي‌گيرد تمام عمليات مربوط به D2+Fm-1 در Z-Array انجام مي‌شود و براي مرحله بعد هم y=y2.x=x2 يك شيفت مناسب ايجاد مي‌كند. در واقع Z-Array شامل v بلوك از بلوكهاي Z است كه در شكل 3-b، 3-c به ازاي g=1 و g=0 نشان داده شده است. AND اضافي كه در شكل 3-a مشاهده مي‌كنيد براي حالتي است كه m زوج باشد چون در اين حالت مي‌خواهيم z توليد شود.
از اينجا به بعد به ضرب كننده‌هايي با g=1 ESMPO × (XOR Eficient SMPO) m-1,v و با g=0 (AND Eficient SMPO) AESMPO گفته مي‌شود.
كاملاً مشخص است كه در Z-Array براي XESMPO، v گيت XOR و (m-1) گيت AND خواهيم داشت و براي AESMPO، v گيت AND، (m-1) گيت AND.
و در حالت كلي (منظور زماني است كه از هيچ ترم مشترك دوبار استفاده نكنيم) ماكزيمم تعداد گيتها در XOR Array برابر خواهد بود با كه تعداد مولفه‌هاي غيرصفر در است. هنگامي كه آنرا بر حسب پايه‌هاي نرمالش توصيف كرده باشيم. (البته اگر m زوج باشد، اين مقدار كاهش پيدا مي‌كند)
و از آنجاييكه [10]

بنابراين مي‌توان نتيجه گرفت كه تعداد گيتهاي XOR در XOR Array در حالت ماكزيمم برابر است با 0.5(CN+1) لذا:

فایل : 16 صفحه

فرمت : Word