Method and apparatus for multiplication and/or modular reduction processing

A method of modular reduction processing of a number which is represented by a sequence of digits, comprising:

• receiving a number x, wherein number x is provided in radix b form and is represented by sequence of 2k digits such that {xi|i=0, 1, 2, . . . , 2k−1};
• dividing x by bk+1 to produce q1;
• multiplying q1 by μ to produce q2, wherein μ is given in radix b form and is represented by sequence of k+1 digits such that μ=└b2k/m┘, wherein m is modulus given in radix b form and is represented by sequence of k digits such that {mi|i=0,1, 2, . . . , 2k−1} wherein mk−1≠0);
• dividing q2 by bk+1 to produce q3;
• multiplying q3 by m;
• reducing the product of q3 multiplied by m modulo bk+1 to produce r2;
• reducing x modulo bk+1 to produce r1;
• subtracting r2 from r1 to produce r;
• and
• determining which of the following is true:
• r is non-negative and ra1 is negative, wherein ra1 is r−m;
• r is non-negative and ra1 is non-negative and ra2 is negative, wherein ra2 is r−2m;
• r is non-negative and ra2 is non-negative;
• r is negative and rpa1 is negative, wherein rpa1=r+bk+1−m;
• r is negative and rpa1 is non-negative and rpa2 is negative, wherein rpa2=r+bk+1−2m;
• and
• r is negative and rpa2 is non-negative,
• wherein if r is non-negative and ra1 is negative, x mod m=r,
• wherein if r is non-negative and ra1 is non-negative and ra2 is negative, x mod m=r−m,
• wherein if r is non-negative and ra2 is non-negative, x mod m=r−2m,
• wherein if r is negative and rpa1 is negative, x mod m=r+bk+1,
• wherein if r is negative and rpa1 is non-negative and rpa2 is negative, x mod m=r+bk+1−m, and
• wherein if r is negative and rpa2 is non-negative, x mod m=r+bk+1−2m.