می‌توان  را به صورت  نیز نوشت که به صورت ضمنی بیان می‌کند دارای میانگین و واریانس زیر است:


در مورد اسکرمبلرهای ضربی نیز می‌توان از آزمون آماری طبق جدول ۳-۴ استفاده نمود. شایان ذکر است که متغیر  به کار برده شده در این آزمون آماری دارای احتمال برابر  است در صورتی‌که در مورد اسکرمبلرهای سنکرون این احتمال برابر با  می‌باشد، بنابراین در این حالت به بیت‌های کمتری احتیاج داریم. اما باید همه‌ی چندجمله‌ای‌های ممکن (نه فقط چندجمله‌ای‌های تکین) را تست کنیم. به منظور به حداقل رساندن زمان اجرای برنامه چندجمله‌ای هایی با حداکثر از درجه  در راستای افزایش وزن انتخاب می‌کنیم.
پایان نامه - مقاله - پروژه
از تجزیه و تحلیل ارائه شده در بخش ۳-۲ می توان نتیجه گرفت که تعداد بیت‌های موردنیاز برای شناسایی اسکرمبلر ضربی با حداکثر طول  برابر است با :

که در آن  و  می‌باشد. تعداد عملیات انجام شده توسط این الگوریتم برابر است با:

که در آن  وزن چندجمله‌ای فیدبک  می‌باشد. از آنجایی که افزایش وزن زمان اجرای برنامه را به صورت نمایی افزایش می‌دهد می توان اسکرمبلرهای خود-سنکرون کوتاه و آنهایی که چندجمله‌ای فیدبک تکین[۲۳] دارند را به صورت کارآمدتری شناسایی کرد. در بسیاری از کاربردهای عملی اسکرمبلرها دارای چندجمله‌ای فیدبک تکین می‌باشند که این الگوریتم در مورد آنها موثر می‌باشد. به عنوان مثال در  و در  چندجمله‌ای فیدبک اسکرمبلرهای خود-سنکرون یا ضربی دوجمله‌ای  و در  چندجمله‌ای فیدبک یک سه جمله‌ای به صورت  می‌باشد. اگرچه یافتن الگوریتمی کارآمد که پیچیدگی و تعداد عملیات آن به وابستگی زیادی به وزن چندجمله‌ای فیدبک  (همینطور در مورد اسکرمبلرهای جمعی) نداشته باشد به صورت مسئله‌ای که بیشتر جای تحقیق و بررسی دارد باقی می ماند.
جدول ‏۳‑۵ عملکرد الگوریتم کلوزیو با بایاس  [۶]

 

چندجمله‌ای فیدبک زمان اجرا با زمان اجرا با 
  ۱۳٫۰۲ s ۲min 53s
  ۵ min 18 s ۱۱min 26s
  ۱۴٫۰۱ s ۱۱day 4h
  << 1 s << 1 s
  << 1 s << 1 s

الگوریتم کلوزیو اصلاح شده
الگوریتم کلوزیو به جای اینکه به طور مستقیم به جستجو برای پیدا کردن چندجمله ای فیدبک  بپردازد به دنبال مضرب های پراکنده‌ای از چندجمله ای فیدبک  با تغییر درجه‌ی آنها از کم به زیاد می‌پردازد. پس از آنکه دو مضرب از  طی اجرای الگریتم شناسایی شد، بزرگترین مقسوم علیه مشترک  این دو مضرب به عنوان چندجمله ای فیدبک تعیین می شود. همان طور که قبلاً ذکر شد اینکه آیا چندجمله ای پراکنده مضربی از  می باشد یا خیر براساس آزمون فرضیه ای که روی قدر مطلق متغیر  انجام می شود تعیین می گردد. زمانی که  مضربی از  باشد خواهیم داشت:  چرا که  می باشد. چنانچه  مضربی از  باشد و بیت های ورودی  دارای بایاس  باشند  نیز دارای توزیعی با بایاس  خواهد بود و متغیر  دارای توزیع گوسی با میانگین و واریانس زیر خواهد بود:

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...