Pohlig-Hellman Algorithm Performance

In this section, the complexity of the our implementation will be derived. In this derivation, it will be assumed that modular multiplication corresponds to one operation and that modular exponentiation sometimes will correspond to one operation and others to log p depending on the exponent (this was assumed in the original derivation in [4]). Also copy operations and finding elements in the list of factors and exponents of p-1 will not be regarded as operations. The code use for the implementation of the Pohlig-Hellman algorithm follows with the estimate number of operations next to each line of code.

                    LINES OF CODE                                      NUMBER OF OPERATIONS

for (i = 1 , moduli_ptr = moduli_base , x_ptr=x_base ; 
        i < number_of_factors ;
        i++, x_ptr++, moduli_ptr++  )
   {
    copy(pminus1,dummy);                                                           0 
    find_elem_list(i,(number_of_factors-1),&factorization,pi,dummy_exp);           0
    divide(dummy,pi,dummy);                                                        1
    powmod(a,dummy,p,gamma);                                                       1
    copy(y,zj);                                                                    0
    comp = -1;                                                                     0
    for( j=mirvar(1) ; compare(j,dummy_exp) != (1) ; incr(j,1,j) )   This is is a loop so we
      {                                                              multiply the operations 
                                                                     inside by the number of 
                                                                     times the loop runs 
	
       powmod(pi,j,pminus1,temp);                                                 1
       copy(pminus1,dummy);                                                       0
       divide(dummy,temp,dummy);                                                  1
       powmod(zj,dummy,p,delta);                                                log p  
       shanks(gamma,delta,p,pi,bee);                                   pi^(1/2)(1+log pi^(1/2))
       insert(&bees,bee,j);                                                       0
       decr(j,1,temp);                                                            0
       powmod(pi,temp,pminus1,temp);                                              1 
       multiply(bee,temp,temp);                                                   1
       powmod(a,temp,p,temp);                                                   log p
       xgcd(temp,p,temp,temp,temp);                                               0  
       powmod2(temp,uno,zj,uno,p,zj);                                             1
       }                                                                       Ends loop

   powmod(pi,dummy_exp,p,dummy);                                                  1 
   bee=mirvar(0);                                                                 0
   comp=-1;                                                                       0 

   for(ptemp=bees.next, copy(zero,j);compare(j,dummy_exp) == (-1);incr(j,1,j)) Begins other     
       {                                                                         loop
        powmod2(ptemp->value1,uno,pi,j,dummy,temp);                               1
        add(bee,temp,bee);                                                        1
        ptemp = ptemp->next;
       }                                                                       Ends loop
   
   copy(bee,*x_ptr);                                                              0
   copy(dummy,*moduli_ptr);                                                       0
   free(&bees);                                                                   0
   bees.value1=mirvar(0);                                                         0
   bees.value2=mirvar(0);                                                         0
   bees.next=NULL;                                                                0
   }
 
                                                          
 crt_init((number_of_factors-1),moduli_base);                               NOT available
 crt(x_base,result);
 crt_end();

The estimates above can be combined to obtain the overall complexity of the algorinhm as follows. First, we see that the first loop runs number-of-factors times where this variable corresponds to k in our previous notation. Thus we have for this loop:

Notice here that the term corresponds to Shank's Algorithm (1 multiplication and and comparisons times). Now one can combine the operations from the other parts of the subroutine to obtain

Since in Big O notation constant factors are not included then we have that the complexity of the algorithm is

One can see that the complexity of our implementation is very similar to the one described in [3], (neglecting constant factors it only differs in the term which in general will be rather small). Finally Table 3 summarizes the run time of the program for different primes.

Table 3.(Note times include time to enter data)