Abstract:
In an embodiment, multi-precision numbers A and B are accessed from a storage device (e.g., a memory array), where A is a dividend and B is a divisor. A multi-precision division operation is iteratively performed on the numbers A and B including: performing a multi-precision subtraction operation on A and B during a first iteration of the multi-precision division operation; performing a multi-precision addition operation on A and B during a second iteration of the multi-precision division operation as a result of a determination that a final borrow occurred during the subtraction operation; and performing a multi-precision addition operation on A and B after a final iteration of the multi-precision division operation.

Description:
TECHNICAL FIELD 
       [0001]    This disclosure relates generally to techniques for optimizing multi-precision division. 
       BACKGROUND 
       [0002]    In accordance with an example scenario, many cryptosystems are based on algorithms that perform modular reduction operations. Modular reduction operations may be expensive computationally, such as where they involve dividing two multi-precision numbers. Certain implementations of modular reduction operations may involve multi-precision division to be performed by a Central Processing Unit (CPU) or Arithmetic Logic Unit (ALU), which can consume a large number of clock cycles. A large number of clock cycles can result in reduced speed of cryptographic computations and increased power consumption. Since cryptosystems may be installed on devices with limited power (e.g., smart cards), optimizing modular reduction operations used in cryptographic computations may be beneficial. 
       SUMMARY 
       [0003]    In an embodiment, multi-precision numbers A and B are accessed from a storage device (e.g., a memory array), where A is a dividend and B is a divisor. A multi-precision division operation is iteratively performed on the numbers A and B including: performing a multi-precision subtraction operation on A and B during a first iteration of the multi-precision division operation; performing a multi-precision addition operation on A and B during a second iteration of the multi-precision division operation as a result of a determination that a final borrow occurred during the subtraction operation; and performing a multi-precision addition operation on A and B after a final iteration of the multi-precision division operation. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0004]      FIG. 1  is a block diagram of an example system that uses optimized multi-precision division. 
           [0005]      FIG. 2  is a block diagram of an example CPU or co-processor of the system of  FIG. 1  for performing optimized multi-precision division. 
           [0006]      FIG. 3  is a flow diagram of an example process for performing modular reduction using optimized multi-precision division. 
           [0007]      FIG. 4  is a flow diagram of an example process for optimized multi-precision division. 
       
    
    
     DETAILED DESCRIPTION 
       [0008]      FIG. 1  is a block diagram of an example system  100  that uses optimized multi-precision division. In some implementations, system  100  can be a cryptosystem or any other system or apparatus for performing multi-precision division, including but not limited to smart cards or smart card readers, smart phones, e-tablets and computer systems. System  100  shown in  FIG. 1  is a smart card. System  100  can include central processing unit (CPU)  102 , optional co-processor  104 , volatile memory  108  and non-volatile memory  110 ,  112  (e.g., EEPROM, ROM). These components communicate through internal bus  106 . System  100  is an example apparatus. In practice, system  100  can include more or fewer components. For example, system  100  can include specific hardware (e.g., ASIC) for performing all or some of the optimized multi-precision division. 
         [0009]      FIG. 2  is a block diagram of an example processor  200  (e.g., CPU  102  or co-processor  104 ) of system  100  of  FIG. 1 . In some implementations, processor  200  can be a secure processor. Processor  200  can include program counter  202 , decoder  203 , Arithmetic Logic Unit (ALU)  204 , accumulator register  206 , multiplexer (MUX)  208 , memory  210  (e.g., RAM  108 ), data bus  212 , control bus  214  and address bus  216 . In practice, processor  200  can include more or fewer components, such as one or more status registers, a clock source, a power source, etc. 
         [0010]    ALU  204  loads data (e.g., numbers A and B) from input registers (not shown) coupled to ALU  204 . A control unit (e.g., decoder  203 , MUX  208 ) commands/instructs ALU  204  to perform a particular operation on that data (e.g., rotate and shift), and the ALU  204  stores the result of the operation in an output register (e.g., accumulator  206 ). The control unit is responsible for moving the processed data on data bus  212  between the input/output registers, ALU  204  and memory  210 . In this example configuration, decoder  203  decodes an instruction read from instruction register  201  and sends a control signal on control bus  214  to ALU  204 . 
         [0011]    ALU  204  can be configured to perform optimized multi-precision numbers A and B stored in the input registers. In this example, the numbers A and B are shown in memory  210  (e.g., RAM). The numbers A and B can be stored in separate memory arrays in memory  210  that can be indexed. The location of the numbers in memory  210  can be determined by an address on address bus  216 . The numbers A and B can be read from their respective memory arrays in memory  219  and moved into input registers coupled to ALU  204 . Additionally, the final result of an operation and supporting or intermediate calculations performed by ALU  204  can be stored in an output register (e.g., accumulator  206 ) or memory  210 . Accumulator  206  can be divided into High and Low portions. The numbers A and B can be 32-bit or 64-bit words. An instruction can be used to determine the word width. Some operations can use the accumulator  206 . ALU  204  can perform optimized multi-precision division by operating on the numbers in the input and output registers (A, B) in response to a rotate/shift instruction (e.g. barrel shifting) by a specified number of bit positions and checking one or more status registers (e.g., for indicating borrow or carry). 
         [0012]      FIG. 3  is a flow diagram of an example process  300  for performing modular reduction using optimized multi-precision division. In some implementations, optimized multi-precision division can be used with a multi-precision modular reduction operation. Modular reduction operations (commonly written as A mod (B) or A % B in software nomenclature) are commonly used in cryptographic algorithms (e.g., RSA, DSA). In some implementations, process  300  can begin by accessing multi-precision numbers A and B from a storage device, such as registers and/or memory ( 302 ). The accessing can be done by a processor or control unit of a cryptosystem. The numbers can be stored in separate memory arrays that can be indexed using pointers. The numbers can be 32-bit or 62-bit word, where a word size is equal to 8 bits. Each of the numbers can span multiple machine words in a memory array. Process  300  can continue by performing modular reduction operations with optimized multi-precision division ( 304 ). Optimized multi-precision division is described in reference to  FIG. 4 . Process  300  can continue by storing the result of the modular reduction (e.g., the remainder) in memory or hardware register for further processing by a cryptographic application ( 306 ). 
       Optimized Multi-Precision Division 
       [0013]    To reduce the number of clock cycles and thus increase speed and reduce power consumption of a system (e.g., a cryptosystem), an optimized multi-precision division process will now be described. To explain the optimization, it is beneficial to first discuss how a conventional multi-precision division process (shown in pseudo code) works and its deficiencies. 
         [0014]    A conventional multi-precision division process is shown below. 
         [0000]    
       
         
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 //Conventional Multi-Precision Division 
               
               
                   
                 wordSize = 8; // (number of bits in a word) 
               
               
                   
                 Asize = 4; // (number of words in A) 
               
               
                   
                 Bsize = 4; // (number of words in B) 
               
               
                   
                 for (i=Asize*wordSize; i &gt;= 0; i−−) 
               
               
                   
                 { 
               
             
          
           
               
                   
                 if (A&gt;=(B&lt;&lt;i)); 
               
             
          
           
               
                   
                 A=A−(B&lt;&lt;i); 
               
             
          
           
               
                   
                 } 
               
               
                   
                   
               
             
          
         
       
     
         [0015]    Referring to the pseudocode above, the operation B&lt;&lt;i shifts the binary number B stored in an input register by “i” bit positions, “i--” means decrement by one the index “i” and A=A−(B&lt;&lt;i) is a multi-precision subtraction operation on A and B. 
         [0016]    The conventional multi-precision division set forth above does not address the details of A/B word storage, which requires additional words of memory due to the bit shift operation B&lt;&lt;i. To prevent memory overflow for the additional words, the number of bit positions that B can be shifted without overflowing the B memory is determined and the number of bit shifts modified appropriately. This results in a modification to the conventional multi-precision process as shown below: 
         [0000]    
       
         
               
             
               
               
             
               
               
             
               
             
           
               
                   
               
             
             
               
                 //Modified Conventional Multi-Precision Division 
               
               
                 find ‘msWordA’= msWord of A; 
               
               
                 find ‘msBitA’ = msBit of A within A[msWordA]; 
               
               
                 find ‘msWordB’= msWord of B; 
               
               
                 find ‘msBitB’= msBit of B within B[msWordB]; 
               
               
                 set i0 = (msWordA*wordSize + msBitA) − (msWordB*wordSize + 
               
               
                 msBitB); 
               
               
                 for (i=i0; i &gt;= 0; i−−) 
               
               
                 { 
               
             
          
           
               
                   
                 if (A&gt;=(B&lt;&lt;i)) 
               
             
          
           
               
                   
                 A=A−(B&lt;&lt;i); 
               
             
          
           
               
                 } 
               
               
                   
               
             
          
         
       
     
         [0017]    The loop operation shown above requires 2 full walks of the B memory array. The first walk is a compare step to determine if B&lt;&lt;i is “&gt;=” A. The second walk of the B memory array is to do the multi-precision subtraction A=A−(B&lt;&lt;i). The compare operation can be eliminated with the following optimized multi-precision division as shown below. 
         [0000]    
       
         
               
             
               
               
             
               
               
             
               
             
               
               
             
               
               
             
               
             
           
               
                   
               
             
             
               
                 //Optimized Multi-Precision Division 
               
               
                 find ‘msWordA’= msWord of A; 
               
               
                 find ‘msBitA’ = msBit of A within A[msWordA]; 
               
               
                 find ‘msWordB’= msWord of B; 
               
               
                 find ‘msBitB’= msBit of B within B[msWordB]; 
               
               
                 negative=0; 
               
               
                 set i0 = (msWordA*wordSize + msBitA) − (msWordB*wordSize + 
               
               
                 msBitB); 
               
               
                 for (i=i0; i &gt;= 0; i−−) 
               
               
                 { 
               
             
          
           
               
                   
                 if (negative) 
               
             
          
           
               
                   
                 A=A+(B&lt;&lt;i); 
               
             
          
           
               
                 negative = not(final_carry); 
               
             
          
           
               
                   
                 else 
               
             
          
           
               
                   
                 A=A−(B&lt;&lt;i); 
               
             
          
           
               
                 negative = final_borrow; 
               
               
                 } 
               
               
                 if (negative) 
               
               
                 A=A+B; 
               
               
                   
               
             
          
         
       
     
         [0018]    As described above, optimized multi-precision division always performs the subtraction A=A−(B&lt;&lt;i) a word at a time (propagating the borrow word by word), and if the subtraction results in a final “borrow,” then the subtraction operation is “undone” in the next loop cycle (next iteration) by doing an addition A=A+(B&lt;&lt;i) operation a word at a time (propagating the carry word by word). The optimized multi-precision division will also require a final iteration to undo the first (i=0) iteration if needed. Note that the optimized multi-precision division is based on the observation that the difference in two sequential iterations (i=n and i=n−1) is a factor of 2B. The first iteration (i=n) will be 2× the second iteration (i=n−1) or the 2nd bit shift operation (B&lt;&lt;(i=n−1)) is ½ the previous bit shift operation (B&lt;&lt;(i=n)). At iteration i=n, A=A−(B&lt;&lt;n) and at iteration i=n−1, A=A−(B&lt;&lt;(n−1))+(B&lt;&lt;n), assuming borrow occurred. Note that (B&lt;&lt;n)−(B&lt;&lt;(n−1)) can be simplified to +B&lt;&lt;(n−1) and the ½ factor is added rather than subtracted. 
         [0019]      FIG. 4  is a flow diagram of an example process  400  for optimized multi-precision division. In some implementations, process  400  can be performed by processor  200 , as described in reference to  FIG. 2 . 
         [0020]    Process  400  can begin by setting an iterative loop start variable i0 to (msWordA*wordSize+msBitA)−(msWordB*wordSize+msBitB) ( 401 ) and setting a variable “negative” to zero ( 402 ). The variable negative is an integer that can take on the value 0 or 1 to indicate that a negative number resulted from an operation. Next, an iterative loop is entered, where the number of iterations is given by index i=i0, where i is an integer decremented by 1 for each iteration until i is less than zero (i&lt;0). In this example, the integer variables msWordA and msWordB are first non-zero words of A and B, respectively, counted from the left or most significant position, the integer variable msBitA is the most significant bit of A within A[msWordA], msBitB is the most significant bit of B within B[msWordB] and the integer variable wordSize is an arbitrary size of a word (e.g., 4 bytes). 
         [0021]    For each iteration, process  400  checks if ( 406 ) negative is 0 or 1. If negative=0, a binary subtraction operation A−=(B&lt;&lt;i) is performed ( 412 ) and the variable negative is set to the complement of the variable final carry or not (final carry). The variable final carry is an integer that takes on the value 0 or 1 to indicate whether or not a final carry resulted from the binary subtraction operation ( 412 ). If ( 416 ) the number of iterations is exhausted, the loop is exited and the variable negative is checked again. If ( 420 ) negative=1, a binary addition operation A+=B is performed ( 418 ). Otherwise, process  400  stops. 
         [0022]    Returning to step  406 , if negative=1, a binary addition operation A+=(B&lt;&lt;i) is performed ( 408 ) and the variable negative is set to the variable final_borrow. The variable final_borrow is an integer that takes on the value 0 or 1 to indicate whether or not a final borrow resulted from the binary addition operation ( 408 ). If ( 416 ) the number of iterations is exhausted, the loop is exited and the variable negative is checked again. If ( 420 ) negative=1, a binary addition operation A+=B is performed ( 418 ). Otherwise, process  400  stops. 
       Example Calculations 
       [0023]    To further illustrate process  400 , two examples will be discussed where given two multi-precision numbers A, B, the number A is modified to A′ by removing all factors of the number B or A′=A%B, where % is the modulo operator. 
         [0024]    Using a one word example, we assume A=0xF and B=0x7, wordSize=4, msWordB=0 and msBitB=1. We want to compute 15%7, where % is modulo operator. Calculations for this one word example are given below in Table I. 
         [0000]    
       
         
               
             
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
             
           
               
                 TABLE I 
               
             
             
               
                   
               
               
                 One Word Example (15%7) 
               
             
          
           
               
                 Step 
                 Borrow 
                 Carry 
                 A 
                 B 
                 i 
                 Neg. 
                 Comment 
               
               
                   
               
             
          
           
               
                   
                 0 
                 0 
                 F(1111) 
                 7(0111) 
                 — 
                 0 
                   
               
               
                 1 
                 0 
                 0 
                 F(1111) 
                 7(0111) 
                 1 
                 0 
                 for loop starts with i = 0*4 + 1 
               
               
                 2 
                 0 
                 0 
                 F(1111) 
                 7(0111) 
                 1 
                 0 
                 if negative takes else clause 
               
               
                 3 
                 0 
                 0 
                 1(0001) 
                 7(0111) 
                 1 
                 0 
                 A− = (B &lt;&lt; 1) 
               
               
                 4 
                 0 
                 0 
                 1(0001) 
                 7(0111) 
                 1 
                 0 
                 negative = final_borrow 
               
               
                 5 
                 0 
                 0 
                 1(0001) 
                 7(0111) 
                 0 
                 0 
                 for loop decrements i by 1 
               
               
                 6 
                 0 
                 0 
                 1(0001) 
                 7(0111) 
                 0 
                 0 
                 for loop continues with i = 0 
               
               
                 7 
                 0 
                 0 
                 1(0001) 
                 7(0111) 
                 0 
                 0 
                 if negative takes else clause 
               
               
                 8 
                 1 
                 0 
                 A(1010) 
                 7(0111) 
                 0 
                 0 
                 A− = (B &lt;&lt; 0) (Note: 1 − 7 = −6 but in 4-bit 
               
               
                   
                   
                   
                   
                   
                   
                   
                 numbers this is −6 + 16 or 10 because 
               
               
                   
                   
                   
                   
                   
                   
                   
                 these numbers are modulo 16) 
               
               
                 9 
                 1 
                 0 
                 A(1010) 
                 7(0111) 
                 0 
                 1 
                 negative = final_borrow 
               
               
                 10 
                 1 
                 0 
                 A(1010) 
                 7(0111) 
                 −1 
                 1 
                 for loop decrements i by 1 
               
               
                 11 
                 1 
                 0 
                 A(1010) 
                 7(0111) 
                 −1 
                 1 
                 for loop exits with i = −1 
               
               
                 12 
                 1 
                 0 
                 A(1010) 
                 7(0111) 
                 −1 
                 1 
                 final if (negative) gets taken 
               
               
                 13 
                 1 
                 0 
                 A(0001) 
                 7(0111) 
                 −1 
                 1 
                 A+ = B 
               
               
                   
               
             
          
         
       
     
         [0025]    As expected for the operation 15%7, ′A=1. 
         [0026]    Using a two word example, we assume A=(0xF, 0xF) and B=(0x7,0x7) wordSize=4, msWordB=1 and msBitB=1. We want to compute 255%7, where % is the modulo operator. Calculations for this two word example are given below in Table II. 
         [0000]    
       
         
               
             
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE II 
               
             
             
               
                   
               
               
                 Two Word Example (255%7) 
               
             
          
           
               
                 Step 
                 Borrow 
                 Carry 
                 A 
                 B 
                 i 
                 Neg. 
                 Comments 
               
               
                   
               
             
          
           
               
                   
                 0 
                 0 
                 F(1111) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 — 
                 0 
                   
               
               
                 1 
                 0 
                 0 
                 F(1111) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 5 
                 0 
                 for loop starts with 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 i = 1*4 + 1 
               
               
                 2 
                 0 
                 0 
                 F(1111) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 5 
                 0 
                 if negative takes else 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 clause 
               
               
                 3 
                 0 
                 0 
                 F(1111) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 5 
                 0 
                 A− = (B &lt;&lt; 5); 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 A− = (0x1110 0x0000) 
               
               
                   
                   
                   
                   
                 −0000 
               
               
                   
                 0 
                 0 
                 F(1111) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 5 
                 0 
                 A− = (B &lt;&lt; 5); 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 A− = (0x1110 0x0000) 
               
               
                   
                   
                   
                 −1110 
               
               
                   
                 0 
                 0 
                 1(0001) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 5 
                 0 
                 A− = (B &lt;&lt; 5); 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 A− = (0x1110 0x0000) 
               
               
                 4 
                 0 
                 0 
                 1(0001) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 5 
                 0 
                 negative = final_borrow 
               
               
                 5 
                 0 
                 0 
                 1(0001) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 4 
                 0 
                 for loop decrements by i 
               
               
                 6 
                 0 
                 0 
                 1(0001) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 4 
                 0 
                 for loop continues with i = 4 
               
               
                 7 
                 0 
                 0 
                 1(0001) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 4 
                 0 
                 if negative takes else 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 clause 
               
               
                 8 
                 0 
                 0 
                 1(0000) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 4 
                 0 
                 A− = (B &lt;&lt; 4); 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 A− = (0x0111 0x0000) 
               
               
                   
                   
                   
                   
                 −0000 
               
               
                   
                 0 
                 0 
                 1(0001) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 4 
                 0 
                 A− = (B &lt;&lt; 4); 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 A− = (0x0111 0x0000) 
               
               
                   
                   
                   
                 −0111 
                   
                   
                   
                   
                   
                 (Note: 1 − 7 = −6 but in 4-bit 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 numbers this is −6 + 16 or 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 10 because these numbers 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 are modulo 16) 
               
               
                   
                 1 
                 0 
                 A(1010) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 4 
                 0 
                 A− = (B &lt;&lt; 4); 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 A− = (0x0111 0x0000) 
               
               
                 9 
                 1 
                 0 
                 A(1010) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 4 
                 1 
                 negative = final_borrow 
               
               
                 10 
                 1 
                 0 
                 A(1010) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 3 
                 1 
                 for loop decrements i by 1 
               
               
                 11 
                 1 
                 0 
                 A(1010) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 3 
                 1 
                 for loop continues with i = 3 
               
               
                 12 
                 1 
                 0 
                 A(1010) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 3 
                 1 
                 if negative taken 
               
               
                 13 
                 1 
                 0 
                 A(1010) 
                 F(1111) 
                 0(0000) 
                 7(0111) 
                 3 
                 1 
                 A+ = (B &lt;&lt; 3); 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 A+ = (0x0011 0x1000) 
               
               
                   
                   
                   
                   
                 +1000 
               
               
                   
                 1 
                 1 
                 A(1010) 
                 7(0111) 
                 0(0000) 
                 7(0111) 
                 3 
                 1 
               
               
                   
                   
                   
                 +0011 
                   
                   
                   
                   
                   
                 (include the carry in this 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 add) 
               
               
                   
                 1 
                 0 
                 E(1110) 
                 7(0111) 
                 0(0000) 
                 7(0111) 
                 3 
                 1 
               
               
                 14 
                 1 
                 0 
                 E(1110) 
                 7(0111) 
                 0(0000) 
                 7(0111) 
                 3 
                 1 
                 negative = not(final_carry) 
               
               
                 15 
                 1 
                 0 
                 E(1110) 
                 7(0111) 
                 0(0000) 
                 7(0111) 
                 2 
                 1 
                 for loop decrements i by 1 
               
               
                 16 
                 1 
                 0 
                 E(1110) 
                 7(0111) 
                 0(0000) 
                 7(0111) 
                 2 
                 1 
                 for loop continues with i = 2 
               
               
                 17 
                 1 
                 0 
                 E(1110) 
                 7(0111) 
                 0(0000) 
                 7(0111) 
                 2 
                 1 
                 if negative taken 
               
               
                 18 
                 1 
                 0 
                 E(1110) 
                 7(0111) 
                 0(0000) 
                 7(0111) 
                 2 
                   
                 A+ = (B &lt;&lt; 2); 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 A+ = (0x0001 0x1100) 
               
               
                   
                   
                   
                   
                 + 1100 
               
               
                   
                 1 
                 1 
                 E(1110) 
                 3(0011) 
                 0(0000) 
                 7(0111) 
                 2 
                 1 
               
               
                   
                   
                   
                 +0001 
               
               
                   
                 1 
                 1 
                 0(0000) 
                 3(0011) 
                 0(0000) 
                 7(0111) 
                 2 
                 1 
               
               
                 19 
                 1 
                 1 
                 0(0000) 
                 3(0011) 
                 0(0000) 
                 7(0111) 
                 2 
                 0 
                 negative = not(final_carry) 
               
               
                 20 
                 1 
                 1 
                 0(0000) 
                 3(0011) 
                 0(0000) 
                 7(0111) 
                 1 
                 0 
                 for loop decrements i by 1 
               
               
                 21 
                 1 
                 1 
                 0(0000) 
                 3(0011) 
                 0(0000) 
                 7(0111) 
                 1 
                 0 
                 for loop continues with i = 1 
               
               
                 22 
                 1 
                 1 
                 0(0000) 
                 3(0011) 
                 0(0000) 
                 7(0111) 
                 1 
                 0 
                 if negative takes else 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 clause 
               
               
                 23 
                 1 
                 1 
                 0(0000) 
                 3(0011) 
                 0(0000) 
                 7(0111) 
                 1 
                 0 
                 A− = (B &lt;&lt; 1); 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 A− = (0x00000x1110) 
               
               
                   
                   
                   
                   
                 −1110 
               
               
                   
                 1 
                 1 
                 0(0000) 
                 5(0101) 
                 0(0000) 
                 7(0111) 
                 1 
                 0 
               
               
                   
                   
                   
                 −0000 
               
               
                   
                 1 
                 1 
                 F(1111) 
                 5(0101) 
                 0(0000) 
                 7(0111) 
                 1 
                 0 
               
               
                 24 
                 1 
                 1 
                 F(1111) 
                 5(0101) 
                 0(0000) 
                 7(0111) 
                 1 
                 1 
                 negative = final_borrow 
               
               
                 25 
                 1 
                 1 
                 F(1111) 
                 5(0101) 
                 0(0000) 
                 7(0111) 
                 0 
                 1 
                 for loop decrements i by 1 
               
               
                 26 
                 1 
                 1 
                 F(1111) 
                 5(0101) 
                 0(0000) 
                 7(0111) 
                 0 
                 1 
                 for loop continues with i = 0 
               
               
                 27 
                 1 
                 1 
                 F(1111) 
                 5(0101) 
                 0(0000) 
                 7(0111) 
                 0 
                 1 
                 if negative taken 
               
               
                 28 
                 1 
                 1 
                 F(1111) 
                 5(0101) 
                 0(0000) 
                 7(0111) 
                 0 
                 1 
                 A+ = (B &lt;&lt; 0); 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 A+ = (0x0000 0x0111) 
               
               
                   
                   
                   
                   
                 +0111 
               
               
                   
                 1 
                 0 
                 F(1111) 
                 C(1100) 
                 0(0000) 
                 7(0111) 
                 0 
                 1 
               
               
                   
                   
                   
                 +0000 
               
               
                   
                 1 
                 0 
                 (F1111) 
                 C(1100) 
                 0(0000) 
                 7(0111) 
                 0 
                 1 
               
               
                 29 
                 1 
                 0 
                 (F1111) 
                 C(1100) 
                 0(0000) 
                 7(0111) 
                 0 
                 1 
                 negative = not(final_carry) 
               
               
                 30 
                 1 
                 0 
                 (F1111) 
                 C(1100) 
                 0(0000) 
                 7(0111) 
                 −1 
                 1 
                 for loop decrements i by 1 
               
               
                 31 
                 1 
                 0 
                 (F1111) 
                 C(1100) 
                 0(0000) 
                 7(0111) 
                 −1 
                 1 
                 final if(negative) gets taken 
               
               
                 32 
                 1 
                 0 
                 (F1111) 
                 C(1100) 
                 0(0000) 
                 7(0111) 
                 −1 
                 1 
                 A+ = B; 
               
               
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 A+ = (0x0000 0x0111) 
               
               
                   
                   
                   
                   
                 +0111 
               
               
                   
                 1 
                 1 
                 (F1111) 
                 3(0011) 
                 0(0000) 
                 7(0111) 
                 −1 
                 1 
               
               
                   
                   
                   
                 +0000 
                   
                   
                   
                   
                   
                 (carry from previous add) 
               
               
                   
                 1 
                 1 
                 0(0000) 
                 3(0011) 
                 0(0000) 
                 7(0111) 
                 −1 
                 1 
               
               
                   
               
             
          
         
       
     
         [0027]    As expected for the operation 255%7, ′A=3. 
         [0028]    Particular implementations of optimized multi-precision division disclosed herein provide one or more of the following advantages. Systems that perform multi-precision division (e.g., cryptosystems) will use fewer clock cycles to perform the division, thus increasing speed and reducing power consumption. 
         [0029]    While this document contains many specific implementation details, these should not be construed as limitations on the scope what may be claimed, but rather as descriptions of features that may be specific to particular embodiments. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable sub combination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can, in some cases, be excised from the combination, and the claimed combination may be directed to a sub combination or variation of a sub combination.