مروری بر رو شهای ارائه شده برای یافتن زنجیره های افزونه کوتاه

زنجیره افزونه برای یک عدد مانند ، دنباله ای از اعداد صحیح است که از یک شروع شده و با e خاتمه می یابد. هر جمله زنجیره از جمع جمله ی قبل با خودش و یا جمله های قبل تر به دست می.آید زنجیره افزونه دنباله صحیحی ازضرب های مورد نیاز برای عملیات به توان رساندن را فراهم میکند به همین خاطر کاربرد زیادی در رمزنگاری کدهای تصحیح خطا و غیره دارد طول زنجیره افزونه به صورت تعداد اعداد موجود در دنباله به جز عدد اول تعریف میشود پس هر چه طول زنجیره کوتاه تر باشد تعداد عملیات در عمل توان رسانی کمتر می.شود مهمترین مساله در توان رسانی زنجیره افزونه پیدا کردن کوتاه ترین زنجیره است این استدلال وجود دارد که پیدا کردن کوتاه ترین زنجیره افزونه یک مساله NP-complete است روشهای مختلفی برای پیدا کردن زنجیره افزونه برای یک عدد وجود دارد، اما روشی مناسب است که زنجیره افزونه کوتاه را به دست آورد به طور کلی دو روش برای به دست آوردن زنجیره افزونه وجود دارد (۱) روشهای کلاسیک یا قطعی و (۲ روشهای تصادفی این مقاله مروری بر روشهای ارایه شده برای یافتن زنجیره افزونه داشته و طول زنجیره های به دست آمده توسط این روشها با هم مقایسه میشود.