Circuits for modular arithmetic based on the complementation of continued fractions
OwnerDejan Lazich, Herbert Alrutz +1inventors
InventorsDejan Lazich, Herbert Alrutz, Christian Senger
Life of this patent
Estimating the term…
Abstract
A method for calculating a modular multiplication of integers a and b or polynomials a(x) and b(x) for a modulus N. The method including (i) calculating a supplemental product continued fraction c=(ab+jN)/t by supplementing particular numerators of a product fraction (ab)/t represented as a continued fraction, and (ii) calculating a second supplemental product continued fraction r=(cd+kN)/t from a previously calculated modular remainder d=RN[t2] and the calculated supplemental product continued fraction c.
Claims11
A method for performing a calculation, where in a first case the calculation is a modular multiplication RN[ab] of integers for a modulus N, where the integers a and b, which are less than the modulus N, and the modulus N are presented using a radix ρ, and where in a second case the calculation is a modular multiplication RN(x)[a(x)b(x)] of polynomials for a modulus polynomial N=N(x), where the polynomials a=a(x) with degree(a(x))<degree(N(x)) and b=b(x) with degree(b(x))<degree(N(x)) and the modulus polynomial N(x) are presented using powers of a free variable x and coefficients from a ring ZM of integers modulo M, the method comprising:
- calculating a supplemental product continued fraction c=(ab+jN)/t by supplementing particular numerators of a product fraction (ab)/t represented as a continued fraction, where in the first case c and j are integers and t=ρK, where in the second case c=c(x) and j=j(x) are polynomials having coefficients from the ring ZM and t=t(x)=xK, and where in the first and the second cases K is an integer greater than or equal to a length Λρ(a) of the operand a which is broken down in the continued fraction;
- and
- calculating a second supplemental product continued fraction r=(cd+kN)/t from a previously calculated modular remainder d=RN[t2] and the calculated supplemental product continued fraction c, where in the first case r, k and d are integers, where in the second case r=r(x)=RN(x)[a(x)b(x)], k=k(x) and d=d(x) are polynomials having coefficients from the ring ZM.
A circuit for modular arithmetic with at least one unit for calculating and supplementing particular numerators of a product fraction ab/t presented as a continued fraction using a radix ρ, comprising:
- a register Reg b having K register cells (b0, b1, . . . , bK−1) for all digits of a multiplicand b;
- a register Reg N having K register cells (N0, N1, . . . , NK−1) for all digits of a modulus N;
- at least one of
- (i) a working register Reg w having K+2 work register cells (w0, w1, . . . , wK+1);
- and
- (ii) a working memory which is accessible through a data bus interface having a width of p bits, and a microprocessor which controls and supervises the working memory and the data bus interface;
- a memory cell a0 for a digit of a multiplicand a;
- a memory cell i0 for a supplementation factor;
- K multipliers (Mb0, Mb1, . . . MbK−1) that multiply digits (b0, b1, . . . , bK−1) with a digit of the multiplicand a;
- K multipliers (MN0, MN1, . . . MNK−1) that multiply digits (N0, N1, . . . , NK−1) with the supplementation factor;
- and
- K adders (A0, A1, . . . , AK−1) that add particular results of the multiplication with a digit of the multiplicand a and the multiplication with the supplementation factor, each adder Ak having a plurality of inputs;
- where if ρ≠2
- a first input of the multiplier Mbk is connected with the output of the register cell bk, a second input of the multiplier Mbk is connected with the output of the memory cell a0, and two outputs of the multiplier Mbk are each connected with one of the inputs of the adder Ak;
- a first input of the multiplier MNk is connected with the output of the register cell Nk, a second input of the multiplier MNk is connected with the output of the memory cell i0, and two outputs of the multiplier MNk are each connected with one of the inputs of the adder Ak;
- a first output of the adder Ak is connected with the work register cell wk, and where k<K−1 two other outputs of the adder Ak are each connected with one of the inputs of the adder AK+1;
- and
- a first output of the adder AK−1 is connected with an input of the work register cell wK and a second output of the adder AK−1 is connected with an input of the register cell wK+1;
- and
- where if ρ=2
- the first input of the multiplier Mbk is connected with the output of the register cell bk, the second input of the multiplier Mbk is connected with the output of the memory cell a0, and two outputs of the multiplier MNk are connected with one of the inputs of the adder Ak;
- the first input of the multiplier MNk is connected with the output of the register cell Nk, the second input of the multiplier MNk is connected with the output of the memory cell i0 and an output of the multiplier MNk is connected with one of the inputs of the adder Ak;
- the first output of the adder Ak is connected with the work register cell wk, for and where k<K−1 the two other outputs of the adder Ak are each connected with one of the inputs of the adder AK+1;
- and
- the first output of the adder AK−1 is connected with the input of the work register cell wK and second output of the adder AK−1 is connected with the input of the register cell wK+1;
- characterized in that the circuit has a circuit Con for determining the supplementation factor for the supplementation of numerators of the product continued fraction, the output of the multiplier Mb0 being additionally connected with inputs of the circuit Con and one output of the circuit Con being connected with an input of the memory cell i0.
Dependencies are inferred from the claim text.