Pipelined modular reduction and division

• US 9,535,656 B2
• Filed: 03/14/2014
• Issued: 01/03/2017
• Est. Priority Date: 03/14/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Condorelli, Vincenzo, Dragone, Silvio, Santiago Fernandez, William, Hadzic, Nihad, Ranck, Andrew R.
• Primary Examiner(s): Yaary, Michael D
• Application Number:
  US14/210,966
• Publication Number:
  US 20150261499A1
• Time in Patent Office: 1,026 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 5/01 for shifting, e.g. justifying, scaling, normalising digital stores in which the information is moved stepwise, e.g. shift-registers G11C19/00; digital stores in which the information circulates G11C21/00
• CPC Class Codes: G06F 7/72 using residue arithmetic

Abstract

Embodiments relate to modular reductions. An aspect includes a system to perform modular reductions. The system includes a shift register to store an input string or number. The system also includes a plurality of processing elements arranged in a pipeline configuration to convert the input string to a predefined alphabet or to convert the number to a different base based on a plurality of modular reductions, an output of one of the plurality of processing elements being an input to a subsequent one of the plurality of processing elements in the pipeline as part of a recursive division, and an input of a first one of the plurality of processing elements in the pipeline being an output of the shift register.

Claims

1. A system to perform modular reductions, the system comprising:

a shift register configured to store an input string or number;

a plurality of processing elements arranged in a pipeline configuration and configured to convert the input string to a predefined alphabet or to convert the number to a different base based on a plurality of modular reductions, an output of one of the plurality of processing elements being a quotient bit that is an input to a subsequent one of the plurality of processing elements in the pipeline as part of a recursive division, and an input of a first one of the plurality of processing elements in the pipeline being an output of the shift register.

2. The system according to claim 1, further comprising a quotient register associated with each of the plurality of processing elements, each of the quotient registers determining a division result.

3. The system according to claim 1, further comprising a processing circuit implementing an encryption algorithm or a computation, the processing circuit loading the shift register with the input string or the number.

4. The system according to claim 1, wherein each of the plurality of processing elements includes an accumulator shift register, a data bus, and a subtractor, the accumulator shift register and the data bus providing input to the subtractor of each of the plurality of processing elements.

5. The system according to claim 4, wherein when an output of the subtractor of a processing element among the plurality of processing elements is a negative value, a bit is loaded into the accumulator shift register of a next processing element among the plurality of processing elements in the pipeline.

6. The system according to claim 4, wherein when an output of the subtractor of a processing element among the plurality of processing elements is a positive value, a bit is loaded into the accumulator shift register of a next processing element among the plurality of processing elements in the pipeline and, additionally, the output of the subtractor is fed back to the accumulator shift register of the processing element among the plurality of processing elements.

7. The system according to claim 1, wherein a number of the plurality of processing elements is equal to a number of characters of the input string or number to be converted with the plurality of processing elements.

8. The system according to claim 1, wherein a number of the plurality of processing elements is less than a number of characters of the input string or number to be converted with the plurality of processing elements, and a last processing element among the plurality of processing elements in the pipeline provides a feedback to the first one of the plurality of processing elements.

9. A method for implementing modular reductions, the method comprising:

loading a shift register with an input string or number; and

converting, by a plurality of processing elements arranged in a pipeline configuration, the input string to a predefined alphabet or the number to a different base based on a plurality of modular reductions, wherein an output of one of the plurality of processing elements is a quotient bit that is an input to a subsequent one of the plurality of processing elements in the pipeline as part of a recursive division, and an input of a first one of the plurality of processing elements in the pipeline is an output of the shift register.

10. The method according to claim 9, further comprising implementing a division corresponding with each of the plurality of processing elements.

11. The method according to claim 9, further comprising executing, using a processor, an encryption algorithm or a computation, the executing including loading the shift register with the input string or the number.

12. The method according to claim 9, wherein the implementing the plurality of processing elements includes each of the plurality of processing elements performing a subtraction of bits in an accumulator shift register and a data bus.

13. The method according to claim 12, further comprising, when an output of the performing the subtraction in a processing element among the plurality of processing elements is a negative value, loading a bit into the accumulator shift register of a next processing element among the plurality of processing elements in the pipeline.

14. The method according to claim 12, further comprising, when an output of the performing the subtraction in a processing element among the plurality of processing elements is a positive value, loading a bit into the accumulator shift register of a next processing element among the plurality of processing elements in the pipeline and additionally feeding back the output to the accumulator shift register of the processing element among the plurality of processing elements.

15. The method according to claim 9, wherein the converting by the plurality of processing elements includes implementing a number of the processing elements equal to a number of characters of the input string or number to be converted with the plurality of processing elements.

16. The method according to claim 9, wherein the converting by the plurality of processing elements includes implementing a number of the processing elements less than a number of characters of the input string or number to be converted with the plurality of processing elements.

17. The method according to claim 16, further comprising a last processing element among the plurality of processing elements in the pipeline providing a feedback to the first one of the plurality of processing elements.

18. A modular reduction module, comprising:

a plurality of processing elements arranged in a pipeline configuration, each of the plurality of processing elements including a subtractor and configured to output a quotient bit, for each subtraction performed by the subtractor, and a remainder value, for each subtraction performed by the subtractor that results in a positive value; and

a shift register configured to provide input to a first processing element among the plurality of processing elements, wherein each subsequent one of the plurality of processing elements in the pipeline configuration receives the quotient bit of the previous one of the plurality of processing elements in the pipeline configuration as an input after each subtraction.

19. The modular reduction module according to claim 18, further comprising a quotient register associated with each of the plurality of processing elements, the quotient register accumulating each quotient bit output by the subtractor of the respective one of the processing elements to generate a division result for the respective one of the processing elements.

20. The modular reduction module according to claim 18, wherein a number of clock cycles to complete processing by the modular reduction module is based on a length of the input provided by the shift register, each one of the plurality of processing elements outputs a remainder valid signal after completing processing, and a remainder valid signal of each of the plurality of processing elements is output based on receiving a remainder valid signal of a respective previous one of the plurality of processing elements.