Кіріспе
Позитивті бүтін сандармен дәрежелеу әдісі, көбейтулердің ең аз санымен қамтамасыз етеді. Математика мен компьютерлік ғылымда оптималды қосу тізбегі арқылы дәрежелеу – бұл оң санның оң бүтін дәрежесін дәрежелеу әдісі, ол көбейтулердің ең аз санын қажет етеді. Қосудың орнына көбейтуді пайдаланып, ең қысқа қосу тізбегінің форматында, негіздің қажетті дәрежесін (көптеудің орнына) есептейді. (Бұл сәйкес келеді.) Тізбектегі әрбір дәрежелеуді екі бұрынғы дәрежелеу нәтижесін көбейту арқылы есептеуге болады. Жалпы алғанда, қосу тізбегі арқылы дәрежелеу әртүрлі алгоритмдермен құрастырылған минималды емес қосу тізбектері арқылы дәрежелеуге сілтеме жасай алады (өйткені ең қысқа қосу тізбегін табу өте қиын). Ең қысқа қосу тізбегі алгоритмі екілік дәрежелеуден артық көбейтуді қажет етпейді және көбінесе одан аз. Оның жақсырақ жұмыс істейтін алғашқы мысалы – a15, онда екілік әдіс алты көбейтуді қажет етеді, ал ең қысқа қосу тізбегіне тек бесеуі ғана керек: (екілік, 6 көбейту) (ең қысқа қосу тізбегі, 5 көбейту). (сондай-ақ ең қысқа қосу тізбегі, 5 көбейту). Кесте дәрежелеуді қосу тізбектерін пайдаланып қалай жасауға болады, мысалы: Көбейтулер саны Нақты дәрежелеу Қосу тізбектерін пайдаланып дәрежелеуді жүзеге асырудың нақты мысалы 0 a1 a1 a2 a × a2 a3 a × a × a2 a4 (a × a→b) × b3 a5 (a × a→b) × b × a3 a6 (a × a→b) × b × b4 a7 (a × a→b) × b × b × a3 a8 ((a × a→b) × b→d) × d4 a9 (a × a × a→c) × c × c4 a10 ((a × a→b) × b→d) × d × b5 a11 ((a × a→b) × b→d) × d × b × a4 a12 ((a × a→b) × b→d) × d × d5 a13 ((a × a→b) × b→d) × d × d × a5 a14 ((a × a→b) × b→d) × d × d × b5 a15 ((a × a→b) × b × a→e) × e × e4 a16 (((a × a→b) × b→d) × d→h) × h. Екінші жағынан, ең қысқа қосу тізбегін анықтау қиын: кез келген дәреже үшін тиімді оптималды әдістер қазіргі уақытта белгілі емес, ал берілген дәрежелер жиыны үшін ең қысқа қосу тізбегін табуға қатысты мәселе NP-толық екені дәлелденген. Ең қысқа тізбек берілген жағдайда да, қосу тізбегі арқылы дәрежелеу екілік әдіске қарағанда көбірек жадты қажет етеді, өйткені ол тізбектің көптеген бұрынғы дәрежелерін сақтауы керек. Сондықтан практикада ең қысқа қосу тізбегі арқылы дәрежелеу көбінесе ең қысқа тізбегі алдын ала есептелетін және тым үлкен емес кішкентай тұрақты дәрежелер үшін қолданылады. Ең қысқа қосу тізбегін жуықтаудың бірнеше әдістері де бар, олар көбінесе екілік дәрежелеуге қарағанда аз көбейтуді қажет етеді; екілік дәрежелеудің өзі оңтайлы емес қосу тізбегі алгоритмі болып табылады. Оптималды алгоритмді таңдау контекстке байланысты (мысалы, көбейтудің салыстырмалы құны және берілген дәреже қайта қолданылатын саны). Ең қысқа қосу тізбегін табу мәселесін динамикалық бағдарламалау арқылы шешуге болмайды, өйткені ол оңтайлы субструктураның болжамын қанағаттандырмайды. Яғни, қуатты кіші қуаттарға бөлшектеу жеткіліксіз, олардың әрқайсысы минималды есептеледі, өйткені кіші қуаттар үшін қосу тізбектері байланысты болуы мүмкін (есептеулерді бөлісу үшін). Мысалы, жоғарыда a15 үшін ең қысқа қосу тізбегінде a6 үшін қосалқы мәселе (a3)2 ретінде есептелуі керек, өйткені a3 қайта пайдаланылады (мысалы, a6 = a2(a2)2-ге қарама-қарсы, ол да үш көбейтуді қажет етеді).
In mathematics and computer science, optimal addition chain exponentiation is a method of exponentiation by a positive integer power that requires a minimal number of multiplications. Using the form of the shortest addition chain, with multiplication instead of addition, computes the desired exponent (instead of multiple) of the base. (This corresponds to .) Each exponentiation in the chain can be evaluated by multiplying two of the earlier exponentiation results. More generally, addition chain exponentiation may also refer to exponentiation by non minimal addition chains constructed by a variety of algorithms (since a shortest addition chain is very difficult to find). The shortest addition chain algorithm requires no more multiplications than binary exponentiation and usually less. The first example of where it does better is for a15, where the binary method needs six multiplications but the shortest addition chain requires only five:
(binary, 6 multiplications)
(shortest addition chain, 5 multiplications). (also shortest addition chain, 5 multiplications). +Table demonstrating how to do exponentiation using addition chainsNumber ofmultiplications Actualexponentiation Specific implementation ofaddition chains to do exponentiation0 a1 a1 a2 a × a2 a3 a × a × a2 a4 (a × a→b) × b3 a5 (a × a→b) × b × a3 a6 (a × a→b) × b × b4 a7 (a × a→b) × b × b × a3 a8 ((a × a→b) × b→d) × d4 a9 (a × a × a→c) × c × c4 a10 ((a × a→b) × b→d) × d × b5 a11 ((a × a→b) × b→d) × d × b × a4 a12 ((a × a→b) × b→d) × d × d5 a13 ((a × a→b) × b→d) × d × d × a5 a14 ((a × a→b) × b→d) × d × d × b5 a15 ((a × a→b) × b × a→e) × e × e4 a16 (((a × a→b) × b→d) × d→h) × h
On the other hand, the determination of a shortest addition chain is hard: no efficient optimal methods are currently known for arbitrary exponents, and the related problem of finding a shortest addition chain for a given set of exponents has been proven NP complete. Even given a shortest chain, addition chain exponentiation requires more memory than the binary method, because it must potentially store many previous exponents from the chain. So in practice, shortest addition chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be pre computed and is not too large. There are also several methods to approximate a shortest addition chain, and which often require fewer multiplications than binary exponentiation; binary exponentiation itself is a suboptimal addition chain algorithm. The optimal algorithm choice depends on the context (such as the relative cost of the multiplication and the number of times a given exponent is re used). The problem of finding the shortest addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations). For example, in the shortest addition chain for a15 above, the subproblem for a6 must be computed as (a3)2 since a3 is re used (as opposed to, say, a6 = a2(a2)2, which also requires three multiplies).
Қосу-сақтау тізбекті экспонентациялау
Егер көбейту мен бөлуге рұқсат берілсе, онда қосу-азайту тізбегін жалпы көбейтулер мен бөлулер санын тіпті азайту үшін қолдануға болады (мұнда азайту бөлуге сәйкес келеді). Дегенмен, көбейтуге қарағанда бөлудің баяу болуы бұл әдісті көбінесе тиімсіз етеді. Ал теріс бүтін дәрежеге қабаттау үшін, бір бөлу қажет болғандықтан, қосу-азайту тізбегі көбінесе тиімді болады. Мысалы, a⁻³¹ үшін, a³¹ үшін ең қысқа қосу тізбегі арқылы 1/a³¹ есептеуге 7 көбейту және 1 бөлу қажет, ал ең қысқа қосу-азайту тізбегіне 5 көбейту және 1 бөлу жеткілікті: (қосу-азайту тізбегі, 5 көбейту + 1 бөлу). Эллипстік қисықтардағы қабаттау үшін, (x, y) нүктесінің керісі қосымша есептеуді қажет етпейді, себебі ол жай ғана (x, −y) болып табылады, сондықтан қосу-азайту тізбектері оң бүтін дәрежелер үшін де осы жағдайда ең жақсы нұсқа болып табылады.
(addition subtraction chain, 5 mults + 1 div). For exponentiation on elliptic curves, the inverse of a point (x, y) is available at no cost, since it is simply (x, −y), and therefore addition subtraction chains are optimal in this context even for positive integer exponents.