CN-121996886-A - Fourier transform realization method for linearization polynomial fast processing

CN121996886ACN 121996886 ACN121996886 ACN 121996886ACN-121996886-A

Abstract

A Fourier transform implementation method for linearization polynomial fast processing realizes the alignment by constructing a recursive protocol structure of quasi-fast Fourier transform and quasi-inverse fast Fourier transform Efficient computation of batch evaluation and coefficient recovery of linearization polynomials over a finite field. The method is suitable for a class of value point sets with special structures, and can be used for integrating Degree of The problem of (2) is gradually reduced to sub-problems of smaller scale and finally complete the whole operation.

Inventors

LI JIANG
LIU SHU
YUAN CHEN
XING CHAOPING
WU TINGYI

Assignees

上海交通大学

Dates

Publication Date: 20260508
Application Date: 20260119

Claims (2)

1. A fourier transform implementation method for linearizing polynomial fast processing, comprising: step 1, setting a processing scale and a value point generation parameter, namely selecting a finite field Size parameter of (2) Parameters of number of expansions Number of value points Wherein: And is also provided with Is a typical application situation of the invention; Step 2, generating a value point set for rapid transformation, which specifically comprises the following steps: Step 2.1 initializing, setting ; Step 2.2 Generation And is provided with ; Step 2.3 Generation And is provided with , ; Step 2.4 and so on, for any integer Generating And is opposite to The structure is as follows: ; through the above construction, finally obtain Different value points ; And 3, performing quick evaluation processing on the linearization polynomial based on the value point set, wherein the quick evaluation processing comprises the following steps of: step 3.1 linearization polynomial selection in finite field On, select one Degree of In the form of a linearization polynomial of: wherein each coefficient is Belonging to ; Step 3.2 Scale reduction for evaluating questions based on the set of value points generated in step 2 The linearization polynomial is processed The evaluation problem at all the value points is defined as two Degree of The problem of evaluating the linearization polynomials on the partial value point set is solved, and the two linearization polynomials are respectively: , Wherein Is used for generating The multiplier used; Step 3.3, processing the step 3.2 to obtain two linearization polynomials at the value points respectively Repeatedly executing the above-mentioned reduction process, further decomposing it into smaller-scale linearization polynomial evaluation problem, and finally making the original one by means of multiple-step reduction treatment -Degree of Is in the linear polynomial of (2) The evaluation problem at each value point is converted into a plurality of -An evaluation operation of the degree 0 linearization polynomial at a single point of value; step 3.4, terminating the evaluation and result synthesis, namely directly giving out the evaluation result of the linearization polynomial obtained by the protocol on the corresponding value points when the linearization polynomial obtained by the protocol only contains constant terms, and sequentially synthesizing according to the protocol path to obtain the original linearization polynomial on all the value points; and 4, carrying out linear polynomial coefficient recovery processing based on the value point set, wherein the method specifically comprises the following steps: Step 4.1 coefficient recovery object setup in finite field Setting the coefficient to be recovered Linearization polynomial Which is provided with -Degree of Expressed as Wherein each coefficient is Belonging to The linearization polynomial is known to be integrated at the take point Function value of the upper part ; Step 4.2 Scale reduction of coefficient recovery problem based on the value point set structure generated in step 2 Degree of The problem of coefficient recovery of the linearization polynomial of (2) is defined as two Degree of Coefficient recovery sub-problems of the linearization polynomials of (2), the two sub-polynomials are respectively: And Wherein the set of function values Coefficient, function value set Coefficients of (2); step 4.3, recovering and synthesizing the sub-problem coefficients, namely integrating the two linearization polynomials obtained in the step 4.2 at the value points respectively Performing coefficient recovery processing on the linear polynomial, and synthesizing the coefficient of the sub-polynomial obtained by recovery according to the structural parameters introduced in the value point generation process to obtain the coefficient of the linear polynomial of the upper layer, wherein the synthesis process is completed through a predetermined coefficient transformation relationship, and the transformation relationship is in a finite field Reversible mapping is adopted, so that the uniqueness and consistency of the coefficient recovery result are ensured; step 4.4, namely repeatedly executing the step 4.2 and the step 4.3, and carrying out the step 4 for the problem of restoring the linear polynomial coefficient of which the scale is halved layer by layer until the protocol is -A degree 0 linearization polynomial, when the linearization polynomial contains only constant terms, directly determining its corresponding coefficients and synthesizing layer by layer according to a reduced path, finally recovering the original linearization polynomial Is a coefficient of the whole of the coefficients of (a).
2. The method for realizing fourier transform for linearizing polynomial fast processing according to claim 1, wherein the set of value points generated by step 2 is for any integer Satisfy the following requirements All of All have And all the value points In the finite field So that it is used to support the subsequent fast fourier transform process.

