# US 2002/0059353 A1 · Methods and apparatus for incomplete modular arithmetic

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

- Number: US 2002/0059353 A1
- Document ID: US20020059353A1
- Status: Published application
- Kind: A1
- Application number: 09/895,835
- Filed: 2001-06-29
- Published: 2002-05-16
- Earliest claimed: 2000-06-29
- Assignees: State of Oregon acting by and through the State Board of Higher Education on behalf of Oregon State University
- Inventors: Cetin K. Koc; Tugrul Yanik; Erkay Savas
- Web page: https://patentgrep.com/patent/US20020059353A1

## CPC

- G06F 7/72: using residue arithmetic
- G06F 7/722: {Modular multiplication (G06F7/724, G06F7/727, G06F7/728 take precedence)}
- G06F 7/728: {using Montgomery reduction}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and apparatus for modular arithmetic operations with respect to a modulus p include representing operands as a series of s w-bit numbers, wherein 1 s = ⌈ k w ⌉ . Operations are executed word by word and a carry, borrow, or other bit or word is obtained from operations on most significant words of the operands. Depending on the value of this bit or word, an operation-specific correction factor is applied. Cryptographic systems include computer executable instructions for such methods. Bit-level operations are generally avoided and the methods and apparatus are applicable to systems based on, for example, public-key cryptographic algorithms defined over the finite field CF(p).

## Claims

### Claim 1

A method of performing modular arithmetic with respect to a modulus p, comprising:
representing operands A, B as respective series of s w-bit words;
performing at least one of the operations of addition, subtraction, and multiplication based on the series of words of the operands to obtain a result C; and
reducing the result C so that C is less than or equal to p−1 and greater than or equal to 0.

### Claim 2 (depends on 1)

A computer readable medium containing instructions for performing the method of claim 1.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
defining a set of incompletely reduced numbers based on the word size w and the modulus p; and
performing the operation so that intermediate values used to obtain the result C are incompletely reduced numbers.

### Claim 4

A modular addition method, comprising:
representing a first operand and a second operand as a first and a second series of words, respectively, wherein the first and the second operands have the same or different values;
performing a series of word additions between corresponding words of the first and second operands to obtain a first intermediate sum;
evaluating a carry value associated with a sum of most significant words of the operands; and
based on the evaluation of the carry value, adding a correction factor for addition to the first intermediate sum to produce a second intermediate sum.

### Claim 5 (depends on 4)

The method of claim 4, further comprising representing the correction factor for addition as a series of words, wherein the step of adding the correction factor to the first intermediate sum is performed word by word.

### Claim 6 (depends on 5)

The method of claim 5, wherein the correction factor for addition is F=2m−Ip, wherein m is a maximum number of bits in the words that represent the operands, and I is a largest integer such that F is between 1 and p−1.

### Claim 7 (depends on 5)

The method of claim 5, further comprising: evaluating a carry value associated with a sum of most significant words of the first intermediate sum and the correction factor; and
adding the correction factor for addition to the second intermediate sum based on the evaluation.

### Claim 8 (depends on 7)

A computer readable medium containing computer executable instructions for performing the method of claim 7.

### Claim 9

A method of performing modular subtraction with respect to a modulus p, comprising
representing a first operand and a second operand as a first and a second series of words, respectively, wherein the first and the second operands have the same or different values;
performing a series of word subtractions between corresponding words of the first and second operands to obtain a first intermediate difference;
evaluating borrow value associated with a difference of most significant words of the operands; and
adding a correction factor for subtraction to the first intermediate difference based on the evaluation of the borrow value to produce a second intermediate difference.

### Claim 10 (depends on 9)

The method of claim 9, wherein the correction factor for subtraction is G=Jp−2m, wherein m is a maximum number of bits used to represent an operand and J is a smallest integer such that G is between 1 and p−1.

### Claim 11

A method of Montgomery multiplication, comprising:
representing a first operand and a second operand as a first series and a second series of s w-bit words, respectively;
selecting a Montgomery radix R=2sw; and
multiplying corresponding words of the first and second operands to form word products; and
processing the word products to obtain a Montgomery product.

### Claim 12

A transaction server, comprising:
an input configured to receive an authentication code; and
a processor configured to receive and confirm the authentication code, the processor including a word-wise, incomplete modular arithmetic module.

### Claim 13 (depends on 12)

The transaction server of claim 12, wherein the arithmetic module includes computer executable instructions stored in a computer readable medium.

### Claim 14 (depends on 12)

The transaction server of claim 12, where the processor is configured to process words of length w, and the arithmetic module is configured based on the word length w.

### Claim 15 (depends on 12)

The transaction server of claim 12, wherein the arithmetic module is configured to perform arithmetic modulo a prime number p and the arithmetic module is configured to process operands represented as s w-bit words, wherein
14 s = ⌈ k w ⌉ .

### Claim 16 (depends on 15)

The transaction server of claim 15, wherein the arithmetic module includes memory configured for storage of a correction factor for addition.

### Claim 17

A cryptographic system, comprising a processor that includes a word-wise, incompletely-reduced-number arithmetic module.

### Claim 18 (depends on 17)

The cryptographic system of claim 17, wherein the arithmetic module is configured to process a cryptographic parameter using addition modulo-p, wherein p is a prime number.

### Claim 19 (depends on 17)

The cryptographic system of claim 17, wherein the arithmetic module is configured to process a cryptographic parameter using subtraction modulo-p, wherein p is a prime number.

### Claim 20 (depends on 17)

The method of claim 17, wherein the arithmetic module is configured to process a cryptographic parameter using Montgomery multiplication with respect to a modulus p, wherein p is a prime number.

### Claim 21

A method of processing a security parameter with respect to a modulus p, the method comprising:
representing the security parameter as a series of s w-bit words;
processing the security parameter word by word to produce a processed value, wherein the processed value is between 0 and 2sw−1; and
producing an output by combining the processed value with a correction factor.

### Claim 22

A scalable method of processing a cryptographic parameter, comprising:
selecting a word length w;
selecting a modulus p;
representing the cryptographic parameter as a series of s w-bit words, wherein
15 s = ⌈ k w ⌉ ;
and
processing the cryptographic parameter word by word to produce an intermediate value that is represented as an incompletely reduced number.

### Claim 23 (depends on 22)

The method of claim 22, further comprising:
evaluating a carry or borrow value produced with a most significant word of the cryptographic parameter; and
applying a correction factor based on the carry or borrow value.
