ETRI-Knowledge Sharing Plaform

KOREAN
논문 검색
Type SCI
Year ~ Keyword

Detail

Journal Article New Block Recombination for Subquadratic Space Complexity Polynomial Multiplication Based on Overlap-Free Approach
Cited 3 time in scopus Download 5 time Share share facebook twitter linkedin kakaostory
Authors
Sun-Mi Park, Ku-Young Chang, Dowon Hong, Changho Seo
Issue Date
2017-08
Citation
IEEE Transactions on Computers, v.66, no.8, pp.1396-1406
ISSN
0018-9340
Publisher
IEEE
Language
English
Type
Journal Article
DOI
https://dx.doi.org/10.1109/TC.2017.2669998
Project Code
17ZH1700, Develpoment of storage and search technologies over encrypted database, Ku Young Chang
Abstract
In this paper, we present new parallel polynomial multiplication formulas which result in subquadratic space complexity. The schemes are based on a recently proposed block recombination of polynomial multiplication formula. The proposed two-way, three-way, and four-way split polynomial multiplication formulas achieve the smallest space complexities. Moreover, by providing area-time tradeoff method, the proposed formulas enable one to choose a parallel formula for polynomial multiplication which is suited for a design environment.
KSP Keywords
Overlap-free, Polynomial multiplication, Space Complexity, Split polynomial, Three-way, design environment, four-way, two-way