TWI841330B - Gaussian elimination computing system and gaussian elimination computing method - Google Patents

Abstract

A Gaussian elimination computing system and a Gaussian elimination computing method are provided. The Gaussian elimination computing system includes a control circuit, a systolic array, and a memory. The control circuit receives an operation matrix. The systolic array includes a square array formed by a plurality computing cells. The systolic array is configured to perform a matrix decomposition operation to the operation matrix, to decompose the operation matrix into an upper triangular matrix and a lower triangular matrix. The memory is configured with an operation data block with the same size of the operation matrix, for storing the upper triangular matrix and the lower triangular matrix after decomposition.

Description

Gaussian elimination calculation system and Gaussian elimination calculation method

The present invention relates to a system and method, and in particular to a Gaussian elimination calculation system and a Gaussian elimination calculation method.

In post-quantum cryptography, unlike quantum cryptography, post-quantum cryptography uses existing binary computers and does not rely on quantum mechanics. It relies on computational problems that cryptographers believe cannot be effectively solved by quantum computers to perform effective encryption.

The present invention provides a Gaussian elimination calculation system and a Gaussian elimination calculation method, which can save memory requirements when performing matrix decomposition operations.

The Gaussian elimination calculation system of the present invention includes a control circuit, a systolic array and a memory. The control circuit receives a calculation matrix. The systolic array includes a square matrix formed by a plurality of calculation cells, and the systolic array is configured to perform a matrix decomposition operation on the calculation matrix to decompose the calculation matrix into a lower triangular matrix and an upper triangular matrix. The memory is configured with a calculation data block of the same size as the calculation matrix to store the decomposed lower triangular matrix and upper triangular matrix.

The Gaussian elimination calculation method of the present invention includes receiving a calculation matrix; inputting the calculation matrix into a pulse array to perform matrix decomposition operation, and decomposing the calculation matrix into a lower triangular matrix and an upper triangular matrix; and configuring a calculation data block of the same size as the calculation matrix in a memory, and storing the decomposed lower triangular matrix and upper triangular matrix in the calculation data block.

Based on the above, the Gaussian elimination calculation system and Gaussian elimination calculation method of the present invention can efficiently utilize memory and improve the efficiency and hardware requirements required for calculation.

1, 3: Gaussian elimination calculation system

10, 30: Control circuit

11, 31: Pulsating array

12, 32, 303: Memory

33, 34, 1102, MUX1~MUX3: Multiplexer

110: Operation Cells

110A: First operation cell

110B: Second operation cell

300: First control circuit

301: Second control circuit

302: Sorting circuit

304: Address memory

500~503: Data block

1100: Debug circuit

1101: or gate

1103, FF: Flip-flop

A, B, A[0]~A[4], B[0]~B[4]: Input

C, C[0]~C[4]: output

CB1~CB3: row group matrix

addr1~addr5: address recorder

data_in[0]~data_in[4]: input value

data_out: input row

data_out[0]~data_out[4]: output value

data_in: output column

ext_contr: controller

ext_en, ext_en[0]~ext_en[4]: external enable signal

ext_op, ext_op[0]~ext_op[4]: external control signal

fail_in, fail_out: Debugging results

FF11~FF19, FF21~FF29: shift register

int_op: internal control signal

M: Operation matrix

check_en, op_in, op_in[0]~op_in[4], op_out, OPA, perm_op, perm_op[0]~perm_op[4]: control signal

P: sorting matrix

pivot_en: Enable signal

R: Input matrix

S, S[0]~S[4]: Select signal

S90~S92: Steps

T: Target Matrix

trig: trigger signal

U12~U15, U23~U25, U34~U35, U45: unit

Figure 1 is a block diagram of the Gaussian elimination calculation system of the first embodiment of the present invention.

Figure 2A is a circuit block diagram of a pulse array in accordance with an embodiment of the present invention.

Figures 2B and 2C are the truth tables of the second and first operation cells in Figure 2A, respectively.

FIG2D shows a schematic diagram of the debugging circuit in the first operation cell in FIG2A.

FIG3A is a block diagram of a Gaussian elimination calculation system according to the first embodiment of the present invention.

FIG3B shows a circuit block diagram of the first control circuit in FIG3A.

FIG3C shows a circuit block diagram of the sequencing circuit in FIG3A.

FIG3D shows a circuit block diagram of a portion of the multiplexer in FIG3A.

Figures 4A to 4Z are used to illustrate the operation flow of a pulse array performing matrix decomposition operations on the first row group matrix.

Figures 5A to 5C show schematic diagrams of the process of the pulse array in Figure 3A writing into the memory.

Figure 6A to Figure 6D show schematic diagrams of the matrix decomposition operation process for the operation matrix.

Figures 7A to 7C show schematic diagrams of the calculation process of how to multiply the inverse matrix and the sorting matrix of the lower triangular matrix by the target matrix.

Figures 8A to 8C show schematic diagrams of how to calculate and obtain the public key matrix based on the inverse matrix of the upper triangular matrix.

FIG9 shows a flow chart of the Gaussian elimination calculation method of the first embodiment of the present invention.

FIG1 is a block diagram of a Gaussian elimination computing system 1 of the first embodiment of the present invention. In some embodiments, the Gaussian elimination computing system 1 can be applied to post-quantum cryptography to receive an input matrix R and generate a public key for encryption according to a corresponding encryption algorithm. For example, the encryption algorithm may be McEliece, BIKE, FrodoKEM, HQC, NTRU Prime or other suitable encryption algorithms. The input matrix R received by the Gaussian elimination computing system 1 may be a random matrix generated randomly, and the input matrix R may be divided by the input matrix R into an operation matrix M and a target matrix T. In the operation matrix M and the target matrix T, the operation matrix M can be used by the Gaussian elimination calculation system 1 to calculate the inverse matrix M ^-1 , and further operate the target matrix T based on the inverse matrix M ^-1 to obtain the public key. In some embodiments, the Gaussian elimination calculation system 1 can determine in real time whether the operation matrix M is full rank or whether the operation matrix M is invertible during the process of calculating the inverse matrix M ^{- 1 of the operation matrix M. In other words, the Gaussian elimination calculation system 1 does not need to wait until the complete calculation process of the inverse matrix M-1} is completed before determining whether it is full rank or whether the inverse matrix M ^-1 exists. On the contrary, when it is determined that the operation matrix M is not full rank or is irreversible, the Gaussian elimination calculation system 1 can abandon the operation on the operation matrix M halfway through the calculation process to achieve the effect of early-abortion. For example, the Gaussian elimination calculation system 1 can use Naive Abortion, Square Inversion, PLU decomposition or other suitable calculation methods to achieve early abandonment in the calculation process. On the other hand, the Gaussian elimination calculation system 1 can save memory space during the calculation process, so that the Gaussian elimination calculation system 1 can use the memory block of the same size as the operation matrix M to perform calculations, avoiding the additional burden on memory capacity and circuit area.

