ATE316668T1 - Fliessbandkern in einem montgomery-multiplizierer - Google Patents

Fliessbandkern in einem montgomery-multiplizierer

Info

Publication number
ATE316668T1
ATE316668T1 AT02788303T AT02788303T ATE316668T1 AT E316668 T1 ATE316668 T1 AT E316668T1 AT 02788303 T AT02788303 T AT 02788303T AT 02788303 T AT02788303 T AT 02788303T AT E316668 T1 ATE316668 T1 AT E316668T1
Authority
AT
Austria
Prior art keywords
montgomery
multipler
belt core
assembly belt
long integer
Prior art date
Application number
AT02788303T
Other languages
English (en)
Inventor
Gerardus T M Hubert
Original Assignee
Koninkl Philips Electronics Nv
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
Application filed by Koninkl Philips Electronics Nv filed Critical Koninkl Philips Electronics Nv
Application granted granted Critical
Publication of ATE316668T1 publication Critical patent/ATE316668T1/de

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/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/724—Finite field arithmetic
    • 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/728—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 using Montgomery reduction
    • 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/52—Multiplying; Dividing
    • G06F7/523—Multiplying only
    • G06F7/533—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even
    • G06F7/5334—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product
    • G06F7/5336—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product overlapped, i.e. with successive bitgroups sharing one or more bits being recoded into signed digit representation, e.g. using the Modified Booth Algorithm
    • G06F7/5338—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product overlapped, i.e. with successive bitgroups sharing one or more bits being recoded into signed digit representation, e.g. using the Modified Booth Algorithm each bitgroup having two new bits, e.g. 2nd order MBA
    • 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/724—Finite field arithmetic
    • G06F7/725—Finite field arithmetic over elliptic curves

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)
  • Mathematical Physics (AREA)
  • General Engineering & Computer Science (AREA)
  • Computing Systems (AREA)
  • Complex Calculations (AREA)
  • Molds, Cores, And Manufacturing Methods Thereof (AREA)
  • Sink And Installation For Waste Water (AREA)
  • Image Generation (AREA)
  • Escalators And Moving Walkways (AREA)
  • External Artificial Organs (AREA)
AT02788303T 2001-12-14 2002-12-05 Fliessbandkern in einem montgomery-multiplizierer ATE316668T1 (de)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
EP01204908 2001-12-14

Publications (1)

Publication Number Publication Date
ATE316668T1 true ATE316668T1 (de) 2006-02-15

Family

ID=8181444

Family Applications (1)

Application Number Title Priority Date Filing Date
AT02788303T ATE316668T1 (de) 2001-12-14 2002-12-05 Fliessbandkern in einem montgomery-multiplizierer

Country Status (8)

Country Link
US (1) US7395295B2 (de)
EP (1) EP1459167B1 (de)
JP (1) JP4619657B2 (de)
CN (1) CN100382011C (de)
AT (1) ATE316668T1 (de)
AU (1) AU2002353282A1 (de)
DE (1) DE60208926T2 (de)
WO (1) WO2003052584A2 (de)

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7240204B1 (en) * 2000-03-31 2007-07-03 State Of Oregon Acting By And Through The State Board Of Higher Education On Behalf Of Oregon State University Scalable and unified multiplication methods and apparatus
WO2003021423A2 (en) * 2001-09-04 2003-03-13 Microunity Systems Engineering, Inc. System and method for performing multiplication
DE60208926T2 (de) * 2001-12-14 2006-08-31 Koninklijke Philips Electronics N.V. Fliessbandkern in einem montgomery-multiplizierer
US7266577B2 (en) * 2002-05-20 2007-09-04 Kabushiki Kaisha Toshiba Modular multiplication apparatus, modular multiplication method, and modular exponentiation apparatus
FI115862B (fi) * 2002-11-06 2005-07-29 Nokia Corp Menetelmä ja järjestelmä kertolaskuoperaation suorittamiseksi ja laite
US7532720B2 (en) * 2003-10-15 2009-05-12 Microsoft Corporation Utilizing SIMD instructions within montgomery multiplication
US7664810B2 (en) * 2004-05-14 2010-02-16 Via Technologies, Inc. Microprocessor apparatus and method for modular exponentiation
KR100670780B1 (ko) * 2004-10-29 2007-01-17 한국전자통신연구원 유한체 ＧＦ（２＾ｍ）에서의 하이브리드 곱셈 연산 장치및 연산 방법
FR2884005B1 (fr) * 2005-04-01 2007-06-01 Thales Sa Methode d'implementation de la multiplication modulaire de montgomery et son dispositif
US8645448B2 (en) 2010-12-03 2014-02-04 Via Technologies, Inc. Carryless multiplication unit
US8667040B2 (en) 2010-12-03 2014-03-04 Via Technologies, Inc. Mechanism for carryless multiplication that employs booth encoding
TWI489375B (zh) * 2010-12-03 2015-06-21 Via Tech Inc 無進位乘法裝置及其處理方法
US8635262B2 (en) * 2010-12-03 2014-01-21 Via Technologies, Inc. Carryless multiplication preformatting apparatus and method
CN105373366B (zh) * 2015-10-12 2018-11-09 武汉瑞纳捷电子技术有限公司 一种生成大素数的方法及装置
CN116166219B (zh) * 2022-12-19 2026-03-31 成都三零嘉微电子有限公司 一种可配置模乘法器

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5513133A (en) * 1992-11-30 1996-04-30 Fortress U&T Ltd. Compact microelectronic device for performing modular multiplication and exponentiation over large numbers
JP2000132376A (ja) * 1998-10-27 2000-05-12 Fujitsu Ltd 剰余演算方法，乗算剰余演算方法，剰余演算装置，乗算剰余演算装置及び記録媒体
AU3286399A (en) * 1998-12-18 2000-07-12 Motorola, Inc. Circuit and method of cryptographic multiplication
JP2000353077A (ja) * 1999-04-07 2000-12-19 Matsushita Electric Ind Co Ltd 多倍長演算装置
US7240204B1 (en) * 2000-03-31 2007-07-03 State Of Oregon Acting By And Through The State Board Of Higher Education On Behalf Of Oregon State University Scalable and unified multiplication methods and apparatus
JP2001296993A (ja) * 2000-04-12 2001-10-26 Toyo Commun Equip Co Ltd 有限体上の乗算回路
DE60208926T2 (de) * 2001-12-14 2006-08-31 Koninklijke Philips Electronics N.V. Fliessbandkern in einem montgomery-multiplizierer
DE10260660B3 (de) * 2002-12-23 2004-06-09 Infineon Technologies Ag Modulare Multiplikation mit paralleler Berechnung der Look-Ahead-Parameter u.a. bei der kryptographischen Berechnung
DE10260655B3 (de) * 2002-12-23 2004-06-24 Infineon Technologies Ag Vorrichtung und Verfahren zum Berechnen einer Multiplikation mit einer Verschiebung des Multiplikanden, insbesondere bei der kryptographischen Berechnung

