Browse Prior Art Database

Modified Circuits for Fermat Transform Implementation

IP.com Disclosure Number: IPCOM000086686D
Original Publication Date: 1976-Oct-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 30K

IBM

Related People

Nussbaumer, H: AUTHOR

Abstract

Arithmetic operations by modulo Fermat can be implemented by very simple circuits, if adequate code-to-code conversion is performed on the original numbers.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 57% of the total text.

Page 1 of 3

Modified Circuits for Fermat Transform Implementation

Arithmetic operations by modulo Fermat can be implemented by very simple circuits, if adequate code-to-code conversion is performed on the original numbers.

Let p = 2/q/+1 be a Fermat number, then Fermat arithmetic circuits will have to operate modulo p. instead of performing the arithmetic operations directly. Let us first convert the original numbers A of this system into new numbers B defined by: B = 2/q/-A. as A is defined modulo p, we have :

(Image Omitted)

Assuming that the first q bits of A are inverted, a new number A can be defined by:

(Image Omitted)

After performing a code conversion, converting the A numbers into B, basic arithmetic operations, such as negation and addition of multiplications of A by a power of 2, will be much simpler.

As for the negation modulo Fermat of A, this will correspond to a simple logical inversion of the bits b(i) of B except if A = 0, B = 2/q/, in which case 2/q/ is kept for the representation of -A in the new system.

The addition of two numbers modulo Fermat is replaced in the converted system by a simple binary addition, with addition in the lower-bit position of the reverse of the higher-order carry bit.

Finally, a multiplication of A by 2/d/ will only require, in the converted system, shifting the bits of B by d positions towards the high-order bits and inverting the overflow bits prior to recirculation into the lowest-bit position, except for A = o, in which case inversion of the overflow bit must be inhibited.