KR100606437B1 - Polynomial Multipliers and Methods in Extensions - Google Patents

Abstract

Disclosed are a polynomial multiplier and method in an extension. The search unit searches for ^{k such} that the order n of the extension input for the predetermined division order S exists between the lower boundary value S ^k-1 and the upper boundary value S ^k . State value determination section lower boundary value S ^k-1 and the upper bound value S a plurality of divided sections formed by division by the division value of a small plurality of intervals between the ^k than the lower boundary value larger upper bound value that is less than S ^k-1 S ^k The upper boundary value of the division section to which the order n of the extension belongs is determined as a state value. The optimum order determination unit determines the value obtained by the equation n '= State ^Sk-2 as the optimal extension body order. Where n 'is the optimal extension order and State means the state value. According to the present invention, even in the case where the degree of extension is relatively large, in the case of coefficient-multiplication, the amount of calculation can be reduced by three times or more.

Extended, Polynomial Multiplication, Order, State, Amount

Description

Apparatus for performing polymomual multiplication in extension field and method

1 is a block diagram showing the configuration of a preferred embodiment of a polynomial multiplication apparatus in an extension according to the present invention;

2 is a flow chart showing the implementation of a preferred embodiment for an efficient polynomial multiplication method in an extension according to the present invention;

Figure 3 is a flow chart showing the implementation of another preferred embodiment for the efficient polynomial multiplication method in the extension according to the present invention,

4 is a diagram showing the result of comparing the coefficient-multiplication calculation amount of the conventional KO method and the KO method to which Algorithm 1 is applied, and

FIG. 5 is a diagram illustrating the results of applying the algorithm according to the present invention to a conventional multi-splitting Karaschva method.

The present invention relates to a polynomial multiplication apparatus and method in an extension, and more particularly, to a polynomial multiplication apparatus and a method capable of efficiently performing multinomial multiplication by a multi-part Karashiba method.

Most public key cryptosystems based on factoring problems, discrete algebraic problems, etc. are based on exponential operations. Exponential operations have advantages and disadvantages depending on the algorithms, and the efficiency of these algorithms is based on the amount of multiplication operations. Thus, the efficient construction of finite multiplication operations has been a hot topic in hardware and software for a long time and is being actively studied. Algorithm efficiency is based on resource usage and complexity, and complexity is the biggest criterion for determining the value of an algorithm. In general, if the size of the fin is n, the approximate complexity is expressed as O (n).

Prime mul sqr add sub 175 bit 0.672 0.656 0.034 0.047 89bit 0.187 0.162 0.031 0.043 62 bit 0.109 0.102 0.031 0.042 31bit 0.0156 0.0063 0.0047 0.0047

In extension GF (p ⁿ ), complexity refers to the amount of computation between addition, subtraction, and multiplication between coefficients. Of these, the amount of multiplication is the largest part of the calculation, so it takes a lot of weight when measuring complexity. Table 1 shows the rate of GF (p) measured in P4VC 2.8 and is in μsec.

Hereinafter, addition, subtraction, and multiplication operations between coefficients are referred to as #ADD, #SUB, and #MUL. In addition, time delay is also an important consideration in binary implementations implemented in hardware. The time delay of addition and subtraction between coefficients is denoted by T _X (time delay of XOR gate), the multiplication operation is denoted by T _A (AND gate time delay), and the total time delay is denoted by T _TOT . Mark it. In the case of general extension p ⁿ , the amount of computation between coefficients is an important criterion of complexity, and in the case of binary data with p = 2, the amount of gates and time delay must be considered at the same time. ) And space complexity. In the present invention, it is considered based on the case of the general extension rather than the binary, and using the results according to the present invention, it is also easy to analyze the binary environment.

In general extension, polynomial multiplication can be divided by the following criteria.

◆ Basal body multiplication configuration

◆ Extended Body Multiplication by Multiplication Method

◆ Composition of Multiplication Operations by Selection of Contracted Polynomials

In the extension, the base can be divided into Polynomial Basis and Normal Basis. Polynomial basis is widely used in both software and hardware, but in the case of regular basis, it is simply composed of shift operation in case of square, but it is suitable for hardware environment because it is based on matrix operation in case of multiplication. Inappropriate. In addition, the amount of addition computation is determined during the modular reduction operation according to the selection of the contract polynomial. Therefore, in general, the smaller the hemming weight of the contracted polynomial, the more efficiently it is constructed. However, in the case of the All-One Polynomial, the hemming weight is the highest, but there is an environment that is more efficient than these. Currently, ternary polynomials, pentagonal polynomials, and all-one polynomials are the main research subjects.

Various multiplication methods exist, but all of them consist of a general multiplication method, the Karatsuba-Ofman (KO) method, or a variation of these methods. The main difference between these two methods is the difference in the method of multiplication between the coefficients. The main difference between these two multiplication methods is to transform the multiplication between the coefficients to reduce the multiplication between the coefficients and increase the number of additions. In the general expansion GF (p ⁿ ), the multiplication between coefficients is much more complicated than the addition between coefficients, so if the multiplication between coefficients decreases, the efficiency increases. As it is composed of one gate as described above, the amount of multiplication is reduced, which does not necessarily mean that the efficiency increases. In the present invention, an analysis result of the polynomial multiplication method is presented, and it is irrelevant to the problem of selection of the contract polynomial when using a general polynomial basis and the result of the present invention.

