# US 2003/0200246 A1 · Modular multiplication method and calculating device

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2003/0200246 A1
- Document ID: US20030200246A1
- Status: Published application
- Kind: A1
- Application number: 10/282,107
- Filed: 2002-10-29
- Published: 2003-10-23
- Earliest claimed: 2002-04-19
- Assignees: Oki Electric Industry Co., Ltd.
- Inventors: Hiroshi Yamazaki
- Web page: https://patentgrep.com/patent/US20030200246A1

## CPC

- G06F 7/729: {using representation by a residue number system}
- G06F 7/727: {Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5 (G06F7/728 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

To provide a modular multiplication method and a calculating device that do not rely on the Montgomery technique, wherein the number of times of multiply-add calculations is reduced to shorten a calculation time for calculation speed-up, there is no limitation in input value, and it is possible to execute a remainder calculation exceeding the calculable maximum bit length of a multiply-add unit that is used. Assuming that N=2n−M and X=α×2n+β, a relation of XmodN=(α×M+β)modN is derived, which is utilized. n represents a maximum bit number where “1” is assigned in N, a solution of 2n+1modN is set as b, A×B is set as X, XmodN is transferred to (X/2n+1×b+Xmod2n+1)modN and further transferred to (X·n/2n+1×b+X·nmod2n+1)modN, calculations of X·n/2n+1×b+X·nmod2n+1 are repeated until a bit length of X·n becomes n+1, X·n−N is derived and a derived result is set as a solution of “A×BmodN”.

## Claims

### Claim 1

A modular multiplication method for deriving a solution of “A×BmodN”, said method comprising:
a first step of setting a maximum bit number where “1” is assigned in N as n, deriving 2n+1modN and setting a solution thereof as b;
a second step of deriving A×B and setting a solution thereof as X;
a third step of transferring XmodN to
(X/2n+1×b+Xmod2n+1)modN;
a fourth step of transferring
(X/2n+1×b+Xmod2n+1)modN
to
(X·n/2n+1×b+X·nmod2n+1)modN
and repeating calculations of
X·n/2n+1×b+X·nmod2n+1
until a bit length of X·n becomes n+1; and
a fifth step of deriving X·n−N and setting a derived result as the solution of “A×BmodN”.

### Claim 2

A modular multiplication method for deriving a solution of “A×BmodN”, said method comprising:
a first step of setting a maximum bit number where “1” is assigned in N as n, deriving 2n+1modN and setting a solution thereof as b;
a second step of deriving A×B and setting a solution thereof as X;
a third step of transferring 2n+mmodN to
(2n+m/2n+1×b+2n+mmod2n+1)modN
and setting a solution thereof as b·m;
a fourth step of transferring XmodN to
(X·n/2n+m×b·m+X·nmod2n+m)modN
and repeating calculations of
X·n/2n+m×b·m+X·nmod2n+m
until a bit length of X·n becomes n+m, and setting a solution thereof as X′;
a fifth step of transferring X′modN to
(X′·n/2n+1×b+X′·nmod2n+1)modN
and repeating calculations of
X′·n/2n+1×b+X′·nmod2n+1
until a bit length of X′·n becomes n+1; and
a sixth step of deriving X′·n−N and setting a derived result as the solution of “A×BmodN”.

### Claim 3

A modular multiplication method for deriving a solution of “A×BmodN”, said method comprising:
a first step of setting a maximum bit number where “1” is assigned in N as s, deriving 2s+1modN and setting a solution thereof as b;
a second step of deriving A×B and setting a solution thereof as X;
a third step of setting a bit length of X as n(n>s), transferring X to
XH×2n−s+XL(n−s<s)
and, based on this, transferring XmodN to
(XH×2n−s+XL)modN
and further transferring it to
((XH×2n−s+XL)+(XLmodN))modN
and setting a solution thereof as XH′;
a fourth step of transferring XH′modN to
(XH′/2s+1×b+XH′mod2s+1)modN
and repeating multiply-add calculations until a bit length of XH′ becomes s+1, and setting a solution thereof as bH;
a fifth step of deriving XLmodN by subtraction and setting a solution thereof as bL; and
a sixth step of deriving (bH+bL)modN and setting a derived result as the solution of “A×BmodN”.

### Claim 4

A multiply-add calculating device for calculating “A×B+C”, said device comprising:
an Am memory, a Bm memory, a Cm1 memory and a Cm2 memory each blocked per given bits and storing A value data, B value data and C value data, respectively;
an Ar register, a Br register and a Cr register for receiving data from said Am, Bm, Cm1 and Cm2 memories, respectively;
a multiply-add unit for calculating Ar×Br+Cr based on data stored in the Ar, Br and Cr registers;
an Hr register for storing upper bits of a result of the calculation by said multiply-add unit, and an Lr register for storing lower bits thereof; and
two selectors disposed on an input and an output side of said Cm1 memory and Cm2 memory for controlling an input/output relative to said Cm1 memory or Cm2 memory,
wherein the contents of said Lr register are stored into said Cm2 memory or Cm1 memory, and said Am memory,
the contents of said Hr register are stored into said Cm1 memory or Cm2 memory, and
said Cm1 memory and Cm2 memory are used alternately per calculation.
