# US 2005/0038845 A1 · Device and method for calculating a result of a division

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

- Number: US 2005/0038845 A1
- Document ID: US20050038845A1
- Status: Published application
- Kind: A1
- Application number: 10/917,262
- Filed: 2004-08-12
- Published: 2005-02-17
- Earliest claimed: 2002-02-12
- Assignees: Infineon Technologies AG
- Inventors: Wieland Fischer
- Web page: https://patentgrep.com/patent/US20050038845A1

## CPC

- G06F 7/72: using residue arithmetic
- G06F 7/535: Dividing only
- G06F 2207/7261: Uniform execution, e.g. avoiding jumps, or using formulae with the same power profile
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A device for calculating a result or an integer multiple of the result of a division of a numerator by a denominator includes a unit for providing a factor which is selected such that a product of the factor and the denominator is greater than the result. The device further includes a unit for modularly reducing a first product of the numerator and the factor using a modulus equaling a sum of a second product of the denominator and the factor and of an integer to obtain an auxiliary quantity having the result. A unit is used to extract the result or the integer multiple of the result from the auxiliary quantity. A division is thus reduced to a modular reduction and an extraction which is uncomplicated as far as calculation is concerned so that, in particular in long-number division tasks, the speed on the one hand and the safety on the other hand are increased.

## Claims

### Claim 1

A device for calculating a result or an integer multiple of the result of a division of a numerator by a denominator within a cryptographic algorithm, wherein the numerator and the denominator are parameters in the cryptographic algorithm, comprising:
a unit for providing a factor selected such that a product of the factor and the denominator is greater than the result;
a unit for modularly reducing a first product of the numerator and the factor using a modulus equaling a sum of a second product of the denominator and the factor and of an integer to obtain an auxiliary quantity comprising the result; and
a unit for extracting the result or the integer multiple of the result from the auxiliary quantity.

### Claim 2 (depends on 1)

The device according to claim 1, wherein the unit for providing is formed to determine the factor in such a way that a base raised to the power of an auxiliary quantity equals the factor.

### Claim 3 (depends on 2)

The device according to claim 2, wherein the base is 2 so that the multiplication by the factor corresponds to a shift by a number of positions in a register, wherein the number of positions equals the auxiliary quantity.

### Claim 4 (depends on 1)

The device according to claim 1,
wherein a two's complement representation is used for representing negative numbers, and
wherein the auxiliary quantity is stored in a register and
wherein the unit for extracting comprises a unit for reading out a lower portion of the register in which the result is contained and a unit for inverting a value read out and for adding a one to obtain the result of the division.

### Claim 5 (depends on 1)

The device according to claim 1,
wherein the unit for extracting comprises:
a unit for calculating, as another auxiliary quantity, a result of a modular reduction of the numerator multiplied by the factor, wherein the denominator multiplied by the factor is provided as the modulus; and
a unit for subtracting the auxiliary quantity from the other auxiliary quantity to obtain the result of the division.

### Claim 6 (depends on 1)

The device according to claim 1, wherein the division is an integer division.

### Claim 7 (depends on 3)

The device according to claim 3, wherein the auxiliary quantity is selected such that it equals the number of positions of the numerator minus double the number of positions of the denominator plus 2.

### Claim 8 (depends on 5)

The device according to claim 5, wherein the unit for extracting is arranged to decide whether the result is negative and, in this case, to add to the result the modulus provided in the unit for modularly reducing for being used.

### Claim 9 (depends on 5)

The device according to claim 5, further comprising:
a first register for storing the numerator;
second register for storing the denominator;
third register for storing the other auxiliary quantity;
a fourth register for storing the auxiliary quantity; and
a register control unit for controlling the unit for calculating and the unit for extracting to obtain the result.

### Claim 10 (depends on 1)

The device according to claim 1,
wherein the result, multiplied by an integer multiplier, is calculated,
wherein the unit for providing is arranged to provide a factor which is selected such that a product of the factor and the denominator and the result, multiplied by the integer multiplier, is greater than the result of the division, and
wherein the unit for modularly reducing is formed to use a modulus equaling a sum of a product of the denominator and the factor and of the integer multiplier.

### Claim 11 (depends on 1)

The device according to claim 1,
wherein the unit for modularly reducing is formed to use a modulus equaling a sum of a product of the denominator and the factor and of an integer, wherein the integer is greater than or equal to 1, and
wherein the unit for extracting is arranged to perform a modular reduction using a modulus equaling a sum of a product of the denominator and the factor and of another integer, wherein the other integer is unequal to the integer so that the result of the division is obtained by the unit for extracting when a difference of the other integer and the integer equals 1, or the result, multiplied by an integer multiplier, is obtained, wherein the integer multiplier equals the difference of the other integer and the integer.

### Claim 12 (depends on 1)

The device according to claim 1, embodied as a crypto coprocessor of a cryptographic device.

### Claim 13 (depends on 1)

The device according to claim 1, wherein the integer is negative so that the result can be obtained without inversion.

### Claim 14 (depends on 11)

The device according to claim 11, wherein the other integer is a negative integer.

### Claim 15

A method for calculating a result or an integer multiple of the result of a division of a numerator by a denominator within a cryptographic algorithm, wherein the numerator and the denominator are parameters in the cryptographic algorithm, comprising the following steps:
providing a factor which is selected such that a product of the factor and the denominator is greater than the result;
modularly reducing a first product of the numerator and the factor using a modulus equaling a sum of a second product of the denominator and the factor and of an integer to obtain an auxiliary quantity comprising the result; and
extracting the result or the integer multiple of the result from the auxiliary quantity.
