Granted Patent B2

US 9,405,729 · App. 14/072,155 · Granted Aug 2, 2016

Abstract

Claims (34)

1. A method for performing an iterative calculation of exponentiation of a large datum by an exponent formed of a number of bits, the method being implemented in an electronic device and comprising:

squaring a large variable, by a squaring block comprising a hardware coprocessor;

multiplying large variables, by a multiplication block comprising a hardware coprocessor;

storing results, by a buffer memory provided by the squaring block;

triggering a calculation by the squaring block for each bit of the exponent while the buffer memory is not full of results that have not been used by the multiplication block when the squaring block is inactive;

storing a result provided by the squaring block in the buffer memory, in association with a value of a group of at least two consecutive bits following a bit of 1 of the exponent, and resetting to zero each bit of the exponent belonging to a single group of at least two consecutive bits;

triggering a multiplication calculation by the multiplication block for multiplying an unused squaring result in the buffer memory by a multiplication result stored for the value of the group associated with the squaring result and storing the result of the multiplication for the value of the group while the buffer memory contains a squaring result not used by the multiplication block when the multiplication block is inactive; and

combining the multiplication results stored for the groups by raising the multiplication results stored to the power of two times the value of the group plus 1 and by multiplying among themselves the results of the raising operations obtained.

2. The method of claim 1 , comprising triggering a dummy calculation by the squaring block, if the buffer memory is full, if the corresponding bit of the exponent is on 1, and if the squaring block is inactive.

3. The method of claim 1 , comprising triggering a dummy calculation by the multiplication block if the buffer memory is empty and if the multiplication block is inactive.

4. The method of claim 1 , wherein all the results provided by the squaring and multiplication blocks are used to obtain the result of the exponentiation.

5. The method of claim 1 , wherein several results provided by the squaring block are stored in the buffer memory.

6. The method of claim 1 , wherein the buffer memory is managed in a cyclical manner, with a write index, a read index and a counter of unused results.

7. The method of claim 1 , wherein the buffer memory is configured to store three to five results provided by the squaring block.

8. The method of claim 1 , wherein the calculations performed by the squaring and multiplication blocks are modular operations.

9. An electronic device comprising:

a processor configured to calculate an exponentiation of a large datum by an exponent formed of a number of bits;

a calculation block for squaring a large variable;

a calculation block for multiplying large variables; and

a buffer memory for temporarily storing several results provided by the squaring block, wherein the processor being configured to:

trigger a calculation by the squaring block for each bit of the exponent while the buffer memory is not full of results not used by the multiplication block when the squaring block is inactive,

store the result provided by the squaring block in the buffer memory, in association with the value of a group of a certain number of consecutive bits following a bit on 1 of the exponent, and

reset to zero each bit of the exponent belonging to a single group of at least two consecutive bits,

trigger a multiplication calculation by the multiplication block for multiplying an unused squaring result in the buffer memory by a multiplication result stored for the value of the group associated with the squaring result and store the result of the multiplication for the value of the group while the buffer memory contains a squaring result not used by the multiplication block and when the multiplication block is inactive, and

combine the multiplication results stored for the groups by raising the multiplication results stored to the power of two times the value of the group plus 1 and by multiplying among themselves the results of the raising operations obtained.

10. The device of claim 9 , wherein the buffer memory is configured to store three to five results provided by the squaring block.

11. The device of claim 9 , wherein the squaring and multiplication blocks each comprise a coprocessor of programmable central unit type, or a fully hardware coprocessor of state machine type, or are each performed by a task executed independently of a main program, the tasks and the main program being executed by the multi-core-type processor.

12. The device of claim 9 , wherein the processor is configured to trigger a dummy calculation by the squaring block, if the buffer memory is full, if the corresponding bit of the exponent is on 1, and if the squaring block is inactive.

13. The device of claim 9 , wherein the processor is configured to trigger a dummy calculation by the multiplication block if the buffer memory is empty and if the multiplication block is inactive.

14. The device of claim 9 , wherein all the results provided by the squaring and multiplication blocks are used to obtain the result of the exponentiation.

15. The device of claim 9 , wherein several results provided by the squaring block are stored in the buffer memory.

16. The device of claim 9 , wherein the buffer memory is managed in a cyclical manner, with a write index, a read index and a counter of unused results.

17. The device of claim 9 , wherein the buffer memory is configured to store three to five results provided by the squaring block.

18. The device of claim 9 , wherein the calculations performed by the squaring and multiplication blocks are modular operations.

Assignments (7)