Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Bipartite modular multiplication method
 
research article

Bipartite modular multiplication method

Kaihara, Marcelo E.
•
Takagi, Naofumi
2008
Ieee Transactions On Computers

This paper proposes a new modular multiplication method that uses Montgomery residues defined by a modulus M and a Montgomery radix R whose value is less than the modulus M. This condition enables the operand multiplier to be split into two parts that can be processed separately in parallel-increasing the calculation speed. The upper part of the split multiplier can be processed by calculating a product modulo M of the multiplicand and this part of the split multiplier. The lower part of the split multiplier can be processed by calculating a product modulo M of the multiplicand, this part of the split multiplier, and the inverse of a constant R. Two different implementations based on this method are proposed: One uses a classical modular multiplier and a Montgomery multiplier and the other generates partial products for each part of the split multiplier separately, which are added and accumulated in a single pipelined unit. A radix-4 version of a multiplier based on a radix-4 classical modular multiplier and a radix-4 Montgomery multiplier has been designed and simulated. The proposed method is also suitable for software implementation in a multiprocessor environment.

  • Details
  • Metrics
Type
research article
DOI
10.1109/TC.2007.70793
Web of Science ID

WOS:000251686300002

Author(s)
Kaihara, Marcelo E.
Takagi, Naofumi
Date Issued

2008

Published in
Ieee Transactions On Computers
Volume

57

Start page

157

End page

164

Subjects

computer arithmetic

•

hardware algorithm

•

modular multiplication

•

Montgomery multiplication

•

Computer Algorithm

•

Hardware Algorithm

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
IC  
Available on Infoscience
November 30, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/61672
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés