Fast modular multiplication system based on radix transformation

A fast modular multiplication system based on radix transformation, wherein the fast modular multiplication system comprises:

• a pre-computation layer, configured to perform radix transformation processing on first and second modular multiplication inputs A and B obtained based on a modulus q, to convert the first and second modular multiplication inputs A and B from binary to a base-X;
• a polynomial modular multiplication layer, comprising a plurality of adders and multipliers, said polynomial modular multiplication layer configured to sequentially perform, through the adders and multipliers built therein, grouped multiplication processing and recombination and reduction processing on intermediate value coefficients of the radix-transformation-processed first and second modular multiplication inputs A and B, to reduce degrees of resultant polynomial of the first and second modular multiplication inputs A and B;
• an iterative reduction layer, comprising a plurality of iterative reduction sub-layers each having a plurality of adders, said iterative reduction layer configured to sequentially perform, through the adders built therein, wiring mapping processing and accumulation processing on the recombination-and-reduction-processed polynomials containing the first and second modular multiplication inputs A and B for several times, to reduce bit widths of coefficients of a (n−1)-degree polynomial of X containing the first and second modular multiplication inputs A and B;
• and
• a base restoration layer, configured to convert, from the base X to the binary, the polynomial containing the first and second modular multiplication inputs A and B on which a last time of accumulation processing has been performed, to obtain an actual modular multiplication result.