| 摘要 |
<P>PROBLEM TO BE SOLVED: To shorten the operation time of S*2<SP>-k</SP>mod N for inputs S, N, k. <P>SOLUTION: After finding out n'=-N<SP>-1</SP>mod 2<SP>w</SP>(S3), s=S mod 2<SP>w</SP>(S5), S'=s*n' mod 2<SP>w</SP>(S6) and S=(s+s'N)/2<SP>w</SP>(S7) are operated, a process for updating S to S' is repeated by K=k/w (omit figures after decimal fractions), w'=k mod w (S9) is found out, steps S5 to S7 are executed by substituting the w' for the w, and the execution result S is outputted. Similar technology can be applied also to multiplication based on two's powers. <P>COPYRIGHT: (C)2003,JPO |
