Computation of a remainder by division using pseudo-remainders

A computer system comprising:

• a computer-readable medium;
• and
• a processor in operable communication with the computer-readable medium, the processor being adapted to:
• determine the second number, wherein the second number (P) is expressed as P =(2k−c), where k is less than a bit processing capability of the processor, and c is less than 2n, where n is given by the formula n=(k−(8b+1)), where b is the number of bytes processed by the processor in each iteration;
• divide the sequence of bytes into a first subsequence of bytes and a second subsequence of bytes;
• calculate a pseudo-remainder by dividing expressing the first subsequence of bytes A*2(k-8b)+B, wherein the pseudo-remainder is a third number calculated as a sum of A*k and B*28b;
• combine the second subsequence of bytes and the pseudo-remainder to create a fourth number;
• and
• divide the fourth number by P to generate the remainder, wherein the first number and the fourth number have the same remainder when divided by P.

A non-transitory computer program product for calculating a remainder by division of a sequence of bytes interpreted as a first number by a second number, the computer program product further including computer-readable program code portions stored thereon, the computer-readable program code portions comprising:

• a first executable portion for determining the second number, wherein the second number (P) is expressed as P=(2k−c), where k is less than a bit processing capability of the processor, and c is less than 2n, where n is given by the formula n=(k−(8b+1)), where b is the number of bytes processed by the processor in each iteration;
• a second executable portion for dividing the sequence of bytes into a first subsequence of bytes and a second subsequence of bytes;
• a third executable portion for calculating a pseudo-remainder by expressing the first subsequence of bytes A*2(k-8b)+B, wherein the pseudo-remainder is a third number calculated as a sum of A*k and B*28b;
• a fourth executable portion for combining the second subsequence of bytes and the pseudo-remainder to create a fourth number;
• and
• a fifth executable portion for dividing the fourth number by P to generate the remainder, wherein the first number and the fourth number have the same remainder by division when divided by the second number.