2015 | OriginalPaper | Chapter
Reverse Product-Scanning Multiplication and Squaring on 8-Bit AVR Processors
Authors : Zhe Liu, Hwajeong Seo, Johann Großschädl, Howon Kim
Published in: Information and Communications Security
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
add
instructions. We also describe an optimized algorithm for multi-precision squaring based on the RPS technique that is, depending on the operand length, up to 44.3 % faster than multiplication. Our AVR Assembly implementations of RPS multiplication and RPS squaring occupy less than 1 kB of code space each and are written in a parameterized fashion so that they can support operands of varying length without recompilation. Despite this high level of flexibility, our RPS multiplication outperforms the looped variant of Hutter et al.’s operand-caching technique and saves between 40 and 51 % of code size. We also combine our RPS multiplication and squaring routines with Karatsuba’s method to further reduce execution time. When executed on an ATmega128 processor, the “karatsubarized RPS method” needs only 85 k clock cycles for a 1024-bit multiplication (or 48 k cycles for a squaring). These results show that it is possible to achieve high performance without sacrificing code size or scalability.