Generally speaking, the Gaussian elimination calculation system 1 will execute and calculate the following formulas (1) to (3) to calculate the public key matrix PK based on the input matrix R.

PM = LU (1)

U ^-1 ． L ^-1 . P. M = I (2)

PK = U ^-1 ． L ^-1 ． P ． T (3) Where P is the sorting matrix, M is the operation matrix, L is the lower triangular matrix, U is the upper triangular matrix, U ^-1 is the inverse matrix of the upper triangular matrix, L ^-1 is the inverse matrix of the lower triangular matrix, I is the unit matrix, PK is the public key matrix, and T is the target matrix. In detail, by PLU decomposition, the operation matrix M can be decomposed into the relationship expressed in formula (1) and formula (2). Furthermore, by reproducing the process of restoring the operation matrix M to the unit matrix in formula (2) on the target matrix T, the target matrix T can be operated through the matrix decomposition process of the operation matrix M as shown in formula (3), and the public key matrix PK can be obtained.

In detail, the Gaussian elimination calculation system 1 includes a control circuit 10, a pulse array 11, and a memory 12. The control circuit 10 can be configured to receive an n×m (i.e., n columns and m rows) input matrix R, and divide the input matrix R into an n×n operation matrix M and an n×(m-n) target matrix T, where n<m. The pulse array 11 is coupled to the control circuit 10 and receives the operation matrix M. In this embodiment, the pulse array 11 can perform a matrix decomposition operation such as PLU decomposition on the operation matrix M to decompose the operation matrix M into a sorting matrix P, a lower triangular matrix L, and an upper triangular matrix U. In addition, the memory 12 can be configured with a computing data block of the same size as the computing matrix M. Therefore, the pulse array 11 can store the decomposed lower triangular matrix L and upper triangular matrix U in the computing data block of the same size as the computing matrix M in the memory 12.

In some embodiments, the pulsating array 11 can be implemented using a systolic array, a systolic network, a systolic line, or other suitable computing architectures. In the following description of this embodiment, the pulsating array 11 will be mainly described by decomposing the pulsating array 11 using the PLU based on the systolic line architecture, but it should be understood that the above implementation should not be used as a basis for limiting the Gaussian elimination computing system 1 and the pulsating array 11.

In some embodiments, when the control circuit 10 receives an n×m input matrix R, the control circuit 10 may first split the input matrix R into an n×n operation matrix M and an n×(mn) target matrix T. Then, the control circuit 10 may further split the operation matrix M into a plurality of n×p row group matrices, and input the row group matrices into the pulse array 11 respectively, thereby calculating the inverse matrix M ^-1 of the overall operation matrix M.

FIG2A is a circuit block diagram of a pulse array 11 according to an embodiment of the present invention. In some embodiments, in response to performing calculations on a row group matrix having a size of n×p, the pulse array 11 may have, for example, a circuit block structure as shown in FIG2A. The pulse array 11 may, for example, receive an input row data_in having input values data_in[0] to data_in[4], and generate an output row having output values data_out[0] to data_out[4] according to an external control signal ext_en and a control signal op_in. As shown in FIG. 2A , the pulse array 11 has a square matrix structure and has a plurality of operation cells 110A and 110B arranged in an array. In the following description, a 5×5 size pulse array 11 is used as an example to illustrate the operation process of the Gaussian elimination calculation system 1. A person skilled in the art can adaptively adjust the size of the pulse array 11 according to different design requirements. More specifically, the pulse array 11 has a first operation cell 110A and a second operation cell 110B. The first operation cell 110A is arranged on the main diagonal line of the pulse array 11 (i.e., the diagonal line from the upper left to the lower right), and the second operation cell 110B is arranged outside the main diagonal line of the pulse array 11. Each operation cell 110 can be, for example, a circuit structure implemented according to a mealy state machine, which includes appropriate logic gates and flip-flops coupled to each other to implement its function, so that each time the operation cell 110 is triggered by a clock signal, it generates an output data value according to the received input data value and the data value stored in itself.

FIG2B and FIG2C are respectively diagrams of the truth value representation of the second operation cell 110B and the first operation cell 110A in FIG2A. Specifically, the second operation cell 110B has a relatively simpler logic function than the first operation cell 110A. Each second operation cell 110B can be operated by a 2-bit control signal OP to have four functions, namely, pass (PASS), addition (ADD), swap (SWAP) and start (INIT). Specifically, when operating in the pass (PASS) function, the second operation cell 110B only passes the input data to the output end, and the input data does not affect the data value stored inside the second operation cell 110B. When operating in the addition (ADD) function, the second operation cell 110B will add up the input data value and the stored data value and output it, and the input data will not affect the data value stored in the second operation cell 110B. When operating in the swap (SWAP) function, the second operation cell 110B will write the input data value into the inside and output the stored data value. When operating in the startup (INIT) function, the second operation cell 110B will write the input data value into the inside and output the data value 0. Compared to some implementations, where the pass (PASS), addition (ADD) and swap (SWAP) functions are indicated by a two-bit control signal, and the start (INIT) function is indicated by an additional bit, the control signal of the second operation cell 110B is encoded in a more concise manner, so that no matter in terms of signal routing or hardware structure requirements, it can bring effective area improvement effects to the Gaussian elimination calculation system 1.

For the first operation cell 110A, the first operation cell 110A can be operated in the decomposition operation mode or the reproduction operation mode. As shown in FIG2C, when operating in the decomposition operation mode, the first operation cell 110A generates an output control signal OPA according to the control of the received control signal op_in and the external enable signal ext_en. When the external enable signal ext_en is, for example, at a logical value of 1, the first operation cell 110A can be controlled by the control signal OP under the functions of passing (PASS), switching (SWAP) and starting (INIT), and outputs the control signal op_out corresponding to passing (PASS), switching (SWAP) and starting (INIT), respectively. In addition, when the external enable signal ext_en is, for example, at a logical value of 0, the first operation cell 110A can operate under the functions of pass (PASS), swap (SWAP) and addition (ADD) according to the input data value and the data value stored in itself. In addition, when the first operation cell 110A operates under the reproduction operation mode, the first operation cell 110A can have the same operating characteristics as the second operation cell 110B, and thus can operate under the functions of pass (PASS), addition (ADD), swap (SWAP) and start (INIT) according to the truth table shown in FIG. 2B and the control signal op_in given by the external.

