Parallel modular multiplication on multi-core processors

被引：12

作者：

Giorgi, Pascal ^{[1
]}

Imbert, Laurent ^{[1
]}

Izard, Thomas ^{[2
]}

机构：

[1] UM2, CNRS, LIRMM, Montpellier, France

[2] SILKAN, Montpellier, France

来源：

2013 21ST IEEE SYMPOSIUM ON COMPUTER ARITHMETIC (ARITH) | 2013年

关键词：

Modular multiplication; bipartite; tripartite; k-ary multipartite algorithms; parallel arithmetic; multi-core;

D O I：

10.1109/ARITH.2013.20

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Current processors typically embed many cores running at high speed. The main goal of this paper is to assess the efficiency of software parallelism for low level arithmetic operations by providing a thorough comparison of several parallel modular multiplications. Famous methods such as Barrett, Montgomery as well as more recent algorithms are compared together with a novel k-ary multipartite multiplication which allows to split the computations into independent processes. Our experiments show that this new algorithm is well suited to software parallelism.

引用

页码：135 / 142

页数：8

共 13 条

[1]

[Anonymous], 2016, HDB APPL CRYPTOGRAPH

[2]

[Anonymous], 2010, Modern Computer Arithmetic, DOI DOI 10.1017/CBO9780511921698

[3]

[Anonymous], GMP GNU MULTIPLE PRE

[4]

BARRETT P, 1987, LECT NOTES COMPUT SC, V263, P311

[5]

Bernstein D, 2008, FAST MULTIPLICATION, V44, P325

[6] Bipartite modular multiplication method [J].

Kaihara, Marcelo E. ;

Takagi, Naofumi .

IEEE TRANSACTIONS ON COMPUTERS, 2008, 57 (02) :157-164

[7]

Karatsuba A., 1963, Sov. Phys. Doklady, V7, P595

[8] Analyzing and comparing Montgomery multiplication algorithms [J].

Koc, CK ;

Acar, T ;

Kaliski, BS .

IEEE MICRO, 1996, 16 (03) :26-33

[9]

MONTGOMERY PL, 1985, MATH COMPUT, V44, P519, DOI 10.1090/S0025-5718-1985-0777282-X

[10] Tripartite modular multiplication [J].

Sakiyama, Kazuo ;

Knezevic, Miroslav ;

Fan, Junfeng ;

Preneel, Bart ;

Verbauwhede, Ingrid .

INTEGRATION-THE VLSI JOURNAL, 2011, 44 (04) :259-269

← 1 2 →