A binary logic circuit is provided for determining a rounded value of $\frac{\mathrm{px}}{q},$
where p and q are coprime constant integers with p<q and q2.sup.i, i is any integer, and x is an integer variable between 0 and integer M where M2q, the binary logic circuit implementing in hardware the optimal solution of the multiply-add operation $\frac{\mathrm{ax}+b}{2^k}$
where a, b and k are fixed integers.

There is provided a modular multiplication device for performing a multiplication of a first multiplicand and a second multiplicand modulo a given modulus, each of the multiplicand comprising a given number of digits, each digit having a given word size. The modular multiplication device comprises: a multiplier for multiplying at least one digit of the first multiplicand with the second multiplicand to produce a multiplier output; a modular reduction unit configured to reduce a quantity derived from the multiplier output by the product of an extended modulus and an integer coefficient, the extended modulus being the product of the given modulus with an extension parameter, which provides a reduction output, the reduction output being a positive integer strictly smaller than the extended modulus, wherein the modular multiplication device further comprises a selection unit configured to select the extension parameter such that the time taken for the device to perform the multiplication is independent from the multiplicands.

Montgomery multiplier architectures are provided. A circuit can include an initial processing element (PE) circuit configured to generate a first output including (i) a radix of a carry out and (ii) a radix of an intermediate result based on radixes of respective operands, a radix of an inverse of a modulus, and a radix of the modulus, middle PE circuits configured to generate a second output including (i) respective radixes of a Montgomery multiplication result and (ii) further respective radixes of a carry out on two consecutive clock cycles based on the first output, and a final PE circuit configured to generate further radixes of the Montgomery multiplication results on two consecutive, subsequent clock cycles based on the second output.

An elliptic curve scalar multiplication apparatus stores a prime number p and information of a first point, the prime number p defining a field of definition F.sub.p, which defines a first curve, which is a Weierstrass form elliptic curve, and expressed as p=p.sub.0+p.sub.1c+ . . . +p.sub.1c.sup.n1, (where c equals 2.sup.f and f is an integer equal to or larger than 1 that is units of breaking data into pieces in multiple-precision integer arithmetic executed by the elliptic curve scalar multiplication apparatus), calculates a Montgomery constant k.sub.0, work, and h.sub.1, executes doubling of a second point, which is calculated from the first point, by Montgomery multiplication that uses k.sub.0, work, and h.sub.1, adds a third point and fourth point, which are calculated from the first point, by Montgomery multiplication that uses k.sub.0, work, and h.sub.1; and calculates a scalar multiple of the first point, based on a result of the doubling and the addition.

In a multiplexer circuit which loads N data segments (N is an integer of N<M) led by an arbitrary data segment from a first register storing M data segments (M is an integer equal to or larger than two) to a second register, an intermediate register is disposed between the first register and the second register. A first selection circuit between the first register and the intermediate register and a second selection circuit between the intermediate register and the second register are designed based on a value of L for minimizing a circuit amount of the first selection circuit and the second selection circuit. The value of L for minimizing the circuit amount is calculated based on values of the M and the N. Therefore, it is possible to reduce the circuit amount of the multiplexer circuit capable of performing data access with respect to large-volume data.

A method comprises receiving a modulus for a number-theoretic transform of a polynomial and selecting a plurality of prime moduli whose product forms the modulus for the number-theoretic transform, wherein the plurality of prime moduli are selected by giving preference to prime moduli having fewer ones in a binary representation of the prime moduli. For each prime modulus in the plurality of prime moduli: dividing a coefficient of the polynomial into segments and performing modular reduction of the segments relative to the prime modulus. Performing the modular reduction of at least one segment comprises implementing a multiplication of a value by a modular reduction of a base value relative to the prime modulus using a shift-add-unit having a smaller area requirement than a modular multiplier. A modular reduction of the coefficient relative to the prime modulus is determined based on the modular reductions of the segments.

A processor-implemented method with a polynomial multiplication operation includes obtaining an auxiliary modulus corresponding to moduli according to a Chinese remainder theorem (CRT), performing a number theoretic transform (NTT) operation with respect to the auxiliary modulus on a result of a modulo operation of the moduli for each of a first polynomial and a second polynomial, performing an element-wise multiplication operation between an NTT operation result corresponding to the first polynomial and an NTT operation result corresponding to the second polynomial, and transforming a result of the element-wise multiplication operation into a polynomial corresponding to each of the moduli.

A method of operating a homomorphic encryption operation accelerator includes performing a number theoretic transform (NTT) operation on each of first homomorphic ciphertext and second homomorphic ciphertext, and performing a base conversion operation by adding a partial sum using a first value of the NTT operation.

A method for performing modular multiplication of a first multiplicand and a second multiplicand in a cryptographic engine, the method including calculating an integer corresponding with an inverse of a modulus based on a number of bits in the modulus, a digit size of the modular multiplier and a fixed size coefficient. The method also includes calculating a result of the modular multiplication using a plurality of modular reduction coefficients determined using the integer and respective digits of the multiplicands, the result less than an upper size limit that is based on the size coefficient and the modulus. The method further includes determining a final result of the modular multiplication based on a difference between the result and the modulus. If the difference is less than zero, the result is the final result, and if the difference is greater than or equal to zero, the difference is the final result.

A modular multiplier includes a random number generator that generates a random number, a memory that stores at least one lookup table including results of pre-computed modular arithmetic, and a processor that obtains results of modular arithmetic on partial products defined by a product of a first polynomial corresponding to a first input and a second polynomial corresponding to a second input with reference to the at least one lookup table, and generates a result of modular arithmetic on a product of the first input and the second input based on addition arithmetic of the obtained results of the modular arithmetic. The processor randomly determines at least one of an order of the addition arithmetic or an acquisition order of modular arithmetic results on the partial products based on the random number generated by the random number generator.