Returning to FIG. 2A , for the overall operation of the pulse array 11, the values of each row in the row group matrix can be input from the top of the pulse array 11 to each operation cell 110 in the first row of the pulse array 11. The first row of the pulse array 11 operates in a corresponding state according to the received external enable signal ext_en[0] and control signal op_in[0] to perform calculations and output data values to the second row of the pulse array 11. Similarly, the second row of the pulse array will also perform calculations according to the external enable signal ext_en[1] and control signal op_in[1] and output data values to the third row of the pulse array 11, and so on.

Although FIG. 2A shows a 5×5 size pulse array 11, the size of the pulse array 11 is not limited to this, as long as the number of rows of the pulse array 11 is greater than or equal to the number of rows of the row group matrix.

FIG2B and FIG2C illustrate and explain the truth tables of the first operation cell 110A and the second operation cell 110B, so as to explain the individual operations of the first operation cell 110A and the second operation cell 110B. However, as shown in FIG2A, in addition to the coupling relationship between rows and columns, the first operation cells 110A on the diagonal are also connected in series. Such a series connection relationship is used to configure the early abandonment function of the first operation cell 110A.

FIG2D shows a circuit diagram of the debug circuit 1100 in the first operation cell 110A in FIG2A. In the pulse array 31, the debug circuit 1100 of each first operation cell 110A is connected to the debug circuit 1100 of the first operation cell 110A of the previous stage to receive the debug judgment result fail_in of the first operation cell 110A of the previous stage. The received debug judgment result fail_in is operated by the OR gate 1101 with the inverted internal storage data, and is output after being selected by the multiplexer 1102 controlled by the control signal check_en. In addition, a flip-flop 1103 is coupled to the output end of the multiplexer 1102 to store the error detection result fail_out and output the error detection result fail_out to the first operation cell 110A of the next stage according to the driving of the clock signal. Therefore, in actual operation, all the data stored in the first operation cells 110A will be checked through the serially connected debugging circuit 1100. As long as the data stored in any first operation cell 110A is 0, the debugging result fail_out output by the first operation cell 110A at that level will be switched to the logical value 1, and the debugging result fail_out with a logical value of 1 will be continuously transmitted through the OR gate 1101 in the debugging circuit 1100 until the end of the series of the first operation cells 110A.

FIG3A is a block diagram of a Gaussian elimination calculation system 3 of the first embodiment of the present invention. The Gaussian elimination calculation system 3 includes a control circuit 30, a pulse array 31, and a memory 32. The Gaussian elimination calculation system 3 is similar to the Gaussian elimination calculation system 1, so for the structure and individual operation details of the pulse array 31, please refer to the description of the pulse array 11 in FIG2A to FIG2D, which will not be elaborated here.

In detail, the control circuit 30 includes a first control circuit 300 and a second control circuit 301. The first control circuit 300 is used to generate an external enable signal ext_en and an external control signal ext_op. The second control circuit 301 can record the control signal op_out output by the pulse array 31 and generate an internal control signal int_op according to the pulse array 31. The control circuit 30 can select the external control signal ext_op or the internal control signal int_op according to the external enable signal ext_en through the selection of the multiplexer MUX2 to generate the control signal op_in. The control signal op_in selected by the multiplexer MUX2 will be input to the pulse array 31 to control the operation of each row in the pulse array 31.

The second control circuit 301 includes a sorting circuit 302, a memory 303 and a multiplexer MUX1. The second control circuit 301 can use the sorting circuit 302 to store the sorting matrix P, which records the order relationship of each column when the pulse array 31 performs matrix decomposition operation on the row group matrix. In addition, the second control circuit 301 can use the memory 303 and the multiplexer MUX1 to record the control signal op_out output by the pulse array 31, and generate an internal control signal int_op to the multiplexer MUX2. In some embodiments, the operation of the second control circuit 301 to update the memory 303 can be a partial update of the memory 303 according to the timing. The partial update content will be described in detail in the following section with the circuit structure and operation content.

In one embodiment, when the pulse array 31 is performing a decomposition operation such as a row group matrix, the pulse array 31 may be operated in a triangular operation mode, that is, the second operation cell 110B below the diagonal of the pulse array 31 may be disabled or turned off, and only the first operation cell 110A on the diagonal of the pulse array 31 and the second operation cell 110B above the diagonal are left turned on for operation. In this triangular operation mode, the first operation cell 110A is operated in a decomposition operation mode, that is, the first operation cell 110A is operated according to the truth table shown in FIG. 2C, and the generated control signal will be used to control the turned-on second operation cell 110B in the same column. Finally, the pulse array 31 will output the control signal op_out from the first operation cell 110A on the diagonal line.

In one embodiment, when the pulse array 31 is performing other operations, such as reproducing operations, the pulse array 31 can be operated in a matrix operation mode, that is, all the operation cells 110 in the pulse array 31 are turned on to perform operations. In this matrix operation mode, the first operation cell 110A is operated in a reproducing operation mode, that is, the first operation cell 110A is operated according to the truth table shown in FIG. 2B, and the operation cells 110 in the entire row of the pulse array 31 are operated according to the received control signal op_in. Finally, the pulse array 31 can generate an output data signal data_out by the last row of operation cells 110 on the pulse array 31.

The multiplexer 33 is coupled to the pulse array 31 to receive the output control signal op_out and the output data signal data_out. The multiplexer 33 selects the corresponding output according to whether the pulse array 31 is operating in a triangle operation mode or a square operation mode, and transmits it to the memory 32. The multiplexer 34 is coupled to the second control circuit 301. The multiplexer 34 is used to receive the control signal op_out and the input column data_in read from the memory 32, and write the calculation result of the pulse array 31 or the data stored in the memory 32 into the memory 303 of the second control circuit 303 according to the calculation requirements.

The output of the pulse array 31 is written into the memory 32 after being selected by the multiplexer MUX3. The structure and function of the multiplexer MUX3 are similar to those of the multiplexer MUX1, and it can write partial data bit by bit.

FIG3B shows a circuit block diagram of the first control circuit 300 in FIG3A. FIG3C shows a circuit block diagram of the sorting circuit 302 in FIG3A. FIG3D shows a circuit block diagram of the multiplexers MUX1 and MUX3 in FIG3A. The structures and operations of FIG3B, FIG3C, and FIG3D will be described in the following sections in conjunction with the operation of the overall Gaussian elimination calculation system 3.

Figures 4A to 4Z are used to illustrate the operation flow of a pulse array 31 performing matrix decomposition operation on the first row group matrix CB1. In Figure 4A, the input matrix R of size 15×25 is first input to the control circuit 30 and stored in the memory 32. In order to perform matrix decomposition operation and calculate the public key matrix PK, the control circuit 30 first decomposes the input matrix R into a 15×15 operation matrix M and a 15×10 target matrix T. In Figure 4A, for the sake of simplicity, all matrix cells in the input matrix R are represented by a circle symbol ○, but in actual applications, the matrix cells in the input matrix R can be the same or different values.