The Karatsuba-Ofman method is an efficient way to reduce the extended body multiplication. M as a way to increase the efficiency of the Karasuba method. Leon proposes a low complexity parallel processing multiplier for finite bodies and presents the concept of optimal number of iterations. However, the Karashiba method has a problem that is applied only when the degree of the expansion body is a multiple of 2. This problem is M. This is largely complemented by the multi-part Karasuba method proposed by Ernst et al. But M. Ernst et al. Do not present the complexity of the multi-part Karasuba method, and there are difficulties in practical application of the method. In order to overcome the problems of the multi-division Karasuba method, a more efficient multi-division Karasuba method and complexity have been proposed.

Hereinafter, a description will be given of a method of constructing a conventional extended body multiplication.

Existing extension multiplication is divided into SchoolBook (SB) multiplication method, Karatsuba-Ofman multiplication method, and Multi-Segment Karatsuba method according to polynomial multiplication method, and successive extension method also exists. do.

The multiplication between elements of the finite field GF (p ⁿ ) generated by the nth order polynomial f (x) in GF (p) will be described. By polynomial basis, the elements a (x) and b (x) of GF (p ⁿ ) are expressed as

At this time, a _i , b _i ∈ GF (p).

Multiplication of the extension is a polynomial multiplication process that multiplies the two elements a (x) and b (x) of the extension as n-1 polynomials, and 2n-2nd polynomial expressed by the following equation as a result of multiplication: It is divided into modulo reduction, which is the process of finding the remainder divided by the next contract polynomial f (x).

For efficient multiplication, we need to optimize polynomial multiplication and modulo reduction.

First, the SB multiplication method will be described.

이다. 따라서 곱셈의 연산량은 a(x)의 전체 계수의 수와 b(x)의 전체 계수의 수를 곱한 만큼 필요하므로 n×n=n² 번의 계수-곱셈 연산이 필요하며 덧셈의 연산량은 c(x)의 n-1차를 기준으로 대칭이므로 수학식 3에 의해 산출된 횟수의 계수-덧셈 연산이 필요하다. Polynomial multiplication of finite element using the SchoolBook (SB) method

to be. Therefore, the amount of multiplication needs to be multiplied by the total number of coefficients of a (x) and the total number of coefficients of b (x), so n × n = n ^two coefficient-multiplication operations are needed. Since the symmetry is based on the n-1th order of), the coefficient-add operation of the number of times calculated by Equation 3 is required.

Therefore, the calculation amount is as follows.

Next, we will look at the KO multiplication method.

The basic KO method in GF (p ⁿ ) is the divide-and-conquer method by double-dividing a finite element. If n / 2 is even, KO may be applied repeatedly. Therefore, the operation can be performed when n = 2 ^m · t (m ≠ 0) in the extension GF (p ⁿ ). By applying KO directly to the n-1th polynomial, log ₂ n iterations can be performed.

On the other hand, the coefficient-addition operation is divided into two processes in the multi-part Karashiba method. The first is the operation of the input value of the n / 2 bit polynomial multiplier, and the second is the operation of the output value of the n / 2 bit polynomial multiplier. If we repeat the KO method once, we need 2 (n / 2) XOR gates in the first process n / 2 bit addition, (A ₀ + A ₁ ), (B ₀ + B ₁ ) and the second process 3n-4 XOR gates are required for the addition operation between the output values A ₀ B ₀ , A ₁ B ₁ , (A ₀ + A ₁ ) (B ₀ + B ₁ ) and the coefficients of the n / 2th-order multiplier. Therefore, assuming that KOA performs m iterations and uses the least significant multiplier SB multiplier,

According to the above results, the parallel processing multiplier using the KO method has lower spatial complexity than the parallel processing multiplier using the SB method. In addition, the multi- split Karasuma method suggested the optimized number of repetitions of KOA as ^k when n / 2 ^k = 4.

Next, we will look at the multi-part Karashiba multiplication method.

The MSK multiplication method extends the KOA method to divide and multiply the elements of the finite body by multiples. Assuming that n (mod k) = 0 in the finite field GF (2 ⁿ ), the multiplication of two elements can be performed by the k-multiplexed Karasuba (MSK _k ) method. If n (mod k) ≠ 0, fill as many coefficients as needed. This section describes a parallel processing multiplier using multiple partitions. This is simply described as a 5-segment example. Assuming that n = 5 ^mt (m ≠ 0) in GF (2 ⁿ ), a (x) and b (x) ∈ GF (2 ⁿ ) are subdivided into five divisions.

Thus, the multiplication of the bits c (x) is

Here, d (x) is as follows.

■ The multiplication of all MSK methods is classified into the following processes.

* STEP 1: Addition operation before polynomial multiplication

STEP 2: Polynomial Multiplication

STEP 3: Add operation after polynomial multiplication

Hereinafter, the complexity of the five-slicing Karasuba method for each classified step will be described.