Also Published As

Publication number Publication date
JP2005513532A (ja) 2005-05-12
DE60208926T2 (de) 2006-08-31
US20050033790A1 (en) 2005-02-10
AU2002353282A1 (en) 2003-06-30
EP1459167A2 (de) 2004-09-22
EP1459167B1 (de) 2006-01-25
WO2003052584A2 (en) 2003-06-26
AU2002353282A8 (en) 2003-06-30
JP4619657B2 (ja) 2011-01-26
CN100382011C (zh) 2008-04-16
CN1605059A (zh) 2005-04-06
US7395295B2 (en) 2008-07-01
DE60208926D1 (de) 2006-04-13
WO2003052584A3 (en) 2004-05-21

Similar Documents

Publication Publication Date Title
DE60208926D1 (de) Fliessbandkern in einem montgomery-multiplizierer
Dang et al. High-speed hardware architectures and FPGA benchmarking of CRYSTALS-Kyber, NTRU, and Saber
TW200500940A (en) Simd integer multiply high with round and shift
FI118612B (fi) Menetelmä ja järjestelmä laskuoperaatioiden suorittamiseksi ja laite
Esmaeildoust et al. Efficient RNS Implementation of Elliptic Curve Point Multiplication Over ${\rm GF}(p) $
McIntosh et al. A search for Fibonacci-Wieferich and Wolstenholme primes
DE60237108D1 (de) Galoisfeld-multiplikation/multiplikation-addition/multiplikation-akkumulierung
WO2001093012A3 (en) Accelerated montgomery exponentiation using plural multipliers
ATE344487T1 (de) Reduzierung von komponenten in einer montgomery multiplikations-recheneinheit
ATE484789T1 (de) Multiplikator
Rashidi A survey on hardware implementations of elliptic curve cryptosystems
EP0660245A3 (de) Arithmetische Maschine
DE50209713D1 (de) Verfahren und vorrichtung zum modularen multiplizieren und rechenwerk zum modularen multiplizieren
Roy et al. Tile before multiplication: An efficient strategy to optimize DSP multiplier for accelerating prime field ECC for NIST curves
Shu et al. FPGA accelerated Tate pairing based cryptosystems over binary fields
DE602004004642D1 (de) Mikrowellen- oder radiofrequenz-vorrichtung enthaltend drei entkoppelten generatoren
AU2003289909A1 (en) Device and method for calculating a multiplication involving a shifting of the multiplicand
JP2012239171A5 (de)
Rashidi Efficient hardware implementations of point multiplication for binary Edwards curves
Bondalapati Parallelizing DSP nested loops on reconfigurable architectures using data context switching
Rashidi Low-cost and fast hardware implementations of point multiplication on binary edwards curves
Kumar et al. Small area reconfigurable FFT design by Vedic Mathematics
Javeed et al. A compact and low latency SPM architecture for ECC cryptosystems
Karp Speeding up N‐body Calculations on Machines without Hardware Square Root
FI115862B (fi) Menetelmä ja järjestelmä kertolaskuoperaation suorittamiseksi ja laite

Legal Events

Date Code Title Description
RER Ceased as to paragraph 5 lit. 3 law introducing patent treaties