Please refer to FIG. 3B , which shows a circuit block diagram of the first control circuit 300 in FIG. 3A . The first control circuit 300 can generate an external enable signal ext_en and an external control signal ext_op according to the operation requirements. In this embodiment, the first control circuit 300 can be used to control a pulse array 31 of, for example, a size of 5×5. On the left side of FIG. 3B , the serially connected shift registers FF11~FF19 delay the enable signal provided by the controller ext_contr, so that the output of the shift registers FF11~FF19 at each stage has a delay of two clock cycles. In addition, the controller ext_contr can also switch the external enable signal provided to any column of the pulse array 31 to enable through an OR gate in an appropriate clock cycle.

On the other hand, on the right side of FIG. 3B , serially connected shift registers FF21 to FF29 are also shown for providing a control signal ext_op to the pulse array 31. Similarly, the shift registers FF21 to FF29 delay the control signal provided by the external control signal ext_op, so that each output of the shift registers FF21 to FF29 has a delay of two clock cycles.

In FIG4B , the control circuit 30 divides the operation matrix M into a plurality of row group matrices. In this embodiment, the 15×15 operation matrix M is divided into three 5×15 row group matrices, and the first row group matrix is first provided to the pulse array 31 for operation. More specifically, the values of each column in the first row group matrix are provided to the first column of the pulse array 31 in time sequence, so that each column of the pulse array 31 is operated in sequence and the operation result is transmitted to the next column of the pulse array 31. In addition, the pulse array 31 performing the matrix decomposition operation will be controlled to operate in the triangular operation mode, that is, only the first operation cell 110A on the diagonal and the second operation cell 110B above the diagonal are turned on, and the second operation cell 110B below the diagonal is turned off.

In detail, the left side of FIG. 4B shows the first row group matrix in the operation matrix M, that is, the first to fifth rows of the operation matrix M. The middle of FIG. 4B shows the values received, stored and output by the operation cells 110 of each row of the pulse array 31. In FIG. 4B, the value [0 1 0 1 1] of the first row of the first row group matrix will first be input into each operation cell 110 of the first row of the pulse array 31. At this time, the external enable signal ext_en corresponding to the first row operation cell 110 will be enabled, so that the first row operation cell 110 receives the control signal op_in provided by the outside. Therefore, the first row operation cell 110 will be controlled by the external control signal op_in under the activation function.

Since the first row of operation cells 110 is controlled under the activation function, referring to the truth tables of FIG. 2B and FIG. 2C, when operation cells 110A and 110B are operated under the activation function, operation cells 110A and 110B will store the input value inside and output the logical value 0.

In addition, the right side of FIG. 4B is the recording process of the sorting matrix. In this embodiment, the sorting matrix is a 1×15 matrix, which corresponds to the sorting or swapping results of the diagonal cells of the first to fifteenth columns in the operation matrix M. In detail, when performing a matrix decomposition operation, such as a PLU decomposition operation, each column of the operation matrix M will be properly swapped so that the diagonal of the operation matrix M is full rank, that is, the cells on the diagonal of the operation matrix M are all 1. Since the first row group matrix of the operation matrix M includes the diagonal cells of the first to fifth columns of the operation matrix M, when performing the operation of the first row group matrix, only the sorting results of the first to fifth columns of the operation matrix M are recorded and recorded in the sorting matrix. In this embodiment, in response to the external enable signal ext_en whose logic value is switched to 1, it means that when the operation cell 110 of the first column receives the input value for operation in the first clock cycle, the address 1 is pre-written in the cell corresponding to the first column of the sorting matrix, indicating that the operation cell 110 of the first column in the pulse array 31 is recording the value of the first column of the first row group matrix.

In FIG. 4C , the external enable signal ext_en provided to the first row of the pulse array 31 is set to a logical value of 0, so that the operation cell 110 in the first row of the pulse array 31 performs operations according to the input value and its stored value. More specifically, the first operation cell 110A in the first row of the pulse array 31 generates a control signal op_out according to the input value and its stored value, and the generated control signal is provided to the remaining second operation cells 110B in the first row that are turned on.

In this embodiment, the value [0 0 1 1 0] of the second column in the first row group is provided to the operation cell 110 of the first column in the pulse array 31. The first operation cell 110A in the first column determines that the operation cell 110A in the column needs to perform the pass (PASS) function based on the received logic value 0 and the stored logic value 0, and thus outputs the received logic value 0 as the control signal op_out corresponding to the pass (PASS) function, and provides the control signal OPA corresponding to the pass (PASS) function to the remaining second operation cells 110B in the same column. The operation cell 110 in the first column directly inputs the received value [0 0 1 1 0] to the operation cell 110 in the second column in the next clock cycle.

In FIG. 4D , the value [1 1 1 1 1] of the third column in the first row group is provided to the operation cell 110 in the first row of the pulse array 31, and the operation cell 110 in the second row receives the output value of the operation cell 110 in the first row (i.e., the value [0 0 1 1 0] of the second column in the first row group). For the first operation cell 110A in the first row of the pulse array 31, the value stored in it is 0 and the value received is 1, thus generating a control signal OPA corresponding to the swap (SWAP), thereby controlling the other second operation cells 110B in the same row to perform row-column swapping in the next clock cycle. That is, in the next clock cycle, the operation cell 110 in the first row will swap the first column in the first row group it stores with the third column in the first row group it receives. Therefore, the operation cell 110 in the first row will store the value of the third column in the first row group in the next clock cycle, and output the first column value of the first row group matrix originally stored to the operation cell 110 in the second row.

In response to the swap decision made by the operation cell 110 in the first row in this cycle, the value 3 is stored in the first cell of the sorting matrix, indicating that the value of the third column in the first row group is stored in the operation cell 110 in the first row. At the same time, since the operation cell 110 in the second row also receives the external enable signal ext_en with a logical value of 1, the cycle number 3 is also recorded in the corresponding second cell of the sorting matrix.

For details, please refer to the sorting circuit 302 shown in FIG. 3C for the recording process of the sorting matrix P. The sorting circuit 302 includes a ring structure formed by serially connecting address recorders addr1 to addr5 and an address memory 304. Specifically, the address recorders addr1 to addr5 correspond to the five columns of the pulse array 31 respectively. When the pulse array 31 starts to perform matrix decomposition operation each time, the address memory 304 can first write the addresses stored therein into the address recorders addr1 to addr5 respectively. Then, in the subsequent process of matrix decomposition operation, when any row of the pulse array 31 is activated (INIT) or swapped (SWAP), the first operation cell 110A of the row will transmit the enabled trigger signal trig to the corresponding address recorder, and when the enable signal pivot_en is also enabled, the current address will be written into the flip-flop FF to complete the recording of each row address. In some embodiments, the current address is the count of the current clock cycle. A plurality of comparators are respectively coupled to the address recorders addr1~addr5 to generate control signals perm_op[0]~perm_op[4]. The comparator will compare the current address with the address stored in the address recorder. When the comparator determines that the current address reaches the address recorded by the address recorder, the comparator will output an enable control signal to control the corresponding row in the operation array 31 to perform a swap (SWAP).

