A low-complexity LUT-based squaring algorithm

Te Jen Chang; Chia Long Wu; Der Chyuan Lou; Ching Yin Chen

doi:10.1016/j.camwa.2008.11.018

A low-complexity LUT-based squaring algorithm

Te Jen Chang^*, Chia Long Wu, Der Chyuan Lou, Ching Yin Chen

^*Corresponding author for this work

Research output: Contribution to journal › Journal Article › peer-review

3 Scopus citations

Abstract

The computation of large modular multi-exponentiation is a time-consuming arithmetic operation used in cryptography. The standard squaring algorithm is well-known and the Guajardo-Paar algorithm fixes the improper carry handling bug produced by the standard squaring algorithm, but produces error-indexing bug. In this paper, a novel squaring algorithm is proposed, which stores base products in the Look-Up Table before the squaring computation and base size comparison method. The proposed algorithm can not only evaluate squaring efficiently but also avoid bugs produced in other proposed algorithms (the Guajardo-Paar algorithm and the Yang-Heih-Laih algorithm). The performance of the proposed algorithm is 1.615 times faster than the standard squaring algorithm and much faster than other algorithms.

Original language	English
Pages (from-to)	1494-1501
Number of pages	8
Journal	Computers and Mathematics with Applications
Volume	57
Issue number	9
DOIs	https://doi.org/10.1016/j.camwa.2008.11.018
State	Published - 05 2009
Externally published	Yes

Keywords

Fast algorithm design
Information security
Modular multiplication
Public-key cryptosystem
Squaring

Access to Document

10.1016/j.camwa.2008.11.018

Cite this

@article{3f54c29e169d411698f43369a1b9ccb1,

title = "A low-complexity LUT-based squaring algorithm",

abstract = "The computation of large modular multi-exponentiation is a time-consuming arithmetic operation used in cryptography. The standard squaring algorithm is well-known and the Guajardo-Paar algorithm fixes the improper carry handling bug produced by the standard squaring algorithm, but produces error-indexing bug. In this paper, a novel squaring algorithm is proposed, which stores base products in the Look-Up Table before the squaring computation and base size comparison method. The proposed algorithm can not only evaluate squaring efficiently but also avoid bugs produced in other proposed algorithms (the Guajardo-Paar algorithm and the Yang-Heih-Laih algorithm). The performance of the proposed algorithm is 1.615 times faster than the standard squaring algorithm and much faster than other algorithms.",

keywords = "Fast algorithm design, Information security, Modular multiplication, Public-key cryptosystem, Squaring",

author = "Chang, {Te Jen} and Wu, {Chia Long} and Lou, {Der Chyuan} and Chen, {Ching Yin}",

year = "2009",

month = may,

doi = "10.1016/j.camwa.2008.11.018",

language = "英语",

volume = "57",

pages = "1494--1501",

journal = "Computers and Mathematics with Applications",

issn = "0898-1221",

publisher = "Elsevier Ltd",

number = "9",

}

TY - JOUR

T1 - A low-complexity LUT-based squaring algorithm

AU - Chang, Te Jen

AU - Wu, Chia Long

AU - Lou, Der Chyuan

AU - Chen, Ching Yin

PY - 2009/5

Y1 - 2009/5

N2 - The computation of large modular multi-exponentiation is a time-consuming arithmetic operation used in cryptography. The standard squaring algorithm is well-known and the Guajardo-Paar algorithm fixes the improper carry handling bug produced by the standard squaring algorithm, but produces error-indexing bug. In this paper, a novel squaring algorithm is proposed, which stores base products in the Look-Up Table before the squaring computation and base size comparison method. The proposed algorithm can not only evaluate squaring efficiently but also avoid bugs produced in other proposed algorithms (the Guajardo-Paar algorithm and the Yang-Heih-Laih algorithm). The performance of the proposed algorithm is 1.615 times faster than the standard squaring algorithm and much faster than other algorithms.

AB - The computation of large modular multi-exponentiation is a time-consuming arithmetic operation used in cryptography. The standard squaring algorithm is well-known and the Guajardo-Paar algorithm fixes the improper carry handling bug produced by the standard squaring algorithm, but produces error-indexing bug. In this paper, a novel squaring algorithm is proposed, which stores base products in the Look-Up Table before the squaring computation and base size comparison method. The proposed algorithm can not only evaluate squaring efficiently but also avoid bugs produced in other proposed algorithms (the Guajardo-Paar algorithm and the Yang-Heih-Laih algorithm). The performance of the proposed algorithm is 1.615 times faster than the standard squaring algorithm and much faster than other algorithms.

KW - Fast algorithm design

KW - Information security

KW - Modular multiplication

KW - Public-key cryptosystem

KW - Squaring

UR - http://www.scopus.com/inward/record.url?scp=63049100730&partnerID=8YFLogxK

U2 - 10.1016/j.camwa.2008.11.018

DO - 10.1016/j.camwa.2008.11.018

M3 - 文章

AN - SCOPUS:63049100730

SN - 0898-1221

VL - 57

SP - 1494

EP - 1501

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

IS - 9

ER -

A low-complexity LUT-based squaring algorithm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this