| 摘要 |
A method for calculating a conversion parameter of the Montgomery modular multiplication to improve the efficiency of software installation, comprising a first step for calculating H<SUB>0</SUB>=2<SUP>v</SUP>xR (mod n) (where v is an integer, v>=1, and (mxk)/v is an integer), a second step for calculating H<SUB>p</SUB>=2<SUP>vx2<?img id="custom-character-00001" he="3.13mm" wi="2.12mm" file="US20060235921A1-20061019-P00900.TIF" alt="custom character" img-content="character" img-format="tif" ?>p</SUP>xR (mod n) from H<SUB>0</SUB>=2<SUP>v</SUP>xR (mod n) by repeating H<SUB>i</SUB>=REDC(H<SUB>i-1</SUB>, H<SUB>i-1</SUB>)<SUB>n </SUB>with respect to i=1, 2, . . . , p (where p represents an integer satisfying the condition 2<SUP>p</SUP>>=(mxk)/v>2<SUP>p-1</SUP>, REDC represents the Montgomery modular multiplication REDC(a, b)<SUB>n</SUB>=axbxR<SUP>-1 </SUP>(mod n), and xˆi represents exponential computation x<SUP>i</SUP>); and a third step for calculating H<SUB>p</SUB>=R<SUP>2 </SUP>(mod n) by calculating H<SUB>p</SUB>=REDC(H<SUB>p</SUB>, g)<SUB>n </SUB>with respect to H<SUB>p </SUB>obtained in the second step when 2<SUP>p</SUP>>(mxk)/v (where g=2<SUP>kxE(p,m,k)</SUP>, E(p, m, k)=2xm-(vx2<SUP>p</SUP>)/k) and finally outputting H<SUB>p </SUB>as R<SUP>2 </SUP>(mod n).
|
