Back to results
US 9,851,948 B2Granted
Method for implementing precomputation of large number in embedded system
AssigneeFeitian Technologies Co., Ltd.
InventorsZhou Lu, Huazhang Yu
Life of this patent
Estimating the term…
Abstract
Disclosed is a method for implementing precomputation of a large number in an embedded system. A modulo module, a modulo adding module, and a Montgomery modular multiplier are invoked according to a data format of a modulus length and a value of each data bit of a binary number corresponding to the modulus length, to perform an iterative operation, so that a precomputation result of a large number can be obtained when the modulus length is an arbitrary value, thereby improving the data processing speed.
Claims15
A method for realizing pre-computation for a large number in an embedded system, comprising:
- SA1 comprising:
- reading data in a first register, and writing the data which is read into a first random access memory;
- reading data in a second register, and writing the data which is read into a second random access memory;
- wherein the first register is configured to store a first data, the second register is configured to store a second data, a sixth register is configured to store a third data, a relationship of the second data to the third data is defined as R=2n, R represents the second data, n represents the third data, and the third data is an integer;
- SA2 comprising:
- invoking a module for modulo to perform an operation on the data in the first random access memory and the data in the second random access memory, and writing a result which is obtained from the operation into a third register and a fourth register respectively;
- wherein the module for modulo is configured to perform modulo operation with the data in the second random access memory mod the data in the first random access memory;
- SA3 comprising:
- reading data in the third register, and writing the data which is read into a third random access memory and a fourth random access memory respectively;
- reading data in the first register, and writing the data which is read into a fifth random access memory;
- SA4 comprising:
- invoking a modulo addition module to perform an operation on the data in the third random access memory, the data in the fourth random access memory and the data in the fifth random access memory, and updating the data in the third register with a result which is obtained from the operation;
- wherein the modulo addition module is configured to perform modulo addition operation with the data in the third random access memory plus the data in the fourth random access memory to obtain a sum, and the sum mod the data in the fifth random access memory;
- SA5 comprising:
- reading data at the least significant bit in the sixth register according to data in a fifth register, and making the data which is read as data at current bit, wherein an initial value of the data in the fifth register is a preset value;
- SA6 comprising:
- determining a value of the data at the current bit, executing step SA7 if the value of the data at the current bit is 0;
- executing step SA10 if the value of the data at the current bit is 1;
- SA7 comprising:
- reading data in the third register, and writing the data which is read into a sixth random access memory and a seventh random access memory respectively;
- reading data in the first register, and writing the data which is read into an eighth random access memory;
- SA8 comprising:
- invoking a Montgomery modulo multiplier to perform modulo multiplication on the data in the sixth random access memory, the data in the seventh random access memory and the data in the eighth random access memory, and updating the data in the third register with a result which is obtained from the modulo multiplication;
- wherein the Montgomery modulo multiplier is configured to perform modulo multiplication on the data in the sixth random access memory, the data in the seventh random access memory and the data in the eighth random access memory as a first input parameter, a second input parameter and a third input parameter respectively;
- SA9 comprising:
- updating data in the fifth register, and according to the updated data in the fifth register, reading data which is one-bit higher than the data at the current bit from the sixth register, and making the data which is read as updated data at the current bit, and returning to step SA6;
- SA10 comprising:
- reading data in the fourth register, and updating the data in the sixth random access memory with the read data;
- reading data in the third register, and updating the data in the seventh random access memory with the read data;
- reading data in the first register, and updating the data in the eighth random access memory with the read data;
- SA11 comprising:
- invoking a Montgomery modulo multiplier to perform modulo multiplication on the data in the sixth random access memory, the data in the seventh random access memory and the data in the eighth random access memory, and updating the data in the fourth register with a result which is obtained from the modulo multiplication;
- SA12 comprising:
- determining whether data at the current bit is data at the most significant bit in the sixth register, executing step SA13 if the data at the current bit is the data at the most significant bit in the sixth register;
- returning to step SA7 if the data at the current bit is not the data at the most significant bit in the sixth register;
- and
- SA13 comprising:
- outputting the data in the fourth register.
35 more elements
A method for realizing pre-computation for a large number in an embedded system, comprising:
- SC1 comprising:
- reading data in a first register, and writing the data which is read into a first random access memory;
- reading data in a second register, and writing the data which is read into a second random access memory;
- SC2 comprising:
- invoking a module for modulo to perform an operation on the data in the first random access memory and the data in the second random access memory, and writing a result which is obtained from the operation into a third register and a fourth register respectively;
- wherein the module for modulo is configured to perform modulo operation with the data in the second random access memory mod the data in the first random access memory;
- SC3 comprising:
- reading data in the third register, and writing the data which is read into a third random access memory and a fourth random access memory respectively;
- reading data in the first register, and writing the data which is read in to a fifth random access memory;
- SC4 comprising:
- invoking a modulo addition module to perform an operation on the data in the third random access memory, the data in the fourth random access memory and the data in the fifth random access memory, and updating the data in the third register with a result which is obtained from the operation;
- wherein the modulo addition module is configured to perform modulo addition operation with the data in the third random access memory plus the data in the fourth random access memory to obtain a sum, and the sum mod the data in the fifth random access memory;
- SC5 comprising:
- reading the updated data in the third register, writing the data which is read into a sixth random access memory and a seventh random access memory respectively;
- reading the data in the first register, and writing the data which is read into an eighth random access memory;
- SC6 comprising:
- invoking a Montgomery modulo multiplier to perform modulo multiplication on the data in the sixth random access memory, the data in the seventh random access memory and the data in the eighth random access memory, and updating the data in the third register with a result which is obtained from the modulo multiplication;
- wherein the Montgomery modulo multiplier is configured to perform modulo multiplication with the data in the sixth random access memory, the data in the seventh random access memory and the data in the eighth random access memory as a first input parameter, a second input parameter and a third input parameter respectively;
- SC7 comprising:
- updating data in a fifth register, and determining whether the data in the fifth register is equal to a length of data in a sixth register, executing step SC8 if the data in the fifth register is equal to the length of the data in the sixth register;
- returning to step SC5 if the data in the fifth register is not equal to the length of the data in the sixth register;
- and
- SC8 comprising:
- outputting the data in the third register.
21 more elements
A method for realizing pre-computation for a large number in an embedded system, comprising:
- SD1 comprising:
- reading data in a first register, and writing the data which is read into a first random access memory;
- reading data in a second register, and writing the data which is read into a second random access memory;
- SD2 comprising:
- invoking a module for modulo to perform an operation on the data in the first random access memory and the data in the second random access memory, and writing a result which is obtained from the operation into a third register and a fourth register respectively;
- wherein the module for modulo is configured to perform modulo operation with the data in the second random access memory mod the data in the first random access memory;
- SD3 comprising:
- reading data in the third register, and writing the data which is read into a third random access memory and a fourth random access memory respectively;
- reading data in the first register, and writing the data which is read into a fifth random access memory;
- SD4 comprising:
- invoking an modulo addition module to perform an operation on the data in the third random access memory, the data in the fourth random access memory and the data in the fifth random access memory, and updating the data in the third register with a result which is obtained from the operation;
- wherein the modulo addition module is configured to perform modulo addition operation with the data in the third random access memory plus the data in the fourth random access memory to obtain a sum, and the sum mod the data in the fifth random access memory;
- SD5 comprising:
- reading the updated data in the third register, and writing the data which is read into a sixth random access memory and a seventh random access memory respectively;
- reading the data in the first register, and writing the data which is read into an eighth random access memory;
- SD6 comprising:
- invoking a Montgomery modulo multiplier to perform modulo multiplication on the data in the sixth random access memory, the data in the seventh random access memory and the data in the eighth random access memory, and updating the data in the third register with a result which is obtained from the modulo multiplication;
- wherein the Montgomery modulo multiplier is configured to perform modulo multiplication with the data in the sixth random access memory, the data in the seventh random access memory and the data in the eighth random access memory as a first input parameter, a second input parameter and a third input parameter respectively;
- SD7 comprising:
- determining whether data in a fifth register is equal to a length of data in a sixth register, executing step SD9 if the data in the fifth register is equal to the length of the data in the sixth register;
- executing step SD8 if the data in the fifth register is not equal to the length of the data in the sixth register;
- SD8 comprising:
- updating the data in the fifth register, and returning to step SD5;
- and
- SD9 comprising:
- outputting the data in the third register.
23 more elements
Dependencies are inferred from the claim text.