# US 2004/0083251 A1 · Parallel modulo arithmetic using bitwise logical operations

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

- Number: US 2004/0083251 A1
- Document ID: US20040083251A1
- Status: Published application
- Kind: A1
- Application number: 10/296,957
- Filed: 2003-11-18
- Published: 2004-04-29
- Earliest claimed: 2000-06-01
- Inventors: Felix Egmont Geiringer; Daniel Shelton
- Web page: https://patentgrep.com/patent/US20040083251A1

## CPC

- G06F 7/724: {Finite field arithmetic (for error detection or correction in general H03M13/00, in computers G06F11/10)}
- H04L 9/002: {Countermeasures against attacks on cryptographic mechanisms (network architectures or network communication protocols for protection against malicious traffic H04L63/1441)}
- H04L 9/0662: {with particular pseudorandom sequence generator}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L 2209/125: Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
- H04L 2209/20: Manipulating the length of blocks of bits, e.g. padding or block truncation
- H04L 2209/34: Encoding or coding, e.g. Huffman coding or error correction
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Parallel modulo arithmetic calculations are carried out on a device adapted to perform bitwise logical operations by storing the numbers to be operated upon in a vector form, and performing arithmetical operations on multiple numbers in parallel. The invention finds particular application in cryptosystems, as well as in other fields.

## Claims

### Claim 1

A method of carrying out parallel modulo arithmetic calculations on a device adapted to perform bitwise logical operations, comprising:
(a) representing a series of numerical values (X) to be operated upon, by respective bitwise vectors;
(b) forming a first word (X˜0) from one bit of each of the said vectors, and a second word (X1) from another bit of each of the said vectors; and
(c) performing bitwise logical operations on one or both of the words.

### Claim 2 (depends on 1)

A method as claimed in claim 1 including:
(d) representing a series of further numerical values (y), to be operated upon, by respective bitwise vectors;
(e) forming another first word (Y˜0) from said one bit of each of said vectors, and another second word (Y1) from said another bit of each of the said vectors; and
(f) performing bitwise operations on both the respective first words (X˜0, Y˜0) or on both the respective second words (X1, Y1).

### Claim 3 (depends on 1)

A method as claimed in claim 1 in which the first word (X˜0) is stored in one location and the second word (X1) in another separate location.

### Claim 4 (depends on 2)

A method as claimed in claim 2 in which the respective first words (X˜0, Y˜0) are stored together in one location and the respective second words (X1, Y1) in another separate location.

### Claim 5 (depends on 1)

A method as claimed in claim 1 in which the numerical values (x) to be operated upon are in modulo 3.

### Claim 6 (depends on 1)

A method as claimed in claim 1 in which the further numerical values (y) to be operated upon are in modulo 3.

### Claim 7 (depends on 5, 6)

A method as claimed in claim 5 and claim 6 including calculating the sums (mod 3) of respective pairs of values (xi, y1) from the series of numerical values (x) and the further values (y) by determining Z˜0 and Z1 as follows:
Z1=(X˜0 XOR Y1) AND (X1 XOR Y˜0),Z˜0=(X˜0 XOR Y˜0) OR (X1 AND Y1) OR Z1
where Z˜0 is a word representing one bit of the result, and Z1 is a word representing another bit of the result.

### Claim 8 (depends on 5, 6)

A method as claimed in claim 5 and claim 6 including calculating the results of subtracting (mod 3) respective pairs of values (xi, yi) from the series of numerical values (x) and the further values (y) by determining Z˜0 and Z1 as follows:
Z˜0=(X˜0 XOR Y˜0) OR (X1 XOR Y1),Z1=(Y˜0 XOR X1) AND ((NOT Y1) OR X˜0) AND Z˜0.
where Z˜0 is a word representing one bit of the result, and Z1 is a word representing another bit of the result.

### Claim 9 (depends on 5, 6)

A method as claimed in claim 5 and claim 6 including calculating the results of multiplying (mod 3) respective pairs of values (xi, yi) from the series of numerical values (x) and the further values (y) by determining Z˜0 and Z1 as follows:
Z˜0=(X˜0 AND Y˜0),Z1=(NOT (X1 XOR Y1)) AND Z˜0.
where Z˜0 is a word representing one bit of the result, and Z1 is a word representing another bit of the result.

### Claim 10 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9)

A method of encryption including the step of carrying out a method as claimed in any one of claims 1 to 9.

### Claim 11 (depends on 1, 2, 3, 4, 5, 6, 7, 8, 9)

A method of decryption including the step of carrying out a method as claimed in any one of claims 1 to 9.

### Claim 12 (depends on 1, 2)

A method of encryption including generating a key by adding, subtracting or multiplying polynomials having coefficients which are in modulo N (N≧3), using a method as claimed in claim 1 or claim 2, the coefficients of a first polynomial comprising the series of numerical values (x) and the coefficients of a second polynomial comprising the series of further numerical values (y).

### Claim 13 (depends on 12)

A method as claimed in claim 12 in which N=3.

### Claim 14 (depends on 1, 2)

A method of decryption including adding, subtracting or multiplying polynomials having coefficients which are in modulo N (N≧3), using a method as claimed in claim 1 or claim 2, the coefficients of a first polynomial comprising the series of numerical values (x) and the coefficients of a second polynomial comprising the series of further numerical values (y).

### Claim 15 (depends on 14)

A method as claimed in claim 14 in which N=3.

### Claim 16

A computer program for carrying out a method as claimed in any one of the preceding claims.

### Claim 17 (depends on 16)

A physical carrier carrying a computer program as claimed in claim 16.

### Claim 18 (depends on 16)

A datastream representative of a computer program as claimed in claim 16.

### Claim 19

A digital device for carrying out parallel modulo arithmetic calculations by means of bitwise logical operations, comprising:
(a) means for representing a series of numerical values (x) to be operated upon, by respective bitwise vectors;
(b) means for forming a first word (X˜0) from one bit of each of the said vectors, and a second word (X1) from another bit of each of the said vectors; and
(c) means for performing bitwise logical operations on one or both of the words.

### Claim 20 (depends on 19)

A device as claimed in claim 19 including:
(d) means for representing a series of further numerical values (y), to be operated upon, by respective bitwise vectors;
(e) means for forming another first word (Y˜0) from said one bit of each of said vectors, and another second word (Y1) from said another bit of each of the said vectors; and
(f) means for performing bitwise operations on both the respective first words (X˜0, Y˜0) or on both the respective second words (X1, Y1).

### Claim 21 (depends on 19, 20)

A device as claimed in claim 19 or claim 20 including storage means at one location for storing the first word, and storage means at another location for storing the second word.

### Claim 22 (depends on 19, 20)

A device as claimed in claim 19 or claim 20 including storage means in one location for storing, together, the respective first words, and storage means in another location for storing, together, the respective second words.
