CIRCUITS FOR MODULAR ARITHMETIC BASED ON THE COMPLEMENTATION OF CONTINUED FRACTIONS

摘要

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=R_N[t²] and the calculated supplemental product continued fraction c.