Name
Abstract | ||
|---|---|---|
This paper presents new speed records for multiprecision multiplication on the AVR ATmega family of 8-bit microcontrollers. For example, our software takes only 1,969 cycles for the multiplication of two 160-bit integers; this is more than 15 % faster than that demonstrated in previous work. For 256-bit inputs, our software is not only the first to break through the 6,000-cycle barrier; with only 4,771 cycles it also breaks through the 5,000-cycle barrier and is more than 21 % faster than previous work. We achieve these speed records by carefully optimizing the Karatsuba multiplication technique for AVR ATmega. One might expect that subquadratic-complexity Karatsuba multiplication is only faster than algorithms with quadratic complexity for large inputs. This paper shows that it is in fact faster than fully unrolled product-scanning multiplication already for surprisingly small inputs, starting at 48 bits. Our results thus make Karatsuba multiplication the method of choice for high-performance implementations of elliptic-curve cryptography on AVR ATmega microcontrollers. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s13389-015-0093-2 | IACR Cryptology ePrint Archive |
Keywords | DocType | Volume |
Karatsuba multiplication, Microcontroller, ATmega | Journal | 5 |
Issue | ISSN | Citations |
3 | 2190-8516 | 11 |
PageRank | References | Authors |
0.65 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Hutter | 1 | 345 | 25.26 |
| Peter Schwabe | 2 | 759 | 44.16 |