Description

Fourier transform realization method for linearization polynomial fast processing Technical Field The invention relates to a technology in the technical field of information processing and coding, in particular to a Fourier transform realization method for linearization polynomial fast processing. Background In the prior art, the batch evaluation and coefficient recovery of the linearization polynomial have higher computation complexity under the condition of a general value point, and a general technical scheme capable of realizing efficient processing in engineering is not available, so that the application of the linearization polynomial in an actual information processing system is limited. Disclosure of Invention Aiming at the problem of low calculation efficiency of the batch evaluation and coefficient recovery of the linearization polynomial in the prior art, the invention provides a Fourier transform realization method for the quick processing of the linearization polynomial, which is characterized in that a value point set meeting the constraint of a specific structure is constructed and utilized, the batch evaluation and coefficient recovery process of the linearization polynomial can be completed under a unified rapid transformation framework, so that the operation times and the intermediate data processing amount required in the calculation process are obviously reduced. Under the condition of the value point, the invention can effectively reduce the batch processing cost of the linearization polynomial on the finite field, ensures that the related calculation process has logarithmic growth characteristics, and solves the problem that the efficiency of the traditional point-by-point calculation or interpolation processing mode is limited when the processing scale is expanded. The invention is realized by the following technical scheme: The invention relates to a Fourier transform realization method for linearization polynomial fast processing, which comprises the following steps: step 1, setting a processing scale and a value point generation parameter, namely selecting a finite field Size parameter of (2)Parameters of number of expansionsNumber of value pointsWherein: And is also provided with Is a typical application of the present invention. Step 2, generating a value point set for rapid transformation, which specifically comprises the following steps: Step 2.1 initializing, setting 。 Step 2.2 GenerationAnd is provided with。 Step 2.3 GenerationAnd is provided with ,。 Step 2.4 and so on, for any integerGeneratingAnd is opposite toThe structure is as follows:。 through the above construction, finally obtain Different value points。 The set of value points generated by step 2 has the following characteristics for supporting the following fast fourier transform process: 1. For any integer Satisfy the following requirementsAll ofAll have。 2. All the value pointsIn the finite field And 3, performing quick evaluation processing on the linearization polynomial based on the value point set, wherein the quick evaluation processing comprises the following steps of: step 3.1 linearization polynomial selection in finite field On, select oneDegree ofIn the form of a linearization polynomial of: wherein each coefficient is Belonging to。 Step 3.2 Scale reduction for evaluating questions based on the set of value points generated in step 2The linearization polynomial is processedThe evaluation problem at all the value points is defined as twoDegree ofIs a problem of evaluating the linearization polynomial of (c) over a set of partial values. The two linearization polynomials are respectively:, Wherein Is used for generatingThe multiplier used. Step 3.3, processing the step 3.2 to obtain two linearization polynomials at the value points respectivelyThe above-described reduction process is repeatedly performed, which is further decomposed into smaller-scale linearized polynomial evaluation problems. Finally, the original is processed by multiple steps of reduction-Degree ofIs in the linear polynomial of (2)The evaluation problem at each value point is converted into a plurality of-An evaluation operation of the degree 0 linearization polynomial at a single point of value. And 3.4, terminating the evaluation and result synthesis, namely directly giving out the evaluation result of the linearization polynomial obtained by the protocol on the corresponding value points when the linearization polynomial obtained by the protocol only contains constant terms, and sequentially synthesizing according to the protocol path to obtain the original linearization polynomial on all the value points. Description of computational complexity by exponentiation of the required power values during the above-described processingThe batch evaluation process of the linearization polynomial can be completed in the logarithmic level protocol step by preprocessing and utilizing the structural characteristics of the value point set, and the