First, coefficient-addition in GF (p ⁿ ) of the partitions of the input value is performed for multiplication of the MSK ₅ method in STEP1. Thus A ₀ + A ₁ , B ₀ + B ₁ , A ₀ + A ₁ + A ₃ + A ₄ , B ₀ + B ₁ + B ₃ + B ₄ are the n / 5-first order coefficients between the coefficients of the partitions, respectively. Because it is an addition operation, it is performed by 18 · n / 5 coefficient-addition operations.

Secondly, in STEP2, A ₀ B ₀ , A ₁ B ₁ ,. , (A ₃ + A ₄ ) (B ₃ + B ₄ ), (A ₀ + A ₁ + A ₃ + A ₄ ) (B ₀ + B ₁ + B ₃ + B ₄ ) is the n / 5-1 order Since it is a multiplication, 14 · (TOT _{n / 5} ) operations are performed.

Finally, in STEP3, the addition (subtraction) operation of the 14 sub-multiplication results is performed. The result of each of the sub-multiplications is 2 · (n / 5-1) difference, and considering the redundant operation, the coefficient-add operation 11 · (2 · n / 5-1) and 12 · (2 · n / 5-1) Count-subtraction operations are required, and each term requires 8 · (n / 5-1) count-add operations because n / 5-1 coefficients are duplicated. Therefore, the calculation amount in case of repeating the MSK ₅ method m times is as follows.

When the sub-multiplication method is configured by the SB method after m iterations using the calculation result of Equation 9, the calculation amount is as follows.

STEP1 reduces the amount of sub-multiplication by using pre-counting-add operation of input values using patterns to reduce the amount of multiplication in MSK. Therefore, the result of precomputation is used as the input value of the sub-multiplication. STEP2 performs n / 5-1th order sub-multiplication operation using the result of precomputation, and the result is outputted through coefficient-addition (subtraction) operation between each coefficient of STEP3 and overlapping orders. .

에서 m≠0이라 가정하면 MSK_p의 최적화된 반복횟수는 n/p^k≠p를 만족하는 k이다. The split-conquer method takes place in time and space complexity. Therefore, as the number of iterations increases, the time complexity increases, but the space complexity is effectively reduced. Assuming n = p ^m t, a maximum of m iterations can be performed. M is not an optimized number of iterations. This is because the SB multiplier at GF (2 ^p ) has a lower spatial complexity than MSK _p . Therefore M. Applying the elliptic curve encryption method for GF (2 ^p ) proposed by Ernst et al.

Assuming that m ≠ 0 at, the optimized number of iterations of MSK _p is ^k, which satisfies n / p ^k ≠ p.

On the other hand, the Successive Extension (SE) method has an advantage when n is composed of a small number (2, 3, ...) in the extension GF (p ⁿ ). The amount of calculation of the multiplication, square, and inverse calculation according to the environment is shown in Table 2.

Environment MUL SQR INV Pledge polynomial Basis ADD MUL ADD MUL ADD MUL INV x ² +1 Polynomial basis 5 3 3 2 2 4 One x ² -2 Polynomial basis 6 3 2 3 3 4 One x ² + x + 1 ONB TYPE 1 4 3 4 2 2 4 One x ² -x-1 Regular basis 4 3 3 3 2 4 One x ² -x + 1 Regular basis 4 3 4 2 2 4 One

의 곱셈을 고려할 때, SE 방법은 다음의 수학식과 같이 연속적으로 계수-곱셈을 수행한다.

Considering the multiplication of, the SE method performs coefficient-multiplication continuously as in the following equation.

의 경우 일반적으로 구성하면 All- One-Polynomial을 사용할 수 없으나 SE방법의 경우 사용이 가능하다. therefore,

In case of general configuration, you cannot use All-One-Polynomial, but in case of SE method, you can use it.

The advantages and disadvantages of the existing and SE methods are listed in Table 3.

When GF (p) → GF (p ⁿ ) is configured at once When using the SE method Advantages Perform n modular subtraction operations. Does not depend on extension order -Optimize addition (subtraction) operations. Choose from a variety of basis and contract polynomials. Disadvantages Limited by base choice Limited by the choice of the contract polynomial -The order of extension should consist of a small number of products. -Whenever expanding continuously, modular subtraction operation should be performed.

Referring to Table 3, the existing method is limited in the selection of the basis selection and the contract polynomial. In addition, the SE method is limited to a case where the order of the extension is composed of a small number of products, and there is a problem that a modular subtraction operation must be performed each time it is continuously extended.

SUMMARY OF THE INVENTION The present invention has been made in an effort to provide a polynomial multiplication apparatus and method in an extension that can reduce the amount of computation of coefficient multiplication despite an increase in the order of the expansion.

In order to achieve the above technical problem, in a preferred embodiment of the polynomial multiplication apparatus in an extension according to the present invention, the order n of the extension input for a predetermined division order S is higher than the lower boundary value S ^k-1. A search unit for searching k to exist between the boundary values S ^k ; The lower boundary value of S ^k-1 and the higher threshold S ^k a plurality of divided sections to section the lower boundary value of S ^k-1 larger and formed by dividing by the upper boundary value of a division value of the smaller plurality than S ^k between A state value determination unit that determines, as a state value, an upper boundary value of a division section to which the order n of the extension belongs; And an optimum order determining unit that determines the value obtained by the equation n '= State ^Sk-2 as an optimal extension body order. Where n 'is the optimal extension order and State means the state value.

