Modular multiplication method and calculating device
AssigneeOki Electric Industry Co., Ltd.
InventorHiroshi Yamazaki
Life of this patent
Estimating the term…
Loading patent…
AssigneeOki Electric Industry Co., Ltd.
InventorHiroshi Yamazaki
Estimating the term…
To provide a modular multiplication method and a calculating device that do not rely on the Montgomery technique, wherein the number of times of multiply-add calculations is reduced to shorten a calculation time for calculation speed-up, there is no limitation in input value, and it is possible to execute a remainder calculation exceeding the calculable maximum bit length of a multiply-add unit that is used. Assuming that N=2n−M and X=α×2n+β, a relation of XmodN=(α×M+β)modN is derived, which is utilized. n represents a maximum bit number where “1” is assigned in N, a solution of 2n+1modN is set as b, A×B is set as X, XmodN is transferred to (X/2n+1×b+Xmod2n+1)modN and further transferred to (X·n/2n+1×b+X·nmod2n+1)modN, calculations of X·n/2n+1×b+X·nmod2n+1 are repeated until a bit length of X·n becomes n+1, X·n−N is derived and a derived result is set as a solution of “A×BmodN”.
A modular multiplication method for deriving a solution of “A×BmodN”, said method comprising:
A modular multiplication method for deriving a solution of “A×BmodN”, said method comprising:
A modular multiplication method for deriving a solution of “A×BmodN”, said method comprising:
A multiply-add calculating device for calculating “A×B+C”, said device comprising:
Dependencies are inferred from the claim text.