Finally, the values calculated and output by the first operation cell 110A in each cycle will be recorded in the internal memory of the control circuit 30, and the memory 32 will be updated at the same time. Specifically, in this clock cycle, the internal memory of the control circuit 30 and the first row of the memory 32 will be updated. Since only the first operation cell 110A in the first row outputs the logic value 0 in this clock cycle, only the first cell in the first row of the internal memory of the control circuit 30 and the memory 32 is written with the logic value 0.

In FIG. 4E , in this clock cycle, the first operation cell 110A in the first row generates a control signal op_out corresponding to pass (PASS). After being activated, the operation cell 110 in the second row stores the last four cells [0 1 1 0] of the second row in the row group matrix, and simultaneously receives the value [0 1 0 1 1] of the first row of the row group matrix. Therefore, the first operation cell 110A in the second row generates a control signal op_out corresponding to swap (SWAP), and updates the sorting matrix accordingly. Finally, the logic value 0 output by the first operation cell 110A in the first row, that is, the control signal op_out corresponding to pass (PASS), will be recorded in the internal memory of the control circuit 30 and the first cell of the second row in the memory 32.

In FIG. 4F , the first operation cells 110A in the first to third rows of the pulse array 31 respectively determine the functions of passing (PASS), adding (ADD) and starting (INIT). Here, the first operation cell 110A in the second row of the pulse array 31 is explained, which generates the judgment result that the row is to perform the addition (ADD) function. Therefore, in the next clock cycle, the operation cell 110 in the row will add the received value and the stored value and output it. But in fact, the first operation cell 110A in the row will output the received logic value 1 as the control signal op_out corresponding to the addition (ADD) function.

In general, in the following Figures 4F to 4P, the data values from the fifth to the last row in the row group matrix will be input into the first row of the pulse array 31 in time sequence, and each row of the pulse array 31 will be calculated according to the received data after activation, and the values output by the pulse array 31 will be written into the internal memory of the control circuit 30 and the third to the third to last row in the memory 32 in sequence.

In addition, the first operation cells 110A in the third to fifth rows of the pulse array 31 store data value 1 in the clock cycles of Figure 4F, Figure 4H, and Figure 4K, respectively, so the sorting matrix records the values 5, 7, and 10 in the third to fifth cells, respectively.

In FIG. 4Q , after all row data values of the row group matrix are input into the pulse array 31, the external enable signal ext_en is provided to the first row of the pulse array 31, and the control signal op_in corresponding to the SWAP function is also input from the outside, so that the first row of the pulse array 31 releases the row data value stored therein and transmits it to the next row of the pulse array 31. Moreover, in the following cycles of FIG. 4R to FIG. 4Z , by providing appropriate external enable signals ext_en and corresponding control signals op_in, the operation cells 110 of each row can release their stored values row by row.

In addition, in FIG. 4Q to FIG. 4U , the control signal check_en will be sequentially provided to the first operation cell 110A in each row. Referring to FIG. 2D , the sequentially enabled control signal check_en will cause the first operation cell 110A in each row to check whether the stored value is 1 step by step. In this embodiment, when the value stored in a first operation cell 110A is 0, the first operation cell 110A will generate a termination signal to terminate the calculation of the input matrix R currently received by the Gaussian elimination calculation system 3, give up in the early stage of the calculation, and request to update the input matrix R to calculate the public key based on the next input matrix R. Therefore, only when the values stored in all the first operation cells 110A are non-zero, the control circuit 30 of the Gaussian elimination calculation system 3 will calculate the next row of the group matrix, thereby avoiding wasting invalid calculation time.

On the other hand, please refer to FIG. 4R and FIG. 4S . When the pulse array 31 completes writing the last row of the internal memory of the control circuit 30 and the memory 32, compared with configuring a larger memory block to continue to store the next row of data generated by the pulse array 31, the Gaussian elimination calculation system 3 uses the unused memory blocks in the upper half of the internal memory of the control circuit 30 and the memory 32, that is, the upper right triangle block in the storage space of the internal memory of the control circuit 30 and the memory 32 to store the next output value of the pulse array 31. In other words, when the pulse array 31 completes writing the last row of the internal memory of the control circuit 30 and the memory 32, the pulse array 31 will loop back to the internal memory of the control circuit 30 and the first row of the memory 32, and align the end of the first row for writing, so as to write the generated operation result into the unused upper right triangle block in the storage space of the internal memory of the control circuit 30 and the memory 32.

Please refer to Figure 3A and Figure 3D. In order to write the calculation results into the unused upper right triangle block in the internal memory of the control circuit 30 and the memory 32 storage space, the calculation results generated by the pulse array 31 will be written into the memory 303 and the memory 32 respectively through the multiplexers MUX1 and MUX3. Specifically, the multiplexers MUX1 and MUX3 can receive two sets of inputs A and B, and the multiplexers MUX1 and MUX3 can select bit by bit through the selection signal S. For example, in the clock cycle shown in Figure 4S, the selection signal S can select the first bit of input A to pass and the second to fifth bits of input B to pass, so that the combined output C is written into the memory 303 and the memory 32.

Finally, the matrix decomposition result of the first row group matrix will be as shown in FIG4Z. In addition, please refer to FIG5A to FIG5C to understand how the pulse array 31 configures the operation result in the memory 32. FIG5A to FIG5C are schematic diagrams showing how the pulse array 31 in FIG3A writes to the memory 32. In detail, as shown in FIG5A, since the operation cells 110A in the first to fifth columns of the pulse array 31 are opened and closed in the order of columns during the matrix decomposition operation, that is, the first operation cell 110A in the first column will be opened first and complete the calculation earliest, whereas the first operation cell 110A in the fifth column will be opened last and complete the calculation last. Therefore, the calculation results of each column output by the first operation cell 110A in the pulse array 31 are arranged according to the output timing to form a parallelogram as shown in Figure 5A. In detail, the horizontal axis direction in Figures 5A to 5C represents the output value of each first operation cell 110A in the first to fifth columns of the pulse array 31, and the vertical axis direction represents the timing of each first operation cell 110A in the pulse array 31 generating the output value.

