مقدمه:
در ابتدا اشاره‌ای کوتاه و جزئی به میدانهای گالوا (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 است که درایه‌های آن را تشکیل می‌دهد.