CA2008774A1 - Methode de multiplication modulaire et systeme connexe de traitement des donnees - Google Patents

Methode de multiplication modulaire et systeme connexe de traitement des donnees

Info

Publication number
CA2008774A1
CA2008774A1 CA2008774A CA2008774A CA2008774A1 CA 2008774 A1 CA2008774 A1 CA 2008774A1 CA 2008774 A CA2008774 A CA 2008774A CA 2008774 A CA2008774 A CA 2008774A CA 2008774 A1 CA2008774 A1 CA 2008774A1
Authority
CA
Canada
Prior art keywords
modular
multiplicand
denotes
partial
range
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CA2008774A
Other languages
English (en)
Other versions
CA2008774C (fr
Inventor
Hikaru Morita
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Inc
Original Assignee
Individual
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from JP1017700A external-priority patent/JPH02199532A/ja
Priority claimed from JP1147795A external-priority patent/JP2812365B2/ja
Priority claimed from JP20697389A external-priority patent/JP2790327B2/ja
Application filed by Individual filed Critical Individual
Publication of CA2008774A1 publication Critical patent/CA2008774A1/fr
Application granted granted Critical
Publication of CA2008774C publication Critical patent/CA2008774C/fr
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/4824—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices using signed-digit representation
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/722—Modular multiplication

Landscapes

  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Complex Calculations (AREA)
CA002008774A 1989-01-30 1990-01-29 Methode de multiplication modulaire et systeme connexe de traitement des donnees Expired - Fee Related CA2008774C (fr)

Applications Claiming Priority (6)

Application Number Priority Date Filing Date Title
JP1-17700 1989-01-30
JP1017700A JPH02199532A (ja) 1989-01-30 1989-01-30 剰余乗算の方法および回路
JP1147795A JP2812365B2 (ja) 1989-06-09 1989-06-09 乗算回路
JP1-147795 1989-06-09
JP1-206973 1989-08-11
JP20697389A JP2790327B2 (ja) 1989-08-11 1989-08-11 剰余乗算回路および剰余乗算方法

Publications (2)

Publication Number Publication Date
CA2008774A1 true CA2008774A1 (fr) 1990-07-30
CA2008774C CA2008774C (fr) 1999-10-05

Family

ID=27281933

Family Applications (1)

Application Number Title Priority Date Filing Date
CA002008774A Expired - Fee Related CA2008774C (fr) 1989-01-30 1990-01-29 Methode de multiplication modulaire et systeme connexe de traitement des donnees

Country Status (4)

Country Link
US (1) US5073870A (fr)
EP (1) EP0381161B1 (fr)
CA (1) CA2008774C (fr)
DE (1) DE69032811T2 (fr)

Families Citing this family (33)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5270956A (en) * 1991-03-18 1993-12-14 University Of Maryland System and method for performing fast algebraic operations on a permutation network
US5274707A (en) * 1991-12-06 1993-12-28 Roger Schlafly Modular exponentiation and reduction device and method
WO1993020503A1 (fr) * 1992-04-07 1993-10-14 Thomson Consumer Electronics S.A. Procede et appareil pour calcul modulo
US5513133A (en) * 1992-11-30 1996-04-30 Fortress U&T Ltd. Compact microelectronic device for performing modular multiplication and exponentiation over large numbers
US5349551A (en) * 1993-07-30 1994-09-20 The United States Of America As Represented By The Director Of National Security Agency Device for and method of preforming an N-bit modular multiplication in approximately N/2 steps
FR2726667B1 (fr) * 1994-11-08 1997-01-17 Sgs Thomson Microelectronics Procede de mise en oeuvre de multiplication modulaire selon la methode montgomery
CN1085862C (zh) * 1996-09-20 2002-05-29 张胤微 高速模乘法装置
US5793659A (en) * 1996-10-15 1998-08-11 United Microelectronics Corporation Method of modular reduction and modular reduction circuit
KR100218683B1 (ko) * 1996-12-04 1999-09-01 정선종 정보 보호용 모듈러 승산 장치
KR100684134B1 (ko) * 1997-05-04 2007-02-16 엠시스템스 리미티드 몽고메리 승산에 기초한 모듈의 승산 및 누승을 위한 개선된 장치와 방법
US6748410B1 (en) 1997-05-04 2004-06-08 M-Systems Flash Disk Pioneers, Ltd. Apparatus and method for modular multiplication and exponentiation based on montgomery multiplication
US6144740A (en) * 1998-05-20 2000-11-07 Network Security Technology Co. Method for designing public key cryptosystems against fault-based attacks with an implementation
US7269261B1 (en) 1999-09-22 2007-09-11 Raytheon Company Key escrow systems
US6925563B1 (en) 1999-09-22 2005-08-02 Raytheon Company Multiplication of modular numbers
DE60139401D1 (de) 2000-05-15 2009-09-10 Sandisk Il Ltd Erweiterung des bereichs rechnerischer körper von ganzen zahlen
US6954772B2 (en) * 2000-08-28 2005-10-11 Sun Microsystems, Inc Method and apparatus for performing modular division
KR100436814B1 (ko) * 2001-12-20 2004-06-23 한국전자통신연구원 아이씨카드용 알에스에이 암호 연산 장치
DE10219158B4 (de) * 2002-04-29 2004-12-09 Infineon Technologies Ag Vorrichtung und Verfahren zum Berechnen eines Ergebnisses einer modularen Multiplikation
US7558817B2 (en) 2002-04-29 2009-07-07 Infineon Technologies Ag Apparatus and method for calculating a result of a modular multiplication
DE10223853B4 (de) * 2002-05-28 2005-06-23 Technische Universität Braunschweig Carolo-Wilhelmina Verfahren und integrierte Schaltung zur Durchführung einer Multiplikation modulo M
KR100459732B1 (ko) * 2002-12-30 2004-12-03 삼성전자주식회사 4-2 컴프레서를 이용한 몽고메리 모듈러 승산기 및 그승산 방법
SG115534A1 (en) * 2003-04-04 2005-10-28 St Microelectronics Asia Method and apparatus for performing modular arithmetic
US20040252829A1 (en) * 2003-04-25 2004-12-16 Hee-Kwan Son Montgomery modular multiplier and method thereof using carry save addition
FR2859030B1 (fr) * 2003-08-21 2005-11-04 Gemplus Card Int Procede de realisation d'une multiplication modulaire et procede de realisation d'une multiplication euclidienne sur des nombres de 2n bits
JP4180024B2 (ja) * 2004-07-09 2008-11-12 Ｎｅｃエレクトロニクス株式会社 乗算剰余演算器及び情報処理装置
JP4170267B2 (ja) * 2004-07-09 2008-10-22 Ｎｅｃエレクトロニクス株式会社 乗算剰余演算器及び情報処理装置
DE102006025713B9 (de) * 2005-10-28 2013-10-17 Infineon Technologies Ag Kryptographie-Vorrichtung und Kryptographie-Verfahren zum Berechnen eines Ergebnisses einer modularen Multiplikation
DE102006025569A1 (de) * 2005-10-28 2007-05-03 Infineon Technologies Ag Vorrichtung und Verfahren zum Berechnen einer Multiplikations-Additions-Operation und zum Berechnen eines Ergebnisses einer modularen Multiplikation
DE102006025677B4 (de) * 2005-10-28 2020-03-12 Infineon Technologies Ag Vorrichtung und Verfahren zum Berechnen eines Ergebnisses einer Summe mit einem Rechenwerk mit begrenzter Wortlänge
DE102006025673B9 (de) 2005-10-28 2010-12-16 Infineon Technologies Ag Rechenwerk zum Reduzieren einer Eingabe-Zahl bezüglich eines Moduls
US8073892B2 (en) * 2005-12-30 2011-12-06 Intel Corporation Cryptographic system, method and multiplier
DE102014222825A1 (de) * 2014-11-07 2016-05-12 Ihp Gmbh - Innovations For High Performance Microelectronics / Leibniz-Institut Für Innovative Mikroelektronik Vorrichtung und Verfahren zur Multiplikation zur Erschwerung von Seitenkanalangriffen
RU2019121710A (ru) * 2016-12-12 2021-01-12 Конинклейке Филипс Н.В. Электронное вычислительное устройство, выполненное с возможностью вычисления произведения целых чисел

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS54144148A (en) * 1978-05-01 1979-11-10 Aisuke Katayama Exponential conversion type high speed multiplying system
JPS6042965B2 (ja) * 1979-06-01 1985-09-26 愛介 片山 複数法形高速乗算装置

Also Published As

Publication number Publication date
CA2008774C (fr) 1999-10-05
EP0381161B1 (fr) 1998-12-09
DE69032811T2 (de) 1999-04-29
EP0381161A2 (fr) 1990-08-08
DE69032811D1 (de) 1999-01-21
US5073870A (en) 1991-12-17
EP0381161A3 (fr) 1992-03-25

Similar Documents

Publication Publication Date Title
EP0381161A3 (fr) Procédé et système de multiplication modulaire
JPH0235348B2 (fr)
CA2310418A1 (fr) Appareil pour arithmetique multiprecision d'entiers
US4598382A (en) Multiplying circuit
GB2103401A (en) Digital filter circuits
CA2119283A1 (fr) Circuit de multiplication et circuit de division
EP0247383A3 (fr) Appareil de traitement arithmétique
CA2229157A1 (fr) Multiplicateurs de l'arbre de wallace utilisant des additionneurs complets et des demi-additionneurs
US5497343A (en) Reducing the number of carry-look-ahead adder stages in high-speed arithmetic units, structure and method
EP0811909B1 (fr) Circuit arithméthique pour calculer la racine carrée d'une somme de carrés
JPH0477932B2 (fr)
WO1991018355A1 (fr) Interpolateur integre et methode de fonctionnement
JPH09212485A (ja) ２次元ｉｄｃｔ回路
US6347326B1 (en) N bit by M bit multiplication of twos complement numbers using N/2+1 X M/2+1 bit multipliers
US6415311B1 (en) Sign extension circuit and method for unsigned multiplication and accumulation
US20050004965A1 (en) Logarithmic arithmetic system
US6167422A (en) Booth multiplication structure which selectively integrates the function of either of incrementing or negating with the function of booth multiplication
JPH0260005B2 (fr)
JP3078696B2 (ja) 逆数演算装置
CA2205525A1 (fr) Circuit multiplicateur et circuit diviseur
JP2820701B2 (ja) ２進数への変換方法
JP2753922B2 (ja) 固定小数点除算方法
JPH04153827A (ja) ディジタル乗算器
JP3087177B2 (ja) 浮動小数点計算方法およびその計算処理装置
JPS6484375A (en) Method for computing sum of products

Legal Events

Date Code Title Description
EEER Examination request
MKLA Lapsed