As shown in FIG5A , the calculation results generated by the pulse array 31 include data blocks 500 and 501. Data block 500 is the lower triangular matrix generated by the PLU matrix decomposition, and data block 501 is the upper triangular matrix generated by the PLU matrix decomposition. In data block 500, since the pulse array 31 receives each column of the row group matrix in row order, the calculation results recorded in data block 500 are also arranged in the row order of the row group matrix. In addition, in the write timing of the data block 501 (please refer to FIGS. 4R to 4Z), taking the row data value stored in the first row of the pulse array 31 as an example, the first row data value stored in the pulse array 31 is the first to be output, as shown in FIGS. 4R and 4S. When the second row operation cell 110 of the pulse array 31 receives the unit value of the first row in the upper triangular matrix U outputted by the first row operation cell 110 of the pulse array 31, the second row operation cell 110 of the pulse array 31 will first pass (PASS) and then output the unit value of the second row in the upper triangular matrix U by swapping (SWAP). Therefore, in data block 501, that is, the calculation results recorded in the upper triangular matrix U are also arranged in the order of the columns of the row group matrix CB1.

If the calculation results generated by the pulse array 31 in each clock cycle are stored in a single row of data blocks, as shown in FIG5A , the memory 32 needs to use a larger memory space than the input row group matrix to store them, resulting in a burden on the hardware. As shown in FIG5B , in this embodiment, in order to save memory space, the memory 32 will be configured with a memory space of the same size as the row group matrix to store the calculation results of the pulse array 31. When the pulse array 31 completes writing to the last row of the memory 32, the pulse array 31 will loop back to the first row of the memory 32 for writing. More specifically, when looping back to the first row of memory 32 for writing, the pulse array 31 will align the end of each row of memory 32 for writing, so as to write the calculation result into the unused space at the end of the row of memory 32, thereby effectively saving the memory space required by the Gaussian elimination calculation system 3. From the perspective of data space configuration, data block 500 will be divided into two data blocks 502 and 503, wherein data block 502 has the same number of rows as the row group matrix. Data block 503 and data block 501 in the lower half triangle of data block 500 will be filled above data block 502, thereby generating a rectangular calculation result configuration result as shown in FIG5C.

Figures 6A to 6D show schematic diagrams of the process of performing matrix decomposition operations on the operation matrix M. In Figures 6A to 6D, the data stored in the memory 32, the sorting circuit 302 of the control circuit 30, and the memory 303 are shown. More specifically, the memory 32 stores the operation matrix M in decomposition, and the sorting circuit 302 stores the sorting matrix P.

In FIG. 6A , following FIG. 4Z , the first row group matrix CB1 of the sorting matrix M has completed the matrix decomposition operation and is written to the memory 32 and the memory 303 of the control circuit 30 . Since the matrix decomposition operation is an operation performed in columns, the Gaussian elimination calculation system 3 will then reproduce the operation of the first row group matrix on the second row group and the third row group, and then perform the matrix decomposition operation on the second row group.

Specifically, when performing a replay operation, all operation cells 110 of the pulse array 31 will be turned on, and the first operation cell 110A will also be switched to the replay operation mode. In this way, all operation cells 110 will operate according to the external control signal op_in.

The second row group matrix can be input to the pulse array 31, and the memory 303 of the control circuit 31 stores the control signal op_out generated when the first row group matrix performs the matrix decomposition operation, which represents the operation behavior of each row of the first row group matrix when the matrix decomposition operation is performed. Therefore, by sequentially inputting the row data of each row of the second row group matrix to the pulse array 31, and providing each row control signal op_out stored in the memory 303 to the corresponding row of the pulse array 31, the operation of the first row group matrix when performing the matrix decomposition operation can be reproduced on the second row group. More specifically, in the first clock cycle, the first row of the second row group matrix may be input to the pulse array 31 as the input row data_in, and the first unit value of the first row of the control signal op_out stored in the memory 303 will also be provided to the first row of the pulse array 31 as the control signal op_in. In the second clock cycle, the second row of the second row group matrix may be input to the pulse array 31 as the input row data_in, and the first unit value of the second row of the control signal op_out stored in the memory 303 will also be provided to the first row of the pulse array 31 as the control signal op_in. In the third clock cycle, the third row of the second row group matrix can be input to the pulse array 31 as the input row data_in, and the first and second unit values of the second row of the control signal op_out stored in the memory 303 will also be provided as the control signal op_in to the first and second rows of the pulse array 31. In this way, the pulse array 31 will receive the same control signal op_in as the first row group matrix when performing the matrix decomposition operation, so that the operation of the first row group matrix is reproduced on the second row group matrix. Similarly, in the next clock cycle, each column of the second row group matrix will be provided to the pulse array 31 in sequence, and the memory 303 of the second control circuit 301 will provide the control signal op_in to each column of the pulse array 31 in the form of a parallelogram as shown in FIG. 5A .

On the one hand, each cell of the control signal op_in records a logic value of a bit, and its logic value 0 corresponds to, for example, a pass (PASS) function, and its logic value 1 corresponds to, for example, an addition (ADD) function. On the other hand, the sorting circuit 302 can also refer to the first five cells of the sorting matrix P stored therein to instruct a swap (SWAP) operation. More specifically, the values recorded in the first five cells of the sorting matrix P correspond to the timing sequence when the first to fifth columns of the pulse array 31 are swapped (SWAP), and the sorting circuit 302 can control each column in the pulse array 31 to perform a swap operation in the corresponding clock cycle accordingly. For example, when the first five cells in the sorting matrix P record the values [3 4 5 7 10], the sorting circuit 302 can control the first to fifth columns of operation cells 110 in the pulse array 31 to perform row-column swaps in the third, fourth, fifth, seventh and tenth clock cycles.

By observing FIG. 5A , it can be seen that the control signal op_in provided to the pulse array 31 has a parallelogram characteristic when arranged according to the time axis, which represents that at the beginning of the operation of the first row group CB1 of the pulse array 31, the operation cells 110 in the first row will be activated to perform the operation, and the operation cells 110 in the second to fifth rows will be activated in sequence in the subsequent operation. At the end of the operation, the operation cells 110 in the first row will end the operation first, and the operation cells 110 in the second to fifth rows will be completed in sequence in the subsequent operation. In some embodiments, the repetition operation of the second row group and the third row group can be input to the pulse array 31 in a manner of partially overlapping the row groups. For example, when the reproduction operation of the second row group CB2 reaches the end, that is, the first row of operation cells 110 in the pulse array 31 has completed the operation but the second to fifth rows of operation cells 110 in the pulse array 31 are still operating, the value of the first row of the third row group CB3 can be continuously input into the first row of operation cells 110 in the pulse array 31, so that the first row of operation cells 110 in the pulse array 31 can perform the reproduction operation of the third row group CB3. In this way, the pulse array 31 can utilize the complementary characteristics of the control signal op_in at the beginning and end of the reproduction operation, so that the pulse array 31 can simultaneously perform the reproduction operation at the end of the second row group and the reproduction operation at the beginning of the third row group in part of the clock cycle. Therefore, the computational scheduling of the pulse array 31 can be more compact, so as not to waste computational resources and time.

Therefore, as shown in FIG6A , after completing the reproduction operation of the second row group and the third row group, the pivot row selected in the first row group will be moved to the bottom five rows of the second row group and the third row group, and the calculation results of the remaining rows will be arranged at the top. Then, the Gaussian elimination calculation system 3 will perform matrix decomposition operation on the second row group.

FIG6B shows the matrix decomposition result of the second row group. In the matrix decomposition process of the second row group, the columns above the axis columns in the second row group will be sequentially input to the pulsating array 31 operating under the triangular operation mode to generate the decomposition result of the second row group, and the order of the sixth to tenth axis columns is recorded in the sixth to tenth cells of the ordering matrix.

In FIG. 6C , the third row group matrix will be reproduced according to the decomposition result of the second row group matrix. More specifically, the first ten columns of the third row group matrix will be input to the pulse array 31 operating in the square matrix operation mode to perform the reproduction operation according to the decomposed second row group matrix and the sixth to tenth cells in the sorting matrix, so that the axis column selected by decomposing the second row group will be moved to the sixth to tenth columns.

Finally, in FIG. 6D , the third row group matrix will be subjected to matrix decomposition operation. In the matrix decomposition process of the third row group, the first to fifth columns above the axis columns of the third row group will be sequentially input to the pulsating array 31 operating under the triangular operation mode to generate the decomposition result of the third row group, and the order of the eleventh to fifteenth axis columns is recorded in the eleventh to fifteenth cells of the ordering matrix.

After calculating the sorting matrix P, the lower triangular matrix L, and the upper triangular matrix U, the next step is to multiply the inverse matrix L ^-1 of the lower triangular matrix L and the sorting matrix P by the target matrix T as shown in the above formula (3).

7A to 7C are schematic diagrams showing the calculation process of multiplying the inverse matrix L ^-1 of the lower triangular matrix L and the sorting matrix P by the target matrix T.

As shown in FIG. 7A , the lower triangular matrix portion of the first row group matrix CB1 stored in the memory 32 will first be copied to the memory 303 through the selection of the multiplexer 34, and will be used to reproduce the target matrix T in conjunction with the first five cells of the sorting matrix P. Similarly, in FIG. 7B , the second row group matrix CB2 and the sixth to tenth cells of the sorting matrix will be used to reproduce the target matrix T. Until FIG. 7C , the last third row group matrix CB3 and the eleventh to fifteenth cells of the sorting matrix will be used to reproduce the target matrix T. After completing the operations of FIG. 7A to FIG. 7C , the calculation process of L ^-1 . P. T in the above formula (3) is completed.

Next, the Gaussian elimination calculation system 3 performs a recurrence operation on the target matrix T according to the inverse matrix U ^-1 of the upper triangular matrix U, so as to calculate the calculation process of U ^-1 . (L ^-1 .P.T). For details, please refer to the following formula (4) for the relationship between the upper triangular matrix U and the inverse matrix U ^-1 .

According to the above formula (4), when performing the multiplication of the inverse matrix U ^-1 , it can be equivalent to using the unit values of the upper triangular matrix U, wherein the unit value calculation of the last row of the upper triangular matrix U must precede the second-to-last row, and the unit value calculation of the second-to-last row must precede the third-to-last row, and so on. Therefore, in order to realize the calculation sequence derived from the above formula (4), the control circuit 30 can write the values in the upper triangular matrix U into the memory 303 in the second control circuit 301 through the method and sequence shown in Figures 8A to 8C, thereby realizing the multiplication of the inverse matrix U ^-1 .

FIG. 8A to FIG. 8C are schematic diagrams showing how to calculate and obtain the public key matrix PK based on the inverse matrix U ^-1 of the upper triangular matrix U.

As shown in FIG8A, the inversion process of the upper triangular matrix U will be performed on the third row group matrix CB3 on the upper right first. In the first to fifth columns of the third row group matrix CB3, the units marked with a value of 1 are the diagonal units generated after decomposition, so in the inversion process of the upper triangular matrix U, only the units U12~U15, U23~U25, U34~U35, and U45 are inverted and stored in the memory 303 according to the position correspondence relationship shown in FIG8A. Furthermore, the sixth to fifteenth columns below the third row group matrix will continue to the cells U12-U15, U23-U25, U34-U35, and U45 whose order has been adjusted above without adjusting the arrangement order, thereby generating the result shown on the right side of FIG. 8A. Specifically, the sixth to fifteenth columns below the third row group matrix can be input to the pulse array 31 operating in the triangle operation mode, and the first control circuit 300 provides a suitable external enable signal ext_en and a control signal ext_op to the pulse array 31, so that the pulse array 31 operates in the shift buffer mode and generates the arrangement relationship shown in FIG. 8A. Compared to using an additional shift register to arrange the sixth to fifteenth columns below the third row group matrix, the same effect can be achieved by operating the pulse array 31 in the triangular operation mode in the shift buffer mode, thereby effectively reducing the hardware requirements and cost of the Gaussian elimination calculation system 1. Finally, the inverse matrix U ^-1 of the upper triangular matrix U stored in the memory 303 will be used for the reproduction operation. Furthermore, in Figures 8B and 8C, the second row group matrix and the first row group matrix will be inverted in sequence and used for the reproduction operation. After completing the operations of Figures 8A to 8C, the overall U ^-1 in the above formula (3) is completed. (L ^-1 .P.T) is calculated, and the public key matrix PK is calculated.

FIG9 shows a flow chart of the Gaussian elimination calculation method of the first embodiment of the present invention. The Gaussian elimination calculation method includes steps S90 to S92. The Gaussian elimination calculation method can be applied to the Gaussian elimination calculation system 1 of FIG1 and/or the Gaussian elimination calculation system 3 of FIG3. In step S90, the operation matrix is input to the Gaussian elimination calculation system. In step S91, the operation matrix is input to the pulse array in the Gaussian elimination calculation system to perform matrix decomposition operation to decompose the operation matrix into a lower triangular matrix and an upper triangular matrix. In step S92, a computing data block of the same size as the computing matrix is configured in the memory of the Gaussian elimination computing system, and the decomposed lower triangular matrix and upper triangular matrix are stored in the computing data block. For detailed operation contents of the Gaussian elimination computing method, please refer to the above operation instructions for Gaussian elimination computing systems 1 and 3.

In summary, the Gaussian elimination calculation method and Gaussian elimination calculation system of the present invention can efficiently utilize memory space and save ineffective calculation time, effectively improving the efficiency and hardware requirements of public key calculation.

