Title:
SYSTEM AND METHOD FOR CALCULATING A RESULT FROM A DIVISION
Document Type and Number:
WIPO Patent Application WO2003069462
Kind Code:
A3
Abstract:
The invention relates to a system for calculating a result or an integer multiple of the result (Q) from a division of a numerator (A) by a denominator (N). The inventive system comprises a device (12) for providing a factor that is selected so that a product of the factor and the denominator is greater than the result. The system also comprises a device (14) for modularly reducing a first product of the numerator and the factor while using a modulus, which is equal to the sum of a second product of the denominator, the factor and an integer in order to obtain an auxiliary quantity that contains the result. A device (16) is used for extracting the result or the integer multiple of the result from the auxiliary quantity. This reduces a division to a modular reduction and to an extraction requiring few calculations whereby increasing speed and certainty, particularly when carrying out long number division problems.
Inventors:
FISCHER WIELAND (DE)
Application Number:
PCT/EP2003/000669
Publication Date:
April 15, 2004
Filing Date:
January 23, 2003
Export Citation:
Assignee:
INFINEON TECHNOLOGIES AG (DE)
FISCHER WIELAND (DE)
FISCHER WIELAND (DE)
International Classes:
G06F7/72; G06F7/00; G06F7/52; G06F7/535; G09C1/00; (IPC1-7): G06F7/52
Foreign References:
| US5710730A | 1998-01-20 | |||
| US5999962A | 1999-12-07 |
Other References:
CHING YU HUNG ET AL: "Fast RNS division algorithms for fixed divisors with application to RSA encryption", INFORMATION PROCESSING LETTERS, 24 AUG. 1994, NETHERLANDS, vol. 51, no. 4, pages 163 - 169, XP002267751, ISSN: 0020-0190
ELDRIDGE S E ET AL: "HARDWARE IMPLEMENTATION OF MONTGOMERY'S MODULAR MULTIPLICATION ALGORITHM", IEEE TRANSACTIONS ON COMPUTERS, IEEE INC. NEW YORK, US, vol. 42, no. 6, 1 June 1993 (1993-06-01), pages 693 - 699, XP000578160, ISSN: 0018-9340
ELDRIDGE S E ET AL: "HARDWARE IMPLEMENTATION OF MONTGOMERY'S MODULAR MULTIPLICATION ALGORITHM", IEEE TRANSACTIONS ON COMPUTERS, IEEE INC. NEW YORK, US, vol. 42, no. 6, 1 June 1993 (1993-06-01), pages 693 - 699, XP000578160, ISSN: 0018-9340
Download PDF:
Previous Patent: METHODS AND APPARATUS FOR ADAPTIVELY ADJUSTING A DATA RECEIVER
Next Patent: LAYERED ARCHITECTURE FOR MOBILE TERMINALS
Next Patent: LAYERED ARCHITECTURE FOR MOBILE TERMINALS