In order to achieve the above technical problem, another preferred embodiment of the polynomial multiplication apparatus in the expansion body according to the present invention is that the order n of the input expansion body is larger than the lower boundary value 2 ^k -2 ^k -2 and the upper boundary value 2. a searcher for searching k such that ^{k + 1} −2 ^k −1 or less; The division section to which the order n of the extension belongs among the plurality of division sections formed by the division values composed of 3 · 2 ^k-2 , 2 ^k , 5 · 2 ^k-2 , and 6 · 2 ^k-2 . A state value determining unit which determines an upper boundary value as a state value; And an optimum order determining unit that determines the value obtained by the equation (n '= State.2k ^-1) as the optimal extension body order. Where n 'is the optimal extension order and State means the state value.

In order to achieve the above technical problem, a preferred embodiment of the polynomial multiplication method in an extension according to the present invention, the order n of the extension input for the predetermined division order S is equal to the lower boundary value S ^k-1 . Retrieving k such that it exists between upper boundary values S ^k ; The lower boundary value of S ^k-1 and the higher threshold S ^k a plurality of divided sections to section the lower boundary value of S ^k-1 larger and formed by dividing by the upper boundary value of a division value of the smaller plurality than S ^k between Determining an upper boundary value of a division section to which the order n of the extension belongs among the state values; And determining the value obtained by the equation n '= State ^Sk-2 as an optimal extension body order. Where n 'is the optimal extension order and State means the state value.

Another preferred embodiment of the polynomial multiplication method in an extension according to the present invention for achieving the above another technical problem is that the order n of the input extension is greater than the lower boundary value 2 ^k -2 ^k -2 and the upper boundary value. Searching k such that it is less than or equal to 2 ^{k + 1} -2 ^k-1 ; The division section to which the order n of the extension belongs among the plurality of division sections formed by the division values composed of 3 · 2 ^k-2 , 2 ^k , 5 · 2 ^k-2 , and 6 · 2 ^k-2 . Determining an upper boundary value as a state value; And determining the value obtained by the equation n '= State · 2 ^k−1 as the optimal extension body order. Where n 'is the optimal extension order and State means the state value.

Thereby, even in the case where the degree of extension is relatively large, the computation amount can be reduced by three times or more in the case of coefficient-multiplication.

Hereinafter, with reference to the accompanying drawings will be described in detail a preferred embodiment of the polynomial multiplication apparatus and method in the extension according to the present invention.

First, a method for efficiently constructing polynomial multiplication in an arbitrary extension GF (p ⁿ ) will be described. In the present invention, a method for minimizing the coefficient-multiplication amount is described since the general extension environment is considered. By applying the KO method, the smaller the value of t is, the better the efficiency is when the degree of extension is n = 2 ^m t. In other words, if the degree of the extension consists of a small number or a product of relatively large numbers, it is substantially inefficient. However, since the degree of the extension body proposed in the standard document is mostly a minority in consideration of safety, a countermeasure for an extension body having a minority order is necessary.

First, a method of selecting an optimal extended body order using the KO method will be described.

Polynomial multiplication using the KO method satisfies the following two properties. Since the KO method is not applied when the degree of the extension is odd, it is assumed that the SB method is used.

Auxiliary Theorem 1. (When the KO Method is Applied to Polynomial Multiplication)

The order of the contract polynomial is n and #MUL is the coefficient-multiplication of polynomial multiplication. If n is even and n> 8, the following equation is satisfied.

Since n is even, n = 2t, where t is an integer greater than one. In the case of the n-first extension, the SB method is applied so that the amount of coefficient-multiplication is #MUL _DB (n-1) = (2t-1) ² . And when the order of the extension is n, once the KO method is applicable, #MUL _KO (n) = 3t ² . Therefore, if #MUL _DB (n-1)>#MUL _KO (n), it is represented by the following equation.

At this time, since t is a positive integer, t> 4 is required to satisfy the inequality. That is, when n is greater than 8, #MUL _DB (n-1)>#MUL _KO (n). According to supplementary theorem 1, it is more efficient to apply the KO method to the order n + 1 by adding 0 as the nth coefficient if n is odd. Also, if n is even, if #MUL _DB (n-1)>#MUL _KO (n), then #MUL _KO (2n)> 3 · MUL _SB (n), so #MUL _KO (2 (n-1) )>#MUL _KO (2n) holds. This can be summarized as follows.

Theorem 2. (When the KO Method is Applied to Polynomial Multiplication)

Assume that the order of the polynomial polynomial is n and #MUL is the coefficient-multiplication of polynomial multiplication, and n = 2 ^k t and satisfies auxiliary theorem 1. If k is a positive integer and t> 4, then

Theorem 2 is easily proved by Supplementary Theorem 1. The results of Auxiliary Theorem 1 and Theorem 2 show that the coefficient-multiplication is small even if the degree of extension is large. For example, polynomial multiplication at GF (p ²⁵⁸ ) is 49,923, but polynomial multiplication at GF (p ³²⁰ ) is 18,225, which is approximately 2.5 times smaller. Can be. Therefore, it is necessary to configure so that the complexity of coefficient-multiplication in any extension is optimized.

Algorithm 1: Construction of an Efficient Polynomial Multiplication Using the KO Method

INPUT: order n of extension

OUTPUT: Higher order n '

1. Find k with 2 ^k -2 ^k-2 <n ≤ 2 ^{k + 1} -2 ^k-1 .

2. If k <3, the general KO method is applied.

3. Find one of the following three cases.

3.1. If 3 · 2 ^k-2 <n ≤ 2 ^k, State = 4.

3.2. If 2 ^k <n ≤ 5 · 2 ^k-2, State = 5.

3.3. If 5 · 2 ^k-2 <n ≤ 6 · 2 ^k-2, State = 6.

4. Return n '= State · 2 ^k-2 .

When configured at n 'rather than the order n of the extension as input, it has a smaller coefficient-multiplication complexity. Therefore, when n <n 'in Algorithm 1, a polynomial multiplication operation is constructed by padding n'-n zeros. Using Algorithm 1, it is possible to obtain an order having the smallest coefficient-multiplication when performing a polynomial multiplication process using the KO method for an extension having an arbitrary order. The result of using the algorithm above and the result using the conventional method are as follows.

Order (n) KO method Algorithm 1 7 49 27 22 363 243 60 2,025 729 76 3,249 2,025 92 4,761 2,187 122 11,163 2,187 146 15,987 6,075 180 18,225 6,561 234 41,067 6,561 298 66,603 18,225 370 102,675 19,683 394 116,427 19,683

Applying Algorithm 1, as shown in Table 4, it is possible to find and configure the most efficient order in the existing KO method. In addition, as the degree of the extension increases, the coefficient-multiplication operation amount may be reduced by several tens of times or more.

Next, the optimal extension order selection using the MSK ₃ method will be described.

Polynomial multiplication using the MSK ₃ method satisfies the following properties: In the case of 3-middle division, the order of extension is applied to multiples of 3, so if n is a multiple of 3, n-1 and n-2 are not multiples of 3, so the SB method is used to perform polynomial multiplication.

Auxiliary Theorem 3. (When MSK3 Method is Applied to Polynomial Multiplication)

The order of the contract polynomial is n and #MUL is the coefficient-multiplication of polynomial multiplication. If n = 3t, then

If t≥2:

If t≥3:

When n is equal to 3t according to Auxiliary Theorem 3, 3t 'is the smallest coefficient-multiplication among 3t'-2, 3t '-1, and 3t'. Therefore, if the degree of expansion is greater than 9, only the degree of expansion is considered to be a multiple of three.

Theorem 4. (When applying polynomial multiplication of the MSK ₃ method)

If the order of the contract polynomial is n (3 ^k-1 <n <3 ^k ) and #MUL is the coefficient-multiplication of polynomial multiplication,

One.

2.

3.

4.

Where k> 0.

이다. 정리 4에서 2의 경우, n=t·3^k-2라 하면, t는 3 < t < 4의 범위를 가져야하므로 만족하는 경우가 없으며, n=t·3^k-3이라 하면, t는 3² < t < 4·3의 범위를 가지므로

이다. 따라서 보조정리 3에 의하여 정리 4에서 2의 경우는 만족한다. 정리 4에서 3의 경우, n=t·3^k-2라 하면, 4 < t < 2·3이므로

이다. 따라서 보조정리 3에 의하여 정리 4에서 3의 경우는 만족한다. 정리 4에서 4의 경우, n=t·3^k-2라 하면, 2·3 < t < 3²이므로

이고 보조정리 3에 의하여 4번째 성질도 만족한다.Assistance Theorem 3 can be easily proved, so detailed proof is omitted. In case of theorem 4 to 1, if the triple division method is repeated once by the multi-sharing Karashuba method, six sub-multiplications are formed.

to be. In the theorem 4 to 2, if n = t · 3 ^k-2 , t must be in the range of 3 <t <4, and there is no case to satisfy. If n = t · 3 ^k-3 , t is 3 ² <t <4 · 3

to be. Therefore, in theorem 3, the case of theorem 4 to 2 is satisfied. For theorem 4 to 3, let n = t · 3 ^k-2 , since 4 <t <2 · 3

to be. Therefore, the theorem 4 to 3 is satisfied by the auxiliary theorem 3. In the case of theorem 4 to 4, let n = t · 3 ^k-2 <t <3 ² so

In addition, the fourth property is satisfied by the auxiliary theorem 3.

The properties of Auxiliary Theorem 3 and Theorem 4 can be summarized as follows.

Algorithm 2: Construction of an Efficient Polynomial Multiplication Using the MSK ₃ Method

INPUT: order n of extension

OUTPUT: Higher order n '

Return n if n <3

2. Find ^k that satisfies 3 ^k-1 <n ≤ 3 ^k .

3. Find the case that applies to you.

3.1. If 3 ^k-1 <n ≤ 4 · 3 ^k-2, State = 4.

3.2. If 4 · 3 ^k-2 <n ≤ 2 · 3 ^k-1, State = 6.

3.3. If 2 · 3 ^k-1 <n <3 ^k, State = 9.

4. Return n '= State · 3 ^k-2 .

Next, the optimal extension order selection using the MSK ₅ method will be described.

Polynomial multiplication using the MSK ₅ method satisfies the following properties: In the case of 5-middle division, the degree of expansion is applied only when it is a multiple of 5. Since n-4 is not a multiple of 5, the SB method is applied when performing polynomial multiplication.

Auxiliary Theorem 5. (When Polynomial Multiplication of MSK ₅ Method is applied)

If the order of the contract polynomial is n and #MUL is the coefficient-multiplication of polynomial multiplication, n = 5t,

When the t is greater than 4 when n = 5t according to the auxiliary theorem 6, 5t'-4, 5t'-3, 5t'-2, 5t'-1, and 5t 'are the most coefficient-multiplications. small. Therefore, if the degree of the expansion body is greater than 20, only the degree of expansion of 5 is considered.

Theorem 6. (When applying polynomial multiplication of the MSK5 method)

If the order of the weak polynomial is n (5 ^k-1 <n ≤ 5 ^k ) and #MUL is the coefficient-multiplication of polynomial multiplication, the following is satisfied.

One.

2.

3.

4.

5.

6.

7.

At this time, k> 1.

Consider the second case of Theorem 6 as an example. For n present in the range, if there is no satisfying t, then the case does not exist in A by theorem 5. Thus proof is derived as in the case of MSK3.

The algorithm is constructed using the auxiliary theorem 6 and theorem 7 as follows.

Algorithm 3: Construction of an Efficient Polynomial Multiplication Using the MSK ₅ Method

INPUT: order n of extension

OUTPUT: Higher order n '

1. If n <4, return n.

2. If n = 4, 5, n = 5 is returned.

3. Find ^k that satisfies 5 ^k-1 <n ≤ 5 ^k .

4. Find the case below that applies to you.

4.1. If 5 ^k-1 <n ≤ 6 · 5 ^k-2, State = 6.

4.2. If 6 · 5 ^k-2 <n ≤ 7 · 5 ^k-2, State = 7.

4.3. If 7 · 5 ^k-2 <n ≤ 2 · 5 ^k-1, State = 10.

4.4. If 2 · 5 ^k−1 <n ≦ 11 · 5 ^k−2, State = 11.

4.5. If 11 · 5 ^k-2 <n ≦ 3 · 5 ^k-1, State = 15.

4.6. When 3 · 5 ^k−1 <n ≤ 5 ^k, State = 25.

5. Return n '= State · 5 ^k-2 .

1 is a block diagram showing the configuration of a preferred embodiment of a polynomial multiplication apparatus in an extension according to the present invention.

Referring to FIG. 1, the polynomial multiplication apparatus 100 in the expanded body according to the present invention includes a search unit 110, a state value determiner 120, an optimum order determiner 130, and a controller 140. .

The search unit 110 searches for ^{k such} that the order n of the extension input for the predetermined division order S exists between the lower boundary value S ^k-1 and the upper boundary value S ^k . State determination unit 120 is formed by dividing by the lower boundary value of S ^k-1 and the upper bound value of S divided value of a small plurality of sections than the lower boundary value larger upper bound value that is less than S ^k-1 S ^k between the ^k The upper boundary value of the divided section to which the order n of the extension belongs among the plurality of divided sections is determined as a state value. The optimum order determiner 130 determines the value obtained by the following equation as an optimal extension body order.

n '= StateSk ^-2 ,

Where n 'is the optimal extension order and State means the state value.

The controller 140 controls the operation of other components.

The polynomial multiplication apparatus 100 having the above configuration is a hardware implementation of the algorithms 2 and 3 described above. Therefore, when the algorithm 2 is applied to the polynomial multiplication apparatus 100, that is, when the division order S is 3, the division values are defined as 4 · S ^k-2 and 2 · S ^k-1 . At this time, when the order n of the extension is smaller than the division order S, the optimum order determination unit 130 determines the order n of the extension as the optimal extension. In contrast, when algorithm 3 is applied to the polynomial multiplier 100, that is, when the division order S is 5, the division values are 6 · S ^k-2 , 7 · S ^k-2 , 2 · S ^k-1 , 11 · S ^k-2 and 3 · S ^k-1 . At this time, when the order n of the extension is smaller than the value obtained by subtracting 1 from the division order S, the optimum order determiner 130 determines the order n of the extension as the optimal extension order, and the order n of the extension is divided. If the value S is subtracted from the order S or equal to the division order S, the division order S is determined as the optimal extension body order.

On the other hand, the polynomial multiplication apparatus that implements the above-described algorithm 1 also has substantially the same configuration as shown in FIG. In the case of the polynomial multiplier with Algorithm 1, the function of each component is as follows.

The search unit 110 searches ^{k such} that the order n of the input extension is greater than the lower boundary value 2 ^k -2 ^k -2 and less than or equal to the upper boundary value 2 ^{k +1} -2 ^k -1. In this case, the order n of the extension is even, and k is greater than or equal to three. The state value determining unit 120 includes an extension body of a plurality of divided sections formed by divided values composed of 3 · 2 ^k-2 , 2 ^k , 5 · 2 ^k-2 , and 6 · 2 ^k-2 . The upper boundary value of the division section to which order n belongs is determined as a state value. The optimum order determiner 130 determines the value obtained by the following equation as an optimal extension body order.

n '= State 2 ^k-1 ,

Where n 'is the optimal extension order and State means the state value.

Figure 2 is a flow chart showing the implementation of a preferred embodiment for an efficient polynomial multiplication method in an extension according to the present invention.

Referring to FIG. 2, the search unit 110 searches for ^{k such} that the order n of the extension input for the predetermined division order S exists between the lower boundary value S ^k-1 and the upper boundary value S ^k ( S200). State determination unit 120 is divided by a lower boundary value of S ^k-1 and the upper bound value S dividing the value of the smaller plurality is greater than the upper bound value S ^k the interval between the ^k than the lower boundary value of S ^k-1 The upper boundary value of the divided section to which the order n of the extension belongs among the plurality of divided sections is determined as a state value (S210). The optimum order determiner 130 determines the value obtained by the following equation as an optimal extension body order.

n '= StateSk ^-2 ,

Where n 'is the optimal extension order and State means the state value.

In the above description, the optimal extension order according to the division value, the order of extension and the magnitude of the extension is the same as that of Algorithm 2 and Algorithm 3 described with reference to FIG. 1.

Figure 3 is a flow chart showing the implementation of another preferred embodiment for an efficient polynomial multiplication method in the extension according to the present invention.

Referring to FIG. 3, the search unit 110 may determine that the order n of the input extension is greater than the lower boundary value 2 ^k −2 ^k −2 and less than or equal to the upper boundary value 2 ^{k + 1} −2 ^k −1. Search k (S300). At this time, the order n of the extension is even, and k is greater than or equal to three. The state value determining unit 120 expands the body into a plurality of divided sections formed by the divided values composed of 3 · 2 ^k-2 , 2 ^k , 5 · 2 ^k-2 , and 6 · 2 ^k-2 . The upper boundary value of the division section to which the order n belongs is determined as a state value (S310). The optimum order determiner 130 determines the value obtained by the following equation as an optimal extension body order.

n '= State 2 ^k-1 ,

Where n 'is the optimal extension order and State means the state value.

According to the efficient polynomial multiplication apparatus and method in the expansion body according to the present invention, it is possible to reduce the number of coefficient-multiplication operations more than ten times more than the conventional polynomial multiplication method. In other words, the efficient polynomial multiplication apparatus and method in the expansion body according to the present invention serve as a design criterion for each polynomial multiplication method. FIG. 4 is a diagram illustrating a result of comparing coefficient-multiplication calculation amounts of a conventional KO method and a KO method to which algorithm 1 is applied. Referring to FIG. 4, in the conventional KO method, the coefficient-multiplication operation amount is rapidly increased as the degree of the polynomial is increased. However, when the algorithm 1 is applied, the coefficient-multiplication operation amount is not increased much.

On the other hand, Table 5 shows a comparison result of the coefficient-multiplication calculation of the conventional MSK ₃ method and Algorithm 2 applied method.

n = 15 n = 30 n = 52 n = 79 n = 105 n = 120 n = 159 n = 241 n = 319 MSK ₃ 150 600 2,704 6,241 7,350 9,600 16,854 58,081 101,761 Algorithm 2 144 576 864 1,296 3,456 5,184 5,184 7,776 20,736

Table 6 also shows a comparison result of the coefficient-multiplication calculation of the conventional MSK5 method and the algorithm 3 method.

n = 10 n = 40 n = 60 n = 80 n = 140 n = 160 n = 230 n = 260 n = 380 MSK ₅ 56 896 2,016 3,584 10,976 14,336 29,624 37,856 80,864 Algorithm 2 56 784 1,764 2,744 7,056 9,604 10,976 23,716 38,416

Table 5 and Table 6 show the result of comparing the coefficient-multiplication amount of the method using the multi-division Karasuba method and the coefficient-multiplication calculation amount when the algorithm 2 is applied among the multiplication methods according to the present invention. Referring to Tables 5 and 6, it can be seen that the result of applying the multiplication method according to the present invention is more efficient as the degree of extension is increased. In addition, although the MSK method has not yet been generalized, it can be seen that the efficiency increase is much greater than that of the conventional SE method.

FIG. 5 is a diagram illustrating the results of applying the algorithm according to the present invention to a conventional multi-splitting Karaschva method. Referring to FIG. 5, the algorithm according to the present invention is a form in which the conventional MSK method limits the coefficient-multiplication calculation amount that is irregular according to the extension order to the most efficient order. In this case, it is possible to easily verify that the coefficient-addition (subtraction) amount is also efficient based on the complexity proposed in the multi-part Karaschba method by using the order of the extension returned from the algorithm according to the present invention.

If the existing MSK ₅ performs m iterations, the lowest complexity can be obtained by constructing the multiplier with the lowest SB method.

On the other hand, Ernst's method has an unnecessary pattern. Therefore, eliminating unnecessary patterns can reduce the multiplication amount than the conventional MSK method. If the new MSK ₅ performs m iterations, the lowest complexity can be achieved by constructing the multiplier at the lowest level using the SB method.

Therefore, it is more effective than the Successive Extension method, which cannot be applied to various orders, and is particularly effective when applied to extensions with decimal orders. The multiplication method according to the present invention can be easily extended in the case of a binary body of p = 2, which can be usefully used when designing hardware having a small complexity.

The invention can also be embodied as computer readable code on a computer readable recording medium. The computer-readable recording medium includes all kinds of recording devices in which data that can be read by a computer system is stored. Examples of computer-readable recording media include ROM, RAM, CD-ROM, magnetic tape, floppy disk, optical data storage, and the like, and may also be implemented in the form of a carrier wave (for example, transmission over the Internet). Include. The computer readable recording medium can also be distributed over network coupled computer systems so that the computer readable code is stored and executed in a distributed fashion.

Although the preferred embodiments of the present invention have been shown and described above, the present invention is not limited to the specific preferred embodiments described above, and the present invention belongs to the present invention without departing from the gist of the present invention as claimed in the claims. Various modifications can be made by those skilled in the art, and such changes are within the scope of the claims.

According to the polynomial multiplication apparatus and method in the expansion body according to the present invention, in the case of coefficient-multiplication, the amount of computation can be reduced by three times or more, even when the degree of the expansion body is relatively large. Not limited to the degree of expansion.

Claims (14)

A search unit for searching k such that the order n of the extension input for the predetermined division order S exists between the lower boundary value S ^k-1 and the upper boundary value S ^k ; The lower boundary value of S ^k-1 and the higher threshold S ^k a plurality of divided sections to section the lower boundary value of S ^k-1 larger and formed by dividing by the upper boundary value of a division value of the smaller plurality than S ^k between A state value determination unit that determines, as a state value, an upper boundary value of a division section to which the order n of the extension belongs; And A polynomial multiplication apparatus for an extension, comprising: an optimum order determination unit for determining an optimal extension order value obtained by the following equation: n '= StateSk ^-2 , Where n 'is the optimal extension order and State means the state value. The method of claim 1, And the division values S are 3, wherein the division values are 4 · S ^k-2 and 2 · S ^k-1 . The method of claim 2, And the optimum order determining unit determines the order n of the extension as an optimal extension body when the order n of the extension is smaller than the division order S. The method of claim 1, When the division order S is 5, the division values are 6 · S ^k-2 , 7 · S ^k-2 , 2 · S ^k-1 , 11 · S ^k-2 , and 3 · S ^k-1 Polynomial multiplier in the expansion body, characterized in that. The method of claim 4, wherein If the order n of the extension is less than the value obtained by subtracting 1 from the division order S, the optimum order determination unit determines the order n of the extension as an optimal extension body, and the order n of the extension is the division order. And a dividing order S is determined to be an optimal extension order if the value of 1 subtracted from S or the division order S is determined. Retrieving k such that the order n of the extension input for the predetermined division order S exists between the lower boundary value S ^k-1 and the upper boundary value S ^k ; The lower boundary value of S ^k-1 and the higher threshold S ^k a plurality of divided sections to section the lower boundary value of S ^k-1 larger and formed by dividing by the upper boundary value of a division value of the smaller plurality than S ^k between Determining an upper boundary value of a division section to which the order n of the extension belongs among the state values; And Determining a value obtained by the following equation as an optimal extension order; a polynomial multiplication method for an extension including: n '= StateSk ^-2 , Where n 'is the optimal extension order and State means the state value. The method of claim 6, And in the case where the division order S is 3, the division values are 4 · S ^k-2 and 2 · S ^k-1 . The method of claim 7, wherein And the order n of the extension is smaller than the division order S, and the order n of the extension is determined to be the optimal extension order. The method of claim 6, When the division order S is 5, the division values are 6 · S ^k-2 , 7 · S ^k-2 , 2 · S ^k-1 , 11 · S ^k-2 , and 3 · S ^k-1 Polynomial multiplication method in the extension, characterized in that. The method of claim 9, If the order n of the extension is smaller than the value obtained by subtracting 1 from the division order S, the order n of the extension is determined as the optimal extension body, and the order n of the extension is subtracted 1 from the division order S. The polynomial multiplication method according to claim 1, wherein the dividing order S is determined to be an optimal extension order if the value is equal to the division order S. Retrieving k so that the order of the input extension member n is less than or equal to the lower boundary value 2 ^k -2 greater than the upper bound value ^{k-2 2 k + 1 -2} k-1 search unit; The division section to which the order n of the extension belongs among the plurality of division sections formed by the division values composed of 3 · 2 ^k-2 , 2 ^k , 5 · 2 ^k-2 , and 6 · 2 ^k-2 . A state value determining unit which determines an upper boundary value as a state value; And A polynomial multiplication apparatus for an extension, comprising: an optimum order determination unit for determining an optimal extension order value obtained by the following equation: n '= State 2 ^k-1 , Where n 'is the optimal extension order and State means the state value. The method of claim 11, The order n of the extension is an even number, wherein k is greater than or equal to 3 polynomial multiplier in the extension. Retrieving k so that the order of the input extension member n is less than or equal to the lower boundary value 2 ^k -2 greater than the upper bound value ^{k-2 2 k + 1 -2} k-1; The division section to which the order n of the extension belongs among the plurality of division sections formed by the division values composed of 3 · 2 ^k-2 , 2 ^k , 5 · 2 ^k-2 , and 6 · 2 ^k-2 . Determining an upper boundary value as a state value; And Determining a value obtained by the following equation as an optimal extension order; a polynomial multiplication method for an extension including: n '= State 2 ^k-1 , Where n 'is the optimal extension order and State means the state value. The method of claim 13, The order n of the extension is an even number, and k is greater than or equal to 3 polynomial multiplication method in the extension.

Images