1: Gaussian elimination calculation system

10: Control circuit

11: Pulsating array

12: Memory

R: Input matrix

Claims (20)

A Gaussian elimination computing system includes: a control circuit receiving an operation matrix; a systolic array including a square matrix formed by a plurality of operation cells, the systolic array being configured to perform a matrix decomposition operation on the operation matrix to decompose the operation matrix into a lower triangular matrix and an upper triangular matrix; and a memory configured with an operation data block having the same size as the operation matrix, for storing the decomposed lower triangular matrix and the upper triangular matrix when performing the matrix decomposition operation. As described in claim 1, the Gaussian elimination calculation system, wherein the control circuit divides the operation matrix into a plurality of row group matrices, each of which has the same number of columns as the operation matrix, and the control circuit inputs each of the row group matrices into the pulse array to perform the matrix decomposition operation. A Gaussian elimination calculation system as described in claim 2, wherein the control circuit provides multiple columns of each row group matrix to a first column of multiple columns in the pulse array in column order, and each column of the pulse array receives an input column matrix from the previous column or from the control circuit, generates an output column matrix after operation, and transmits the output column matrix to the next column of each column. A Gaussian elimination computing system as described in claim 3, wherein the computing cells include: a plurality of first computing cells arranged on a diagonal line in the pulse array; and a plurality of second computing cells arranged outside the diagonal line in the pulse array, wherein when the pulse array operates in a triangular operation mode, the first computing cells are operated in a decomposition operation mode, and the second computing cells arranged below the diagonal line are closed, Each of the first operation cells generates a control signal according to a received first data value and a stored second data value to control the second operation cells in the same row to perform the same operation as the first operation cell; when the pulse array operates in an array operation mode, all of the operation cells are turned on and the first operation cells are operated in a recurrence operation mode, and the operation cells in each row receive a control signal together to perform the same operation. A Gaussian elimination computing system as described in claim 4, wherein the operations performed by the operation cells include one of shift, addition, exchange, and activation. A Gaussian elimination computing system as described in claim 4, wherein after completing the operation on each row group matrix, each first computing cell checks whether each second data value stored therein is zero. A Gaussian elimination calculation system as described in claim 6, wherein when it is detected that any of the second data values is zero, the pulse array terminates the operation of the operation matrix and requests to update the operation matrix. As described in claim 2, the Gaussian elimination calculation system, wherein when the pulse array writes the calculation results of each row group matrix into the memory, the pulse array writes from the first row of the memory in a manner aligned with the head of the row in the memory, and when the pulse array completes writing the last row of the memory in row order, the pulse array loops back to the first row of the memory and writes thereafter in a manner aligned with the tail of the row in the memory. The Gaussian elimination calculation system as described in claim 8 further includes a multiplexer coupled between the pulse array and the memory, and the multiplexer is used to receive a selection signal to selectively write the calculation results of each row group matrix into the memory according to the bit. A Gaussian elimination calculation system as described in claim 1, wherein the control circuit receives an input matrix and obtains the operation matrix and a target matrix by distinguishing the input matrix, wherein the input matrix, the operation matrix and the target matrix have the same number of columns, wherein the control circuit also records a sorting matrix to record the sorting of all columns of the operation matrix in the matrix decomposition operation, and the control circuit controls the pulse array to calculate the target matrix according to the sorting matrix, the upper triangular matrix and the lower triangular matrix to obtain a common key matrix. A Gaussian elimination calculation method includes: receiving a calculation matrix; inputting the calculation matrix into a systolic array to perform a matrix decomposition operation, and decomposing the calculation matrix into a lower triangular matrix and an upper triangular matrix; and configuring a calculation data block of the same size as the calculation matrix in a memory, and storing the decomposed lower triangular matrix and the upper triangular matrix in the calculation data block when performing the matrix decomposition operation. As described in claim 11, the Gaussian elimination calculation method, wherein the step of inputting the operation matrix into the pulse array to perform the matrix decomposition operation includes: dividing the operation matrix into a plurality of row group matrixes, each of which has the same number of columns as the operation matrix, and inputting each of the row group matrixes into the pulse array to perform the matrix decomposition operation. As described in claim 12, the step of inputting each row group matrix into the pulse array to perform the matrix decomposition operation includes: providing multiple columns of each row group matrix to a first column of multiple columns in the pulse array in column order, and each column of the pulse array receives an input column matrix from the previous column or from the control circuit, generates an output column matrix after operation, and transmits the output column matrix to the next column of each column. The Gaussian elimination calculation method as described in claim 13, wherein the pulse array includes a plurality of operation cells, the operation cells include: a plurality of first operation cells, arranged on a diagonal line in the pulse array; and a plurality of second operation cells, arranged at positions outside the diagonal line in the pulse array, the Gaussian elimination calculation method includes: when the pulse array operates in a triangular operation mode, the first operation cells operate in a decomposition operation mode, The second operation cells arranged below the diagonal line are turned off, and each of the first operation cells generates a control signal according to a received first data value and a stored second data value to control the second operation cells in the same row to perform the same operation as the first operation cell; and when the pulse array operates in an array operation mode, all of the operation cells are turned on, and the operation cells in each row receive a control signal together to perform the same operation. The Gaussian elimination calculation method as described in claim 14, wherein the operations performed by the operation cells include one of shift, addition, exchange, and activation. The Gaussian elimination calculation method as described in claim 14 also includes, after completing the operation on each row group matrix, each first operation cell checks whether each second data value stored therein is zero. The Gaussian elimination calculation method as described in claim 16 also includes terminating the operation of the operation matrix and requesting to update the operation matrix when any of the second data values is detected to be zero. The Gaussian elimination calculation method as described in claim 12 further includes: when the pulse array writes the operation results of each row group matrix into the memory, the pulse array writes from the first row of the memory in a manner aligned with the head of the row in the memory, and when the pulse array completes writing the last row of the memory in row order, the pulse array loops back to the first row of the memory and writes thereafter in a manner aligned with the tail of the row in the memory. The Gaussian elimination calculation method as described in claim 18 further includes receiving a selection signal by coupling a multiplexer between the pulse array and the memory, so as to selectively write the operation results of each row group matrix into the memory according to the bit. As described in claim 11, the step of receiving the operation matrix includes: receiving an input matrix, and obtaining the operation matrix and a target matrix by distinguishing the input matrix, the input matrix, the operation matrix and the target matrix have the same number of columns, and the Gaussian elimination calculation method further includes: recording a sorting matrix to record the sorting of all columns of the operation matrix in the matrix decomposition operation, and calculating the target matrix according to the sorting matrix, the upper triangular matrix and the lower triangular matrix by the pulse array to obtain a public key matrix.