\newcommand{\emailaddr}[1]{\mbox{$<${#1}$>$}}
\def\twiddle{\raisebox{0.3ex}{\mbox{\tiny $\sim$}}}
\def\gap{\vspace{0.5ex}}
\makeindex
\begin{document}
\frontmatter
\pagestyle{empty}
\title{LibTomMath User Manual \\ v0.36}
\author{Tom St Denis \\ tomstdenis@iahu.ca}
\maketitle
This text, the library and the accompanying textbook are all hereby placed in the public domain.  This book has been 
formatted for B5 [176x250] paper using the \LaTeX{} {\em book} macro package.

\vspace{10cm}

   }

   /* generic reply for invalid code */
   return "Invalid error code";
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_error.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  c->sign = neg;
  res = MP_OKAY;

LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_fast_mp_invmod.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* if A >= m then A = A - m */
  if (mp_cmp_mag (x, n) != MP_LT) {
    return s_mp_sub (x, n, x);
  }
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_fast_mp_montgomery_reduce.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

         while (tx++ < a->used && ty-- >= 0) { ... }
       */
      iy = MIN(a->used-tx, ty+1);

      /* execute loop */
      for (iz = 0; iz < iy; ++iz) {
         _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);

      }

      /* store term */
      W[ix] = ((mp_digit)_W) & MP_MASK;

      /* make next carry */
      _W = _W >> ((mp_word)DIGIT_BIT);

      *tmpc++ = 0;
    }
  }
  mp_clamp (c);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_fast_s_mp_mul_digs.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

      *tmpc++ = 0;
    }
  }
  mp_clamp (c);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_fast_s_mp_mul_high_digs.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

      *tmpb++ = 0;
    }
  }
  mp_clamp (b);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_fast_s_mp_sqr.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* put the single bit in its place */
  a->dp[b / DIGIT_BIT] = ((mp_digit)1) << (b % DIGIT_BIT);

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_2expt.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* force the sign of b to positive */
  b->sign = MP_ZPOS;

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_abs.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

      res = s_mp_sub (a, b, c);
    }
  }
  return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_add.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  }
  mp_clamp(c);

  return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_add_d.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    return res;
  }
  res = mp_mod (&t, c, d);
  mp_clear (&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_addmod.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  mp_clamp (&t);
  mp_exch (c, &t);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_and.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* reset the sign flag if used == 0 */
  if (a->used == 0) {
    a->sign = MP_ZPOS;
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_clamp.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    /* reset members to make debugging easier */
    a->dp    = NULL;
    a->alloc = a->used = 0;
    a->sign  = MP_ZPOS;
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_clear.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    while (next_mp != NULL) {
        mp_clear(next_mp);
        next_mp = va_arg(args, mp_int*);
    }
    va_end(args);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_clear_multi.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

     /* if negative compare opposite direction */
     return mp_cmp_mag(b, a);
  } else {
     return mp_cmp_mag(a, b);
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_cmp.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  } else if (a->dp[0] < b) {
    return MP_LT;
  } else {
    return MP_EQ;
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_cmp_d.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    if (*tmpa < *tmpb) {
      return MP_LT;
    }
  }
  return MP_EQ;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_cmp_mag.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

         q >>= 4;
      } while (qq == 0);
   }
   return x;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_cnt_lsb.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* copy used count and sign */
  b->used = a->used;
  b->sign = a->sign;
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_copy.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  while (q > ((mp_digit) 0)) {
    ++r;
    q >>= ((mp_digit) 1);
  }
  return r;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_count_bits.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

LBL_Q:mp_clear (&q);
  return res;
}

#endif

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_div.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    }
  }
  b->sign = a->sign;
  mp_clamp (b);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_div_2.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  if (d != NULL) {
    mp_exch (&t, d);
  }
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_div_2d.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  }
  mp_clear(&q);
  
  return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_div_3.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  }
  mp_clear(&q);
  
  return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_div_d.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

          return 0;
       }
   }
   return 1;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_dr_is_modulus.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  if (mp_cmp_mag (x, n) != MP_LT) {
    s_mp_sub(x, n, x);
    goto top;
  }
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_dr_reduce.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    * the number of bits in a mp_digit [e.g. DIGIT_BIT==31]
    */
   *d = (mp_digit)((((mp_word)1) << ((mp_word)DIGIT_BIT)) - 
        ((mp_word)a->dp[0]));
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_dr_setup.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  mp_int  t;

  t  = *a;
  *a = *b;
  *b = t;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_exch.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    b <<= 1;
  }

  mp_clear (&g);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_expt_d.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

#else 
     /* no invmod */
     return MP_VAL;
#endif
  }

/* modified diminished radix reduction */
#if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && defined(BN_S_MP_EXPTMOD_C)
  if (mp_reduce_is_2k_l(P) == MP_YES) {
     return s_mp_exptmod(G, X, P, Y, 1);
  }
#endif

#ifdef BN_MP_DR_IS_MODULUS_C
  /* is it a DR modulus? */

#endif
#ifdef BN_MP_EXPTMOD_FAST_C
  }
#endif
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_exptmod.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
    mp_clear (&M[x]);
  }
  return err;
}
#endif


/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_exptmod_fast.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

   if (U3 != NULL) { mp_exch(U3, &u3); }

   err = MP_OKAY;
_ERR: mp_clear_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL);
   return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_exteuclid.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

      a->sign = neg;
   }
   
   return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_fread.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

   }
   
   XFREE (buf);
   return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_fwrite.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  c->sign = MP_ZPOS;
  res = MP_OKAY;
LBL_V:mp_clear (&u);
LBL_U:mp_clear (&v);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_gcd.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    res = (res << DIGIT_BIT) | DIGIT(a,i);
  }

  /* force result to 32-bits always so it is consistent on non 32-bit platforms */
  return res & 0xFFFFFFFFUL;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_get_int.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    for (; i < a->alloc; i++) {
      a->dp[i] = 0;
    }
  }
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_grow.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  a->used  = 0;
  a->alloc = MP_PREC;
  a->sign  = MP_ZPOS;

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_init.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  if ((res = mp_init (a)) != MP_OKAY) {
    return res;
  }
  return mp_copy (b, a);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_init_copy.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

        cur_arg = va_arg(args, mp_int*);
    }
    va_end(args);
    return res;                /* Assumed ok, if error flagged above. */
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_init_multi.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  if ((err = mp_init(a)) != MP_OKAY) {
     return err;
  }
  mp_set(a, b);
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_init_set.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  int err;
  if ((err = mp_init(a)) != MP_OKAY) {
     return err;
  }
  return mp_set_int(a, b);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_init_set_int.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  for (x = 0; x < size; x++) {
      a->dp[x] = 0;
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_init_size.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

#ifdef BN_MP_INVMOD_SLOW_C
  return mp_invmod_slow(a, b, c);
#endif

  return MP_VAL;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_invmod.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* C is now the inverse */
  mp_exch (&C, c);
  res = MP_OKAY;
LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_invmod_slow.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  }

  *ret = (mp_cmp_mag(&t,arg) == MP_EQ) ? MP_YES : MP_NO;
ERR:mp_clear(&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_is_square.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* done */
  res = MP_OKAY;
LBL_P1:mp_clear (&p1);
LBL_A1:mp_clear (&a1);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_jacobi.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

 * let n represent half of the number of digits in 
 * the min(a,b)
 *
 * a = a1 * B**n + a0
 * b = b1 * B**n + b0
 *
 * Then, a * b => 
   a1b1 * B**2n + ((a1 + a0)(b1 + b0) - (a0b0 + a1b1)) * B + a0b0
 *
 * Note that a1b1 and a0b0 are used twice and only need to be 
 * computed once.  So in total three half size (half # of 
 * digit) multiplications are performed, a0b0, a1b1 and 
 * (a1+b1)(a0+b0)
 *
 * Note that a multiplication of half the digits requires
 * 1/4th the number of single precision multiplications so in 
 * total after one call 25% of the single precision multiplications 
 * are saved.  Note also that the call to mp_mul can end up back 
 * in this function if the a0, a1, b0, or b1 are above the threshold.  
 * This is known as divide-and-conquer and leads to the famous 

  /* now calc the products x0y0 and x1y1 */
  /* after this x0 is no longer required, free temp [x0==t2]! */
  if (mp_mul (&x0, &y0, &x0y0) != MP_OKAY)  
    goto X1Y1;          /* x0y0 = x0*y0 */
  if (mp_mul (&x1, &y1, &x1y1) != MP_OKAY)
    goto X1Y1;          /* x1y1 = x1*y1 */

  /* now calc x1+x0 and y1+y0 */
  if (s_mp_add (&x1, &x0, &t1) != MP_OKAY)
    goto X1Y1;          /* t1 = x1 - x0 */
  if (s_mp_add (&y1, &y0, &x0) != MP_OKAY)
    goto X1Y1;          /* t2 = y1 - y0 */
  if (mp_mul (&t1, &x0, &t1) != MP_OKAY)
    goto X1Y1;          /* t1 = (x1 + x0) * (y1 + y0) */

  /* add x0y0 */
  if (mp_add (&x0y0, &x1y1, &x0) != MP_OKAY)
    goto X1Y1;          /* t2 = x0y0 + x1y1 */
  if (s_mp_sub (&t1, &x0, &t1) != MP_OKAY)
    goto X1Y1;          /* t1 = (x1+x0)*(y1+y0) - (x1y1 + x0y0) */

  /* shift by B */
  if (mp_lshd (&t1, B) != MP_OKAY)
    goto X1Y1;          /* t1 = (x0y0 + x1y1 - (x1-x0)*(y1-y0))<<B */
  if (mp_lshd (&x1y1, B * 2) != MP_OKAY)
    goto X1Y1;          /* x1y1 = x1y1 << 2*B */

Y0:mp_clear (&y0);
X1:mp_clear (&x1);
X0:mp_clear (&x0);
ERR:
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_karatsuba_mul.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* now calc the products x0*x0 and x1*x1 */
  if (mp_sqr (&x0, &x0x0) != MP_OKAY)
    goto X1X1;           /* x0x0 = x0*x0 */
  if (mp_sqr (&x1, &x1x1) != MP_OKAY)
    goto X1X1;           /* x1x1 = x1*x1 */

  /* now calc (x1+x0)**2 */
  if (s_mp_add (&x1, &x0, &t1) != MP_OKAY)
    goto X1X1;           /* t1 = x1 - x0 */
  if (mp_sqr (&t1, &t1) != MP_OKAY)
    goto X1X1;           /* t1 = (x1 - x0) * (x1 - x0) */

  /* add x0y0 */
  if (s_mp_add (&x0x0, &x1x1, &t2) != MP_OKAY)
    goto X1X1;           /* t2 = x0x0 + x1x1 */
  if (s_mp_sub (&t1, &t2, &t1) != MP_OKAY)
    goto X1X1;           /* t1 = (x1+x0)**2 - (x0x0 + x1x1) */

  /* shift by B */
  if (mp_lshd (&t1, B) != MP_OKAY)
    goto X1X1;           /* t1 = (x0x0 + x1x1 - (x1-x0)*(x1-x0))<<B */
  if (mp_lshd (&x1x1, B * 2) != MP_OKAY)
    goto X1X1;           /* x1x1 = x1x1 << 2*B */

T1:mp_clear (&t1);
X1:mp_clear (&x1);
X0:mp_clear (&x0);
ERR:
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_karatsuba_sqr.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  c->sign = MP_ZPOS;

LBL_T:
  mp_clear_multi (&t1, &t2, NULL);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_lcm.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    for (x = 0; x < b; x++) {
      *top++ = 0;
    }
  }
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_lshd.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    mp_exch (&t, c);
  }

  mp_clear (&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_mod.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* clear the digit that is not completely outside/inside the modulus */
  c->dp[b / DIGIT_BIT] &=
    (mp_digit) ((((mp_digit) 1) << (((mp_digit) b) % DIGIT_BIT)) - ((mp_digit) 1));
  mp_clamp (c);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_mod_2d.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

int
mp_mod_d (mp_int * a, mp_digit b, mp_digit * c)
{
  return mp_div_d(a, b, NULL, c);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_mod_d.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

      }
    }
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_montgomery_calc_normalization.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  if (mp_cmp_mag (x, n) != MP_LT) {
    return s_mp_sub (x, n, x);
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_montgomery_reduce.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* rho = -1/m mod b */
  *rho = (((mp_word)1 << ((mp_word) DIGIT_BIT)) - x) & MP_MASK;

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_montgomery_setup.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

#endif

  }
  c->sign = (c->used > 0) ? neg : MP_ZPOS;
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_mul.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

      *tmpb++ = 0;
    }
  }
  b->sign = a->sign;
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_mul_2.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

       c->dp[(c->used)++] = r;
    }
  }
  mp_clamp (c);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_mul_2d.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* set used count */
  c->used = a->used + 1;
  mp_clamp(c);

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_mul_d.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
 */

/* d = a * b (mod c) */

int mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
{
  int     res;
  mp_int  t;

  if ((res = mp_init (&t)) != MP_OKAY) {
    return res;
  }

  if ((res = mp_mul (a, b, &t)) != MP_OKAY) {
    mp_clear (&t);
    return res;
  }
  res = mp_mod (&t, c, d);
  mp_clear (&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_mulmod.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

LBL_T3:mp_clear (&t3);
LBL_T2:mp_clear (&t2);
LBL_T1:mp_clear (&t1);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_n_root.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  } else {
     b->sign = MP_ZPOS;
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_neg.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  }
  mp_clamp (&t);
  mp_exch (c, &t);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_or.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  }

  err = MP_OKAY;
LBL_T:mp_clear (&t);
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_prime_fermat.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

      return MP_OKAY;
    }
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_prime_is_divisible.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  /* passed the test */
  *result = MP_YES;
LBL_B:mp_clear (&b);
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_prime_is_prime.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  *result = MP_YES;
LBL_Y:mp_clear (&y);
LBL_R:mp_clear (&r);
LBL_N1:mp_clear (&n1);
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_prime_miller_rabin.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

   err = MP_OKAY;
LBL_ERR:
   mp_clear(&b);
   return err;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_prime_next_prime.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

       }
   }
   return sizes[x-1].t + 1;
}


#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_prime_rabin_miller_trials.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

   /* calc the maskAND value for the MSbyte*/
   maskAND = ((size&7) == 0) ? 0xFF : (0xFF >> (8 - (size & 7)));

   /* calc the maskOR_msb */
   maskOR_msb        = 0;
   maskOR_msb_offset = ((size & 7) == 1) ? 1 : 0;
   if (flags & LTM_PRIME_2MSB_ON) {
      maskOR_msb       |= 0x80 >> ((9 - size) & 7);


   }  

   /* get the maskOR_lsb */
   maskOR_lsb         = 1;
   if (flags & LTM_PRIME_BBS) {
      maskOR_lsb     |= 3;
   }

error:
   XFREE(tmp);
   return err;
}


#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_prime_random_ex.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

 *
 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
 */

/* chars used in radix conversions */
const char *mp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_radix_smap.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

      return res;
    }
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_rand.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
 */

/* read signed bin, big endian, first byte is 0==positive or 1==negative */

int mp_read_signed_bin (mp_int * a, const unsigned char *b, int c)
{
  int     res;

  /* read magnitude */
  if ((res = mp_read_unsigned_bin (a, b + 1, c - 1)) != MP_OKAY) {
    return res;
  }

  /* first byte is 0 for positive, non-zero for negative */
  if (b[0] == 0) {
     a->sign = MP_ZPOS;
  } else {
     a->sign = MP_NEG;
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_read_signed_bin.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
 */

/* reads a unsigned char array, assumes the msb is stored first [big endian] */

int mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c)
{
  int     res;

  /* make sure there are at least two digits */
  if (a->alloc < 2) {
     if ((res = mp_grow(a, 2)) != MP_OKAY) {
        return res;

      a->used += 2;
#endif
  }
  mp_clamp (a);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_read_unsigned_bin.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  
CLEANUP:
  mp_clear (&q);

  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_reduce.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

   
ERR:
   mp_clear(&q);
   return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_reduce_2k.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

   
ERR:
   mp_clear(&q);
   return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_reduce_2k_l.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

   }
   
   *d = tmp.dp[0];
   mp_clear(&tmp);
   return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_reduce_2k_setup.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

   }
   
ERR:
   mp_clear(&tmp);
   return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_reduce_2k_setup_l.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

          }
      }
   }
   return MP_YES;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_reduce_is_2k.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

      return (iy >= (a->used/2)) ? MP_YES : MP_NO;
      
   }
   return MP_NO;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_reduce_is_2k_l.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  
  if ((res = mp_2expt (a, b->used * 2 * DIGIT_BIT)) != MP_OKAY) {
    return res;
  }
  return mp_div (a, b, a, NULL);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_reduce_setup.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    }
  }
  
  /* remove excess digits */
  a->used -= b;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_rshd.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

void mp_set (mp_int * a, mp_digit b)
{
  mp_zero (a);
  a->dp[0] = b & MP_MASK;
  a->used  = (a->dp[0] != 0) ? 1 : 0;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_set.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    /* ensure that digits are not clamped off */
    a->used += 1;
  }
  mp_clamp (a);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_set_int.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    }
    a->dp    = tmp;
    a->alloc = a->used;
  }
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_shrink.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

/* get the size for an signed equivalent */
int mp_signed_bin_size (mp_int * a)
{
  return 1 + mp_unsigned_bin_size (a);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_signed_bin_size.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

      res = MP_VAL;
#endif
  }
  b->sign = MP_ZPOS;
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_sqr.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    return res;
  }
  res = mp_mod (&t, b, c);
  mp_clear (&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_sqrmod.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

E1: mp_clear(&t2);
E2: mp_clear(&t1);
  return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_sqrt.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

      res = s_mp_sub (b, a, c);
    }
  }
  return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_sub.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

     *tmpc++ = 0;
  }
  mp_clamp(c);
  return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_sub_d.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    return res;
  }
  res = mp_mod (&t, c, d);
  mp_clear (&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_submod.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  if ((res = mp_to_unsigned_bin (a, b + 1)) != MP_OKAY) {
    return res;
  }
  b[0] = (unsigned char) ((a->sign == MP_ZPOS) ? 0 : 1);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_to_signed_bin.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

   if (*outlen < (unsigned long)mp_signed_bin_size(a)) {
      return MP_VAL;
   }
   *outlen = mp_signed_bin_size(a);
   return mp_to_signed_bin(a, b);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_to_signed_bin_n.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    }
  }
  bn_reverse (b, x);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_to_unsigned_bin.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

   if (*outlen < (unsigned long)mp_unsigned_bin_size(a)) {
      return MP_VAL;
   }
   *outlen = mp_unsigned_bin_size(a);
   return mp_to_unsigned_bin(a, b);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_to_unsigned_bin_n.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

     mp_clear_multi(&w0, &w1, &w2, &w3, &w4, 
                    &a0, &a1, &a2, &b0, &b1, 
                    &b2, &tmp1, &tmp2, NULL);
     return res;
}     
     
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_toom_mul.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

ERR:
     mp_clear_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL);
     return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_toom_sqr.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  *str = '\0';

  mp_clear (&t);
  return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_toradix.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  *str = '\0';

  mp_clear (&t);
  return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_toradix_n.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

/* get the size for an unsigned equivalent */
int mp_unsigned_bin_size (mp_int * a)
{
  int     size = mp_count_bits (a);
  return (size / 8 + ((size & 7) != 0 ? 1 : 0));
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_unsigned_bin_size.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  }
  mp_clamp (&t);
  mp_exch (c, &t);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_xor.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  tmp = a->dp;
  for (n = 0; n < a->alloc; n++) {
     *tmp++ = 0;
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_mp_zero.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  0x0593, 0x0595, 0x0599, 0x059F, 0x05A7, 0x05AB, 0x05AD, 0x05B3,
  0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
  0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
  0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
#endif
};
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_prime_tab.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    s[ix] = s[iy];
    s[iy] = t;
    ++ix;
    --iy;
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_reverse.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

    }
  }

  mp_clamp (c);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_s_mp_add.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

 * additional optimizations in place.
 *
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
 */

#ifdef MP_LOW_MEM
   #define TAB_SIZE 32
#else
   #define TAB_SIZE 256
#endif

int s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode)

  mp_clear(&M[1]);
  for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
    mp_clear (&M[x]);
  }
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_s_mp_exptmod.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  mp_clamp (&t);
  mp_exch (&t, c);

  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_s_mp_mul_digs.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  }
  mp_clamp (&t);
  mp_exch (&t, c);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_s_mp_mul_high_digs.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  mp_clamp (&t);
  mp_exch (&t, b);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_s_mp_sqr.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

  }

  mp_clamp (c);
  return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bn_s_mp_sub.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:31:56 $ */

 */

/* Known optimal configurations

 CPU                    /Compiler     /MUL CUTOFF/SQR CUTOFF
-------------------------------------------------------------
 Intel P4 Northwood     /GCC v3.4.1   /        88/       128/LTM 0.32 ;-)
 AMD Athlon64           /GCC v3.4.4   /        80/       120/LTM 0.35
 
*/

int     KARATSUBA_MUL_CUTOFF = 80,      /* Min. number of digits before Karatsuba multiplication is used. */
        KARATSUBA_SQR_CUTOFF = 120,     /* Min. number of digits before Karatsuba squaring is used. */
        
        TOOM_MUL_CUTOFF      = 350,      /* no optimal values of these are known yet so set em high */
        TOOM_SQR_CUTOFF      = 400; 
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/bncore.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:56 $ */

            last if ($_ =~ /math\.libtomcrypt\.org/);
         }
         <SRC>;   
      }
      
      $inline = 0;
      while (<SRC>) {
      next if ($_ =~ /\$Source/);
      next if ($_ =~ /\$Revision/);
      next if ($_ =~ /\$Date/);
         $text[$line++] = $_;
         ++$inline;
         chomp($_);
         $_ =~ s/\t/"    "/ge;
         $_ =~ s/{/"^{"/ge;
         $_ =~ s/}/"^}"/ge;
         $_ =~ s/\\/'\symbol{92}'/ge;

August 1st, 2005
v0.36  -- LTM_PRIME_2MSB_ON was fixed and the "OFF" flag was removed.
       -- [Peter LaDow] found a typo in the XREALLOC macro
       -- [Peter LaDow] pointed out that mp_read_(un)signed_bin should have "const" on the input
       -- Ported LTC patch to fix the prime_random_ex() function to get the bitsize correct [and the maskOR flags]
       -- Kevin Kenny pointed out a stray //
       -- David Hulton pointed out a typo in the textbook [mp_montgomery_setup() pseudo-code]
       -- Neal Hamilton (Elliptic Semiconductor) pointed out that my Karatsuba notation was backwards and that I could use 
          unsigned operations in the routine.  
       -- Paul Schmidt pointed out a linking error in mp_exptmod() when BN_S_MP_EXPTMOD_C is undefined (and another for read_radix)
       -- Updated makefiles to be way more flexible

March 12th, 2005
v0.35  -- Stupid XOR function missing line again... oops.
       -- Fixed bug in invmod not handling negative inputs correctly [Wolfgang Ehrhardt]
       -- Made exteuclid always give positive u3 output...[ Wolfgang Ehrhardt ]
       -- [Wolfgang Ehrhardt] Suggested a fix for mp_reduce() which avoided underruns.  ;-)
       -- mp_rand() would emit one too many digits and it was possible to get a 0 out of it ... oops
       -- Added montgomery to the testing to make sure it handles 1..10 digit moduli correctly

#endif

   div2_n = mul2_n = inv_n = expt_n = lcm_n = gcd_n = add_n =
      sub_n = mul_n = div_n = sqr_n = mul2d_n = div2d_n = cnt = add_d_n =
      sub_d_n = 0;

   /* force KARA and TOOM to enable despite cutoffs */
   KARATSUBA_SQR_CUTOFF = KARATSUBA_MUL_CUTOFF = 8;
   TOOM_SQR_CUTOFF = TOOM_MUL_CUTOFF = 16;

   for (;;) {
      /* randomly clear and re-init one variable, this has the affect of triming the alloc space */
      switch (abs(rand()) % 7) {
      case 0:
	 mp_clear(&a);
	 mp_init(&a);

	    printf("d == %d\n", ix);
	    return 0;
	 }
      }
   }
   return 0;
}

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/demo/demo.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:16 $ */

	     mp_count_bits(&a), CLK_PER_SEC / tt, tt);
      fprintf(log, "%d %9llu\n", cnt * DIGIT_BIT, tt);
   }
   fclose(log);

   return 0;
}

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/demo/timing.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:16 $ */

   return 0;
}   
       
         
            
            
          

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/etc/2kprime.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:16 $ */

   
   mp_clear(&a);
   mp_clear(&b);
   
   return 0;
}


/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/etc/drprime.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:16 $ */

#   K - PIII
#   W - first P4 [Williamette]
#   N - P4 Northwood
#   P - P4 Prescott
#   B - Blend of P4 and PM [mobile]
#
# Default to just generic max opts
CFLAGS += -O3 -xP -ip

# default lib name (requires install with root)
# LIBNAME=-ltommath

# libname when you can't install the lib with install
LIBNAME=../libtommath.a

    /* but make sure its prime */
    while (isprime (k) == 0) {
      k += 2;
    }
  }
  return 0;
}

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/etc/mersenne.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:16 $ */

    return 0;
}






/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/etc/mont.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:16 $ */

  mp_toradix (&p, buf, 10);
  printf ("P == %s\n", buf);
  mp_toradix (&q, buf, 10);
  printf ("Q == %s\n", buf);

  return 0;
}

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/etc/pprime.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:16 $ */

     if (t2 < t1) break;
  }
  printf("KARATSUBA_MUL_CUTOFF = %d\n", y);
  printf("KARATSUBA_SQR_CUTOFF = %d\n", x);

  return 0;
}

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/etc/tune.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:16 $ */

513   1435869
769   3544970
1025   7791638
2049  46902238
2561  85334899
3073 141451412
4097 308770310

607   2109225
1279  10148314
2203  34126877
3217  82716424
4253 161569606

1024   7705271
2048  34286851
4096 165207491
521   1618631

532   1928550
784   3763908
1036   7564221
1540  16566059
2072  32283784
3080  79851565
4116 157843530

<h1>Modular Inverse</h1>
<center><img src=invmod.png></center>
<hr>

</body>
</html>
/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/logs/index.html,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:16 $ */

#Makefile for GCC
#
#Tom St Denis

#version of library 
VERSION=0.36

CFLAGS  +=  -I./ -Wall -W -Wshadow -Wsign-compare

ifndef IGNORE_SPEED

#for speed 
CFLAGS += -O3 -funroll-loops

#for size 
#CFLAGS += -Os

#x86 optimizations [should be valid for any GCC install though]
CFLAGS  += -fomit-frame-pointer

#debug
#CFLAGS += -g3

endif

#install as this user
ifndef INSTALL_GROUP
   GROUP=wheel
else
   GROUP=$(INSTALL_GROUP)
endif

ifndef INSTALL_USER
   USER=root

else
   USER=$(INSTALL_USER)
endif

default: libtommath.a

#default files to install
ifndef LIBNAME
   LIBNAME=libtommath.a
endif
HEADERS=tommath.h tommath_class.h tommath_superclass.h

#LIBPATH-The directory for libtommath to be installed to.
#INCPATH-The directory to install the header files for libtommath.
#DATAPATH-The directory to install the pdf docs.
DESTDIR=
LIBPATH=/usr/lib

bn_mp_radix_smap.o bn_mp_read_radix.o bn_mp_toradix.o bn_mp_radix_size.o \
bn_mp_fread.o bn_mp_fwrite.o bn_mp_cnt_lsb.o bn_error.o \
bn_mp_init_multi.o bn_mp_clear_multi.o bn_mp_exteuclid.o bn_mp_toradix_n.o \
bn_mp_prime_random_ex.o bn_mp_get_int.o bn_mp_sqrt.o bn_mp_is_square.o bn_mp_init_set.o \
bn_mp_init_set_int.o bn_mp_invmod_slow.o bn_mp_prime_rabin_miller_trials.o \
bn_mp_to_signed_bin_n.o bn_mp_to_unsigned_bin_n.o

$(LIBNAME):  $(OBJECTS)
	$(AR) $(ARFLAGS) $@ $(OBJECTS)
	ranlib $@

#make a profiled library (takes a while!!!)
#
# This will build the library with profile generation
# then run the test demo and rebuild the library.
# 
# So far I've seen improvements in the MP math

profiled_single:
	perl gen.pl
	$(CC) $(CFLAGS) -fprofile-arcs -DTESTING -c mpi.c -o mpi.o
	$(CC) $(CFLAGS) -DTESTING -DTIMER demo/timing.c mpi.o -o ltmtest
	./ltmtest
	rm -f *.o ltmtest
	$(CC) $(CFLAGS) -fbranch-probabilities -DTESTING -c mpi.c -o mpi.o
	$(AR) $(ARFLAGS) $(LIBNAME) mpi.o
	ranlib $(LIBNAME)	

install: $(LIBNAME)
	install -d -g $(GROUP) -o $(USER) $(DESTDIR)$(LIBPATH)
	install -d -g $(GROUP) -o $(USER) $(DESTDIR)$(INCPATH)
	install -g $(GROUP) -o $(USER) $(LIBNAME) $(DESTDIR)$(LIBPATH)
	install -g $(GROUP) -o $(USER) $(HEADERS) $(DESTDIR)$(INCPATH)

test: $(LIBNAME) demo/demo.o
	$(CC) $(CFLAGS) demo/demo.o $(LIBNAME) -o test
	
mtest: test	
	cd mtest ; $(CC) $(CFLAGS) mtest.c -o mtest
        
timing: $(LIBNAME)
	$(CC) $(CFLAGS) -DTIMER demo/timing.c $(LIBNAME) -o ltmtest

# makes the LTM book DVI file, requires tetex, perl and makeindex [part of tetex I think]
docdvi: tommath.src
	cd pics ; make 
	echo "hello" > tommath.ind
	perl booker.pl
	latex tommath > /dev/null

clean:
	rm -f *.bat *.pdf *.o *.a *.obj *.lib *.exe *.dll etclib/*.o demo/demo.o test ltmtest mpitest mtest/mtest mtest/mtest.exe \
        *.idx *.toc *.log *.aux *.dvi *.lof *.ind *.ilg *.ps *.log *.s mpi.c *.da *.dyn *.dpi tommath.tex `find -type f | grep [~] | xargs` *.lo *.la
	rm -rf .libs
	cd etc ; make clean
	cd pics ; make clean

#zipup the project (take that!)
no_oops: clean
	cd .. ; cvs commit 
	echo Scanning for scratch/dirty files
	find . -type f | grep -v CVS | xargs -n 1 bash mess.sh

zipup: clean manual poster docs
	perl gen.pl ; mv mpi.c pre_gen/ ; \
	cd .. ; rm -rf ltm* libtommath-$(VERSION) ; mkdir libtommath-$(VERSION) ; \
	cp -R ./libtommath/* ./libtommath-$(VERSION)/ ; \
	tar -c libtommath-$(VERSION)/* | bzip2 -9vvc > ltm-$(VERSION).tar.bz2 ; \
	zip -9 -r ltm-$(VERSION).zip libtommath-$(VERSION)/*

	gcc -mno-cygwin -mdll -o libtommath.dll -Wl,--out-implib=libtommath.dll.a -Wl,--export-all-symbols *.o
	ranlib libtommath.dll.a

# build the test program using the windows DLL
test: $(OBJECTS) windll
	gcc $(CFLAGS) demo/demo.c libtommath.dll.a -Wl,--enable-auto-import -o test -s
	cd mtest ; $(CC) -O3 -fomit-frame-pointer -funroll-loops mtest.c -o mtest -s

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/makefile.cygwin_dll,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:31:57 $ */

#   K - PIII
#   W - first P4 [Williamette]
#   N - P4 Northwood
#   P - P4 Prescott
#   B - Blend of P4 and PM [mobile]
#
# Default to just generic max opts
CFLAGS += -O3 -xP -ip

#install as this user
USER=root
GROUP=root

default: libtommath.a

#MSVC Makefile
#
#Tom St Denis

CFLAGS = /I. /Ox /DWIN32 /W3 /Fo$@

default: library

OBJECTS=bncore.obj bn_mp_init.obj bn_mp_clear.obj bn_mp_exch.obj bn_mp_grow.obj bn_mp_shrink.obj \
bn_mp_clamp.obj bn_mp_zero.obj  bn_mp_set.obj bn_mp_set_int.obj bn_mp_init_size.obj bn_mp_copy.obj \
bn_mp_init_copy.obj bn_mp_abs.obj bn_mp_neg.obj bn_mp_cmp_mag.obj bn_mp_cmp.obj bn_mp_cmp_d.obj \
bn_mp_rshd.obj bn_mp_lshd.obj bn_mp_mod_2d.obj bn_mp_div_2d.obj bn_mp_mul_2d.obj bn_mp_div_2.obj \

bn_mp_reduce_2k_l.obj bn_mp_reduce_is_2k_l.obj bn_mp_reduce_2k_setup_l.obj \
bn_mp_radix_smap.obj bn_mp_read_radix.obj bn_mp_toradix.obj bn_mp_radix_size.obj \
bn_mp_fread.obj bn_mp_fwrite.obj bn_mp_cnt_lsb.obj bn_error.obj \
bn_mp_init_multi.obj bn_mp_clear_multi.obj bn_mp_exteuclid.obj bn_mp_toradix_n.obj \
bn_mp_prime_random_ex.obj bn_mp_get_int.obj bn_mp_sqrt.obj bn_mp_is_square.obj \
bn_mp_init_set.obj bn_mp_init_set_int.obj bn_mp_invmod_slow.obj bn_mp_prime_rabin_miller_trials.obj \
bn_mp_to_signed_bin_n.obj bn_mp_to_unsigned_bin_n.obj

HEADERS=tommath.h tommath_class.h tommath_superclass.h

library: $(OBJECTS)
	lib /out:tommath.lib $(OBJECTS)

#Makefile for GCC
#
#Tom St Denis
VERSION=0:36

CC = libtool --mode=compile gcc

CFLAGS  +=  -I./ -Wall -W -Wshadow -Wsign-compare

ifndef IGNORE_SPEED

#for speed 
CFLAGS += -O3 -funroll-loops

#for size 
#CFLAGS += -Os

#x86 optimizations [should be valid for any GCC install though]
CFLAGS  += -fomit-frame-pointer

endif

#install as this user
ifndef INSTALL_GROUP
   GROUP=wheel
else
   GROUP=$(INSTALL_GROUP)
endif

ifndef INSTALL_USER
   USER=root

else
   USER=$(INSTALL_USER)
endif

default: libtommath.la

#default files to install
ifndef LIBNAME
   LIBNAME=libtommath.la
endif
ifndef LIBNAME_S
   LIBNAME_S=libtommath.a
endif
HEADERS=tommath.h tommath_class.h tommath_superclass.h

#LIBPATH-The directory for libtommath to be installed to.
#INCPATH-The directory to install the header files for libtommath.
#DATAPATH-The directory to install the pdf docs.
DESTDIR=
LIBPATH=/usr/lib

bn_mp_radix_smap.o bn_mp_read_radix.o bn_mp_toradix.o bn_mp_radix_size.o \
bn_mp_fread.o bn_mp_fwrite.o bn_mp_cnt_lsb.o bn_error.o \
bn_mp_init_multi.o bn_mp_clear_multi.o bn_mp_exteuclid.o bn_mp_toradix_n.o \
bn_mp_prime_random_ex.o bn_mp_get_int.o bn_mp_sqrt.o bn_mp_is_square.o bn_mp_init_set.o \
bn_mp_init_set_int.o bn_mp_invmod_slow.o bn_mp_prime_rabin_miller_trials.o \
bn_mp_to_signed_bin_n.o bn_mp_to_unsigned_bin_n.o


$(LIBNAME):  $(OBJECTS)
	libtool --mode=link gcc *.lo -o $(LIBNAME) -rpath $(LIBPATH) -version-info $(VERSION)
	libtool --mode=link gcc *.o -o $(LIBNAME_S)
	ranlib $(LIBNAME_S)
	libtool --mode=install install -c $(LIBNAME) $(LIBPATH)/$@
	install -d -g $(GROUP) -o $(USER) $(DESTDIR)$(INCPATH)
	install -g $(GROUP) -o $(USER) $(HEADERS) $(DESTDIR)$(INCPATH)

test: $(LIBNAME) demo/demo.o
	gcc $(CFLAGS) -c demo/demo.c -o demo/demo.o
	libtool --mode=link gcc -o test demo/demo.o $(LIBNAME_S)
	
mtest: test	
	cd mtest ; gcc $(CFLAGS) mtest.c -o mtest
        
timing: $(LIBNAME)
	gcc $(CFLAGS) -DTIMER demo/timing.c $(LIBNAME_S) -o ltmtest

#!/bin/bash
if cvs log $1 >/dev/null 2>/dev/null; then exit 0; else echo "$1 shouldn't be here" ; exit 1; fi

   0.179052232, 0.178103594, 0.177183820, 0.176291434, 	/* 48 49 50 51 */
   0.175425064, 0.174583430, 0.173765343, 0.172969690, 	/* 52 53 54 55 */
   0.172195434, 0.171441601, 0.170707280, 0.169991616, 	/* 56 57 58 59 */
   0.169293808, 0.168613099, 0.167948779, 0.167300179, 	/* 60 61 62 63 */
   0.166666667
};


/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/mtest/logtab.h,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:17 $ */

/* Default configuration for MPI library */
/* $Id: mpi-config.h,v 1.1.1.2 2005/09/26 16:32:17 kennykb Exp $ */

#ifndef MPI_CONFIG_H_
#define MPI_CONFIG_H_

/*
  For boolean options, 
  0 = no

#define MP_COMPAT_MACROS 1   /* define compatibility macros?    */
#endif

#endif /* ifndef MPI_CONFIG_H_ */


/* crc==3287762869, version==2, Sat Feb 02 06:43:53 2002 */

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/mtest/mpi-config.h,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:17 $ */

#define MP_WORD_BIT        (CHAR_BIT*sizeof(mp_word))
#define MP_WORD_MAX        UINT_MAX

#define MP_DIGIT_SIZE      2
#define DIGIT_FMT          "%04X"
#define RADIX              (MP_DIGIT_MAX+1)


/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/mtest/mpi-types.h,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:17 $ */

/*
    mpi.c

    by Michael J. Fromberger <sting@linguist.dartmouth.edu>
    Copyright (C) 1998 Michael J. Fromberger, All Rights Reserved

    Arbitrary precision integer arithmetic library

    $Id: mpi.c,v 1.1.1.2 2005/09/26 16:32:17 kennykb Exp $
 */

#include "mpi.h"
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/* }}} */

/* }}} */

/*------------------------------------------------------------------------*/
/* HERE THERE BE DRAGONS                                                  */
/* crc==4242132123, version==2, Sat Feb 02 06:43:52 2002 */

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/mtest/mpi.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:17 $ */

/*
    mpi.h

    by Michael J. Fromberger <sting@linguist.dartmouth.edu>
    Copyright (C) 1998 Michael J. Fromberger, All Rights Reserved

    Arbitrary precision integer arithmetic library

    $Id: mpi.h,v 1.1.1.2 2005/09/26 16:32:17 kennykb Exp $
 */

#ifndef _H_MPI_
#define _H_MPI_

#include "mpi-config.h"

/*------------------------------------------------------------------------*/
/* Error strings                                                          */

const  char  *mp_strerror(mp_err ec);

#endif /* end _H_MPI_ */

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/mtest/mpi.h,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:17 $ */

      mp_to64(&b, buf);
      printf("%s\n", buf);
   }
   }
   fclose(rng);
   return 0;
}

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/mtest/mtest.c,v $ */
/* $Revision: 1.1.1.2 $ */
/* $Date: 2005/09/26 16:32:17 $ */

   /* generic reply for invalid code */
   return "Invalid error code";
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_error.c */

/* Start: bn_fast_mp_invmod.c */
#include <tommath.h>
#ifdef BN_FAST_MP_INVMOD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  c->sign = neg;
  res = MP_OKAY;

LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_fast_mp_invmod.c */

/* Start: bn_fast_mp_montgomery_reduce.c */
#include <tommath.h>
#ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  /* if A >= m then A = A - m */
  if (mp_cmp_mag (x, n) != MP_LT) {
    return s_mp_sub (x, n, x);
  }
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_fast_mp_montgomery_reduce.c */

/* Start: bn_fast_s_mp_mul_digs.c */
#include <tommath.h>
#ifdef BN_FAST_S_MP_MUL_DIGS_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

         while (tx++ < a->used && ty-- >= 0) { ... }
       */
      iy = MIN(a->used-tx, ty+1);

      /* execute loop */
      for (iz = 0; iz < iy; ++iz) {
         _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);

      }

      /* store term */
      W[ix] = ((mp_digit)_W) & MP_MASK;

      /* make next carry */
      _W = _W >> ((mp_word)DIGIT_BIT);

      *tmpc++ = 0;
    }
  }
  mp_clamp (c);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_fast_s_mp_mul_digs.c */

/* Start: bn_fast_s_mp_mul_high_digs.c */
#include <tommath.h>
#ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

      *tmpc++ = 0;
    }
  }
  mp_clamp (c);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_fast_s_mp_mul_high_digs.c */

/* Start: bn_fast_s_mp_sqr.c */
#include <tommath.h>
#ifdef BN_FAST_S_MP_SQR_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

    }
  }
  mp_clamp (b);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_fast_s_mp_sqr.c */

/* Start: bn_mp_2expt.c */
#include <tommath.h>
#ifdef BN_MP_2EXPT_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  /* put the single bit in its place */
  a->dp[b / DIGIT_BIT] = ((mp_digit)1) << (b % DIGIT_BIT);

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_2expt.c */

/* Start: bn_mp_abs.c */
#include <tommath.h>
#ifdef BN_MP_ABS_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  /* force the sign of b to positive */
  b->sign = MP_ZPOS;

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_abs.c */

/* Start: bn_mp_add.c */
#include <tommath.h>
#ifdef BN_MP_ADD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

      res = s_mp_sub (a, b, c);
    }
  }
  return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_add.c */

/* Start: bn_mp_add_d.c */
#include <tommath.h>
#ifdef BN_MP_ADD_D_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  mp_clamp(c);

  return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_add_d.c */

/* Start: bn_mp_addmod.c */
#include <tommath.h>
#ifdef BN_MP_ADDMOD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

    return res;
  }
  res = mp_mod (&t, c, d);
  mp_clear (&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_addmod.c */

/* Start: bn_mp_and.c */
#include <tommath.h>
#ifdef BN_MP_AND_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  mp_clamp (&t);
  mp_exch (c, &t);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_and.c */

/* Start: bn_mp_clamp.c */
#include <tommath.h>
#ifdef BN_MP_CLAMP_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  /* reset the sign flag if used == 0 */
  if (a->used == 0) {
    a->sign = MP_ZPOS;
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_clamp.c */

/* Start: bn_mp_clear.c */
#include <tommath.h>
#ifdef BN_MP_CLEAR_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

    a->dp    = NULL;
    a->alloc = a->used = 0;
    a->sign  = MP_ZPOS;
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_clear.c */

/* Start: bn_mp_clear_multi.c */
#include <tommath.h>
#ifdef BN_MP_CLEAR_MULTI_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

    while (next_mp != NULL) {
        mp_clear(next_mp);
        next_mp = va_arg(args, mp_int*);
    }
    va_end(args);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_clear_multi.c */

/* Start: bn_mp_cmp.c */
#include <tommath.h>
#ifdef BN_MP_CMP_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

     return mp_cmp_mag(b, a);
  } else {
     return mp_cmp_mag(a, b);
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_cmp.c */

/* Start: bn_mp_cmp_d.c */
#include <tommath.h>
#ifdef BN_MP_CMP_D_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  } else if (a->dp[0] < b) {
    return MP_LT;
  } else {
    return MP_EQ;
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_cmp_d.c */

/* Start: bn_mp_cmp_mag.c */
#include <tommath.h>
#ifdef BN_MP_CMP_MAG_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

      return MP_LT;
    }
  }
  return MP_EQ;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_cmp_mag.c */

/* Start: bn_mp_cnt_lsb.c */
#include <tommath.h>
#ifdef BN_MP_CNT_LSB_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

         q >>= 4;
      } while (qq == 0);
   }
   return x;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_cnt_lsb.c */

/* Start: bn_mp_copy.c */
#include <tommath.h>
#ifdef BN_MP_COPY_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  /* copy used count and sign */
  b->used = a->used;
  b->sign = a->sign;
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_copy.c */

/* Start: bn_mp_count_bits.c */
#include <tommath.h>
#ifdef BN_MP_COUNT_BITS_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  while (q > ((mp_digit) 0)) {
    ++r;
    q >>= ((mp_digit) 1);
  }
  return r;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_count_bits.c */

/* Start: bn_mp_div.c */
#include <tommath.h>
#ifdef BN_MP_DIV_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  return res;
}

#endif

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_div.c */

/* Start: bn_mp_div_2.c */
#include <tommath.h>
#ifdef BN_MP_DIV_2_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

    }
  }
  b->sign = a->sign;
  mp_clamp (b);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_div_2.c */

/* Start: bn_mp_div_2d.c */
#include <tommath.h>
#ifdef BN_MP_DIV_2D_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

    mp_exch (&t, d);
  }
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_div_2d.c */

/* Start: bn_mp_div_3.c */
#include <tommath.h>
#ifdef BN_MP_DIV_3_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  }
  mp_clear(&q);
  
  return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_div_3.c */

/* Start: bn_mp_div_d.c */
#include <tommath.h>
#ifdef BN_MP_DIV_D_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  mp_clear(&q);
  
  return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_div_d.c */

/* Start: bn_mp_dr_is_modulus.c */
#include <tommath.h>
#ifdef BN_MP_DR_IS_MODULUS_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

          return 0;
       }
   }
   return 1;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_dr_is_modulus.c */

/* Start: bn_mp_dr_reduce.c */
#include <tommath.h>
#ifdef BN_MP_DR_REDUCE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

    s_mp_sub(x, n, x);
    goto top;
  }
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_dr_reduce.c */

/* Start: bn_mp_dr_setup.c */
#include <tommath.h>
#ifdef BN_MP_DR_SETUP_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

    * the number of bits in a mp_digit [e.g. DIGIT_BIT==31]
    */
   *d = (mp_digit)((((mp_word)1) << ((mp_word)DIGIT_BIT)) - 
        ((mp_word)a->dp[0]));
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_dr_setup.c */

/* Start: bn_mp_exch.c */
#include <tommath.h>
#ifdef BN_MP_EXCH_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  mp_int  t;

  t  = *a;
  *a = *b;
  *b = t;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_exch.c */

/* Start: bn_mp_expt_d.c */
#include <tommath.h>
#ifdef BN_MP_EXPT_D_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

    b <<= 1;
  }

  mp_clear (&g);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_expt_d.c */

/* Start: bn_mp_exptmod.c */
#include <tommath.h>
#ifdef BN_MP_EXPTMOD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

#else 
     /* no invmod */
     return MP_VAL;
#endif
  }

/* modified diminished radix reduction */
#if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && defined(BN_S_MP_EXPTMOD_C)
  if (mp_reduce_is_2k_l(P) == MP_YES) {
     return s_mp_exptmod(G, X, P, Y, 1);
  }
#endif

#ifdef BN_MP_DR_IS_MODULUS_C
  /* is it a DR modulus? */

#endif
#ifdef BN_MP_EXPTMOD_FAST_C
  }
#endif
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_exptmod.c */

/* Start: bn_mp_exptmod_fast.c */
#include <tommath.h>
#ifdef BN_MP_EXPTMOD_FAST_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

    mp_clear (&M[x]);
  }
  return err;
}
#endif


/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_exptmod_fast.c */

/* Start: bn_mp_exteuclid.c */
#include <tommath.h>
#ifdef BN_MP_EXTEUCLID_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

   err = MP_OKAY;
_ERR: mp_clear_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL);
   return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_exteuclid.c */

/* Start: bn_mp_fread.c */
#include <tommath.h>
#ifdef BN_MP_FREAD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

   }
   
   return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_fread.c */

/* Start: bn_mp_fwrite.c */
#include <tommath.h>
#ifdef BN_MP_FWRITE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

   }
   
   XFREE (buf);
   return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_fwrite.c */

/* Start: bn_mp_gcd.c */
#include <tommath.h>
#ifdef BN_MP_GCD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  res = MP_OKAY;
LBL_V:mp_clear (&u);
LBL_U:mp_clear (&v);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_gcd.c */

/* Start: bn_mp_get_int.c */
#include <tommath.h>
#ifdef BN_MP_GET_INT_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

    res = (res << DIGIT_BIT) | DIGIT(a,i);
  }

  /* force result to 32-bits always so it is consistent on non 32-bit platforms */
  return res & 0xFFFFFFFFUL;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_get_int.c */

/* Start: bn_mp_grow.c */
#include <tommath.h>
#ifdef BN_MP_GROW_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

      a->dp[i] = 0;
    }
  }
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_grow.c */

/* Start: bn_mp_init.c */
#include <tommath.h>
#ifdef BN_MP_INIT_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  a->alloc = MP_PREC;
  a->sign  = MP_ZPOS;

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_init.c */

/* Start: bn_mp_init_copy.c */
#include <tommath.h>
#ifdef BN_MP_INIT_COPY_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  if ((res = mp_init (a)) != MP_OKAY) {
    return res;
  }
  return mp_copy (b, a);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_init_copy.c */

/* Start: bn_mp_init_multi.c */
#include <tommath.h>
#ifdef BN_MP_INIT_MULTI_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

    }
    va_end(args);
    return res;                /* Assumed ok, if error flagged above. */
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_init_multi.c */

/* Start: bn_mp_init_set.c */
#include <tommath.h>
#ifdef BN_MP_INIT_SET_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

     return err;
  }
  mp_set(a, b);
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_init_set.c */

/* Start: bn_mp_init_set_int.c */
#include <tommath.h>
#ifdef BN_MP_INIT_SET_INT_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  int err;
  if ((err = mp_init(a)) != MP_OKAY) {
     return err;
  }
  return mp_set_int(a, b);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_init_set_int.c */

/* Start: bn_mp_init_size.c */
#include <tommath.h>
#ifdef BN_MP_INIT_SIZE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

      a->dp[x] = 0;
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_init_size.c */

/* Start: bn_mp_invmod.c */
#include <tommath.h>
#ifdef BN_MP_INVMOD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

#ifdef BN_MP_INVMOD_SLOW_C
  return mp_invmod_slow(a, b, c);
#endif

  return MP_VAL;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_invmod.c */

/* Start: bn_mp_invmod_slow.c */
#include <tommath.h>
#ifdef BN_MP_INVMOD_SLOW_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  mp_exch (&C, c);
  res = MP_OKAY;
LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_invmod_slow.c */

/* Start: bn_mp_is_square.c */
#include <tommath.h>
#ifdef BN_MP_IS_SQUARE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  *ret = (mp_cmp_mag(&t,arg) == MP_EQ) ? MP_YES : MP_NO;
ERR:mp_clear(&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_is_square.c */

/* Start: bn_mp_jacobi.c */
#include <tommath.h>
#ifdef BN_MP_JACOBI_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  res = MP_OKAY;
LBL_P1:mp_clear (&p1);
LBL_A1:mp_clear (&a1);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_jacobi.c */

/* Start: bn_mp_karatsuba_mul.c */
#include <tommath.h>
#ifdef BN_MP_KARATSUBA_MUL_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

 * let n represent half of the number of digits in 
 * the min(a,b)
 *
 * a = a1 * B**n + a0
 * b = b1 * B**n + b0
 *
 * Then, a * b => 
   a1b1 * B**2n + ((a1 + a0)(b1 + b0) - (a0b0 + a1b1)) * B + a0b0
 *
 * Note that a1b1 and a0b0 are used twice and only need to be 
 * computed once.  So in total three half size (half # of 
 * digit) multiplications are performed, a0b0, a1b1 and 
 * (a1+b1)(a0+b0)
 *
 * Note that a multiplication of half the digits requires
 * 1/4th the number of single precision multiplications so in 
 * total after one call 25% of the single precision multiplications 
 * are saved.  Note also that the call to mp_mul can end up back 
 * in this function if the a0, a1, b0, or b1 are above the threshold.  
 * This is known as divide-and-conquer and leads to the famous 

  /* now calc the products x0y0 and x1y1 */
  /* after this x0 is no longer required, free temp [x0==t2]! */
  if (mp_mul (&x0, &y0, &x0y0) != MP_OKAY)  
    goto X1Y1;          /* x0y0 = x0*y0 */
  if (mp_mul (&x1, &y1, &x1y1) != MP_OKAY)
    goto X1Y1;          /* x1y1 = x1*y1 */

  /* now calc x1+x0 and y1+y0 */
  if (s_mp_add (&x1, &x0, &t1) != MP_OKAY)
    goto X1Y1;          /* t1 = x1 - x0 */
  if (s_mp_add (&y1, &y0, &x0) != MP_OKAY)
    goto X1Y1;          /* t2 = y1 - y0 */
  if (mp_mul (&t1, &x0, &t1) != MP_OKAY)
    goto X1Y1;          /* t1 = (x1 + x0) * (y1 + y0) */

  /* add x0y0 */
  if (mp_add (&x0y0, &x1y1, &x0) != MP_OKAY)
    goto X1Y1;          /* t2 = x0y0 + x1y1 */
  if (s_mp_sub (&t1, &x0, &t1) != MP_OKAY)
    goto X1Y1;          /* t1 = (x1+x0)*(y1+y0) - (x1y1 + x0y0) */

  /* shift by B */
  if (mp_lshd (&t1, B) != MP_OKAY)
    goto X1Y1;          /* t1 = (x0y0 + x1y1 - (x1-x0)*(y1-y0))<<B */
  if (mp_lshd (&x1y1, B * 2) != MP_OKAY)
    goto X1Y1;          /* x1y1 = x1y1 << 2*B */

Y0:mp_clear (&y0);
X1:mp_clear (&x1);
X0:mp_clear (&x0);
ERR:
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_karatsuba_mul.c */

/* Start: bn_mp_karatsuba_sqr.c */
#include <tommath.h>
#ifdef BN_MP_KARATSUBA_SQR_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  /* now calc the products x0*x0 and x1*x1 */
  if (mp_sqr (&x0, &x0x0) != MP_OKAY)
    goto X1X1;           /* x0x0 = x0*x0 */
  if (mp_sqr (&x1, &x1x1) != MP_OKAY)
    goto X1X1;           /* x1x1 = x1*x1 */

  /* now calc (x1+x0)**2 */
  if (s_mp_add (&x1, &x0, &t1) != MP_OKAY)
    goto X1X1;           /* t1 = x1 - x0 */
  if (mp_sqr (&t1, &t1) != MP_OKAY)
    goto X1X1;           /* t1 = (x1 - x0) * (x1 - x0) */

  /* add x0y0 */
  if (s_mp_add (&x0x0, &x1x1, &t2) != MP_OKAY)
    goto X1X1;           /* t2 = x0x0 + x1x1 */
  if (s_mp_sub (&t1, &t2, &t1) != MP_OKAY)
    goto X1X1;           /* t1 = (x1+x0)**2 - (x0x0 + x1x1) */

  /* shift by B */
  if (mp_lshd (&t1, B) != MP_OKAY)
    goto X1X1;           /* t1 = (x0x0 + x1x1 - (x1-x0)*(x1-x0))<<B */
  if (mp_lshd (&x1x1, B * 2) != MP_OKAY)
    goto X1X1;           /* x1x1 = x1x1 << 2*B */

T1:mp_clear (&t1);
X1:mp_clear (&x1);
X0:mp_clear (&x0);
ERR:
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_karatsuba_sqr.c */

/* Start: bn_mp_lcm.c */
#include <tommath.h>
#ifdef BN_MP_LCM_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  c->sign = MP_ZPOS;

LBL_T:
  mp_clear_multi (&t1, &t2, NULL);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_lcm.c */

/* Start: bn_mp_lshd.c */
#include <tommath.h>
#ifdef BN_MP_LSHD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

      *top++ = 0;
    }
  }
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_lshd.c */

/* Start: bn_mp_mod.c */
#include <tommath.h>
#ifdef BN_MP_MOD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

    mp_exch (&t, c);
  }

  mp_clear (&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_mod.c */

/* Start: bn_mp_mod_2d.c */
#include <tommath.h>
#ifdef BN_MP_MOD_2D_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  c->dp[b / DIGIT_BIT] &=
    (mp_digit) ((((mp_digit) 1) << (((mp_digit) b) % DIGIT_BIT)) - ((mp_digit) 1));
  mp_clamp (c);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_mod_2d.c */

/* Start: bn_mp_mod_d.c */
#include <tommath.h>
#ifdef BN_MP_MOD_D_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

int
mp_mod_d (mp_int * a, mp_digit b, mp_digit * c)
{
  return mp_div_d(a, b, NULL, c);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_mod_d.c */

/* Start: bn_mp_montgomery_calc_normalization.c */
#include <tommath.h>
#ifdef BN_MP_MONTGOMERY_CALC_NORMALIZATION_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

      }
    }
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_montgomery_calc_normalization.c */

/* Start: bn_mp_montgomery_reduce.c */
#include <tommath.h>
#ifdef BN_MP_MONTGOMERY_REDUCE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  if (mp_cmp_mag (x, n) != MP_LT) {
    return s_mp_sub (x, n, x);
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_montgomery_reduce.c */

/* Start: bn_mp_montgomery_setup.c */
#include <tommath.h>
#ifdef BN_MP_MONTGOMERY_SETUP_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  /* rho = -1/m mod b */
  *rho = (((mp_word)1 << ((mp_word) DIGIT_BIT)) - x) & MP_MASK;

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_montgomery_setup.c */

/* Start: bn_mp_mul.c */
#include <tommath.h>
#ifdef BN_MP_MUL_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

#endif

  }
  c->sign = (c->used > 0) ? neg : MP_ZPOS;
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_mul.c */

/* Start: bn_mp_mul_2.c */
#include <tommath.h>
#ifdef BN_MP_MUL_2_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

      *tmpb++ = 0;
    }
  }
  b->sign = a->sign;
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_mul_2.c */

/* Start: bn_mp_mul_2d.c */
#include <tommath.h>
#ifdef BN_MP_MUL_2D_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

    }
  }
  mp_clamp (c);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_mul_2d.c */

/* Start: bn_mp_mul_d.c */
#include <tommath.h>
#ifdef BN_MP_MUL_D_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  c->used = a->used + 1;
  mp_clamp(c);

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_mul_d.c */

/* Start: bn_mp_mulmod.c */
#include <tommath.h>
#ifdef BN_MP_MULMOD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
 */

/* d = a * b (mod c) */

int mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
{
  int     res;
  mp_int  t;

  if ((res = mp_init (&t)) != MP_OKAY) {
    return res;
  }

  if ((res = mp_mul (a, b, &t)) != MP_OKAY) {
    mp_clear (&t);
    return res;
  }
  res = mp_mod (&t, c, d);
  mp_clear (&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_mulmod.c */

/* Start: bn_mp_n_root.c */
#include <tommath.h>
#ifdef BN_MP_N_ROOT_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

LBL_T3:mp_clear (&t3);
LBL_T2:mp_clear (&t2);
LBL_T1:mp_clear (&t1);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_n_root.c */

/* Start: bn_mp_neg.c */
#include <tommath.h>
#ifdef BN_MP_NEG_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  } else {
     b->sign = MP_ZPOS;
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_neg.c */

/* Start: bn_mp_or.c */
#include <tommath.h>
#ifdef BN_MP_OR_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  }
  mp_clamp (&t);
  mp_exch (c, &t);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_or.c */

/* Start: bn_mp_prime_fermat.c */
#include <tommath.h>
#ifdef BN_MP_PRIME_FERMAT_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  err = MP_OKAY;
LBL_T:mp_clear (&t);
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_prime_fermat.c */

/* Start: bn_mp_prime_is_divisible.c */
#include <tommath.h>
#ifdef BN_MP_PRIME_IS_DIVISIBLE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

      return MP_OKAY;
    }
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_prime_is_divisible.c */

/* Start: bn_mp_prime_is_prime.c */
#include <tommath.h>
#ifdef BN_MP_PRIME_IS_PRIME_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  /* passed the test */
  *result = MP_YES;
LBL_B:mp_clear (&b);
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_prime_is_prime.c */

/* Start: bn_mp_prime_miller_rabin.c */
#include <tommath.h>
#ifdef BN_MP_PRIME_MILLER_RABIN_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  *result = MP_YES;
LBL_Y:mp_clear (&y);
LBL_R:mp_clear (&r);
LBL_N1:mp_clear (&n1);
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_prime_miller_rabin.c */

/* Start: bn_mp_prime_next_prime.c */
#include <tommath.h>
#ifdef BN_MP_PRIME_NEXT_PRIME_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

   err = MP_OKAY;
LBL_ERR:
   mp_clear(&b);
   return err;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_prime_next_prime.c */

/* Start: bn_mp_prime_rabin_miller_trials.c */
#include <tommath.h>
#ifdef BN_MP_PRIME_RABIN_MILLER_TRIALS_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

       }
   }
   return sizes[x-1].t + 1;
}


#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_prime_rabin_miller_trials.c */

/* Start: bn_mp_prime_random_ex.c */
#include <tommath.h>
#ifdef BN_MP_PRIME_RANDOM_EX_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

   /* calc the maskAND value for the MSbyte*/
   maskAND = ((size&7) == 0) ? 0xFF : (0xFF >> (8 - (size & 7)));

   /* calc the maskOR_msb */
   maskOR_msb        = 0;
   maskOR_msb_offset = ((size & 7) == 1) ? 1 : 0;
   if (flags & LTM_PRIME_2MSB_ON) {
      maskOR_msb       |= 0x80 >> ((9 - size) & 7);


   }  

   /* get the maskOR_lsb */
   maskOR_lsb         = 1;
   if (flags & LTM_PRIME_BBS) {
      maskOR_lsb     |= 3;
   }

error:
   XFREE(tmp);
   return err;
}


#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_prime_random_ex.c */

/* Start: bn_mp_radix_size.c */
#include <tommath.h>
#ifdef BN_MP_RADIX_SIZE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  /* return digs + 1, the 1 is for the NULL byte that would be required. */
  *size = digs + 1;
  return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_radix_size.c */

/* Start: bn_mp_radix_smap.c */
#include <tommath.h>
#ifdef BN_MP_RADIX_SMAP_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

 *
 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
 */

/* chars used in radix conversions */
const char *mp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_radix_smap.c */

/* Start: bn_mp_rand.c */
#include <tommath.h>
#ifdef BN_MP_RAND_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

      return res;
    }
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_rand.c */

/* Start: bn_mp_read_radix.c */
#include <tommath.h>
#ifdef BN_MP_READ_RADIX_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  if (mp_iszero(a) != 1) {
     a->sign = neg;
  }
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_read_radix.c */

/* Start: bn_mp_read_signed_bin.c */
#include <tommath.h>
#ifdef BN_MP_READ_SIGNED_BIN_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
 */

/* read signed bin, big endian, first byte is 0==positive or 1==negative */

int mp_read_signed_bin (mp_int * a, const unsigned char *b, int c)
{
  int     res;

  /* read magnitude */
  if ((res = mp_read_unsigned_bin (a, b + 1, c - 1)) != MP_OKAY) {
    return res;
  }

  /* first byte is 0 for positive, non-zero for negative */
  if (b[0] == 0) {
     a->sign = MP_ZPOS;
  } else {
     a->sign = MP_NEG;
  }

  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_read_signed_bin.c */

/* Start: bn_mp_read_unsigned_bin.c */
#include <tommath.h>
#ifdef BN_MP_READ_UNSIGNED_BIN_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
 */

/* reads a unsigned char array, assumes the msb is stored first [big endian] */

int mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c)
{
  int     res;

  /* make sure there are at least two digits */
  if (a->alloc < 2) {
     if ((res = mp_grow(a, 2)) != MP_OKAY) {
        return res;

      a->used += 2;
#endif
  }
  mp_clamp (a);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_read_unsigned_bin.c */

/* Start: bn_mp_reduce.c */
#include <tommath.h>
#ifdef BN_MP_REDUCE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

CLEANUP:
  mp_clear (&q);

  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_reduce.c */

/* Start: bn_mp_reduce_2k.c */
#include <tommath.h>
#ifdef BN_MP_REDUCE_2K_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

   
ERR:
   mp_clear(&q);
   return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_reduce_2k.c */

/* Start: bn_mp_reduce_2k_l.c */
#include <tommath.h>
#ifdef BN_MP_REDUCE_2K_L_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

ERR:
   mp_clear(&q);
   return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_reduce_2k_l.c */

/* Start: bn_mp_reduce_2k_setup.c */
#include <tommath.h>
#ifdef BN_MP_REDUCE_2K_SETUP_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

   
   *d = tmp.dp[0];
   mp_clear(&tmp);
   return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_reduce_2k_setup.c */

/* Start: bn_mp_reduce_2k_setup_l.c */
#include <tommath.h>
#ifdef BN_MP_REDUCE_2K_SETUP_L_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

   }
   
ERR:
   mp_clear(&tmp);
   return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_reduce_2k_setup_l.c */

/* Start: bn_mp_reduce_is_2k.c */
#include <tommath.h>
#ifdef BN_MP_REDUCE_IS_2K_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

      }
   }
   return MP_YES;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_reduce_is_2k.c */

/* Start: bn_mp_reduce_is_2k_l.c */
#include <tommath.h>
#ifdef BN_MP_REDUCE_IS_2K_L_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

      
   }
   return MP_NO;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_reduce_is_2k_l.c */

/* Start: bn_mp_reduce_setup.c */
#include <tommath.h>
#ifdef BN_MP_REDUCE_SETUP_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  
  if ((res = mp_2expt (a, b->used * 2 * DIGIT_BIT)) != MP_OKAY) {
    return res;
  }
  return mp_div (a, b, a, NULL);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_reduce_setup.c */

/* Start: bn_mp_rshd.c */
#include <tommath.h>
#ifdef BN_MP_RSHD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  }
  
  /* remove excess digits */
  a->used -= b;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_rshd.c */

/* Start: bn_mp_set.c */
#include <tommath.h>
#ifdef BN_MP_SET_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

void mp_set (mp_int * a, mp_digit b)
{
  mp_zero (a);
  a->dp[0] = b & MP_MASK;
  a->used  = (a->dp[0] != 0) ? 1 : 0;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_set.c */

/* Start: bn_mp_set_int.c */
#include <tommath.h>
#ifdef BN_MP_SET_INT_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

    a->used += 1;
  }
  mp_clamp (a);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_set_int.c */

/* Start: bn_mp_shrink.c */
#include <tommath.h>
#ifdef BN_MP_SHRINK_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

    a->dp    = tmp;
    a->alloc = a->used;
  }
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_shrink.c */

/* Start: bn_mp_signed_bin_size.c */
#include <tommath.h>
#ifdef BN_MP_SIGNED_BIN_SIZE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

/* get the size for an signed equivalent */
int mp_signed_bin_size (mp_int * a)
{
  return 1 + mp_unsigned_bin_size (a);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_signed_bin_size.c */

/* Start: bn_mp_sqr.c */
#include <tommath.h>
#ifdef BN_MP_SQR_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

#endif
  }
  b->sign = MP_ZPOS;
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_sqr.c */

/* Start: bn_mp_sqrmod.c */
#include <tommath.h>
#ifdef BN_MP_SQRMOD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

    return res;
  }
  res = mp_mod (&t, b, c);
  mp_clear (&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_sqrmod.c */

/* Start: bn_mp_sqrt.c */
#include <tommath.h>
#ifdef BN_MP_SQRT_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

E1: mp_clear(&t2);
E2: mp_clear(&t1);
  return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_sqrt.c */

/* Start: bn_mp_sub.c */
#include <tommath.h>
#ifdef BN_MP_SUB_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

      res = s_mp_sub (b, a, c);
    }
  }
  return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_sub.c */

/* Start: bn_mp_sub_d.c */
#include <tommath.h>
#ifdef BN_MP_SUB_D_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  }
  mp_clamp(c);
  return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_sub_d.c */

/* Start: bn_mp_submod.c */
#include <tommath.h>
#ifdef BN_MP_SUBMOD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  }
  res = mp_mod (&t, c, d);
  mp_clear (&t);
  return res;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_submod.c */

/* Start: bn_mp_to_signed_bin.c */
#include <tommath.h>
#ifdef BN_MP_TO_SIGNED_BIN_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

    return res;
  }
  b[0] = (unsigned char) ((a->sign == MP_ZPOS) ? 0 : 1);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_to_signed_bin.c */

/* Start: bn_mp_to_signed_bin_n.c */
#include <tommath.h>
#ifdef BN_MP_TO_SIGNED_BIN_N_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

   if (*outlen < (unsigned long)mp_signed_bin_size(a)) {
      return MP_VAL;
   }
   *outlen = mp_signed_bin_size(a);
   return mp_to_signed_bin(a, b);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_to_signed_bin_n.c */

/* Start: bn_mp_to_unsigned_bin.c */
#include <tommath.h>
#ifdef BN_MP_TO_UNSIGNED_BIN_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  }
  bn_reverse (b, x);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_to_unsigned_bin.c */

/* Start: bn_mp_to_unsigned_bin_n.c */
#include <tommath.h>
#ifdef BN_MP_TO_UNSIGNED_BIN_N_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

   if (*outlen < (unsigned long)mp_unsigned_bin_size(a)) {
      return MP_VAL;
   }
   *outlen = mp_unsigned_bin_size(a);
   return mp_to_unsigned_bin(a, b);
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_to_unsigned_bin_n.c */

/* Start: bn_mp_toom_mul.c */
#include <tommath.h>
#ifdef BN_MP_TOOM_MUL_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

                    &a0, &a1, &a2, &b0, &b1, 
                    &b2, &tmp1, &tmp2, NULL);
     return res;
}     
     
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_toom_mul.c */

/* Start: bn_mp_toom_sqr.c */
#include <tommath.h>
#ifdef BN_MP_TOOM_SQR_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

ERR:
     mp_clear_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL);
     return res;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_toom_sqr.c */

/* Start: bn_mp_toradix.c */
#include <tommath.h>
#ifdef BN_MP_TORADIX_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  *str = '\0';

  mp_clear (&t);
  return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_toradix.c */

/* Start: bn_mp_toradix_n.c */
#include <tommath.h>
#ifdef BN_MP_TORADIX_N_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  mp_clear (&t);
  return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_toradix_n.c */

/* Start: bn_mp_unsigned_bin_size.c */
#include <tommath.h>
#ifdef BN_MP_UNSIGNED_BIN_SIZE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

/* get the size for an unsigned equivalent */
int mp_unsigned_bin_size (mp_int * a)
{
  int     size = mp_count_bits (a);
  return (size / 8 + ((size & 7) != 0 ? 1 : 0));
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_unsigned_bin_size.c */

/* Start: bn_mp_xor.c */
#include <tommath.h>
#ifdef BN_MP_XOR_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  mp_clamp (&t);
  mp_exch (c, &t);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_xor.c */

/* Start: bn_mp_zero.c */
#include <tommath.h>
#ifdef BN_MP_ZERO_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  tmp = a->dp;
  for (n = 0; n < a->alloc; n++) {
     *tmp++ = 0;
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_mp_zero.c */

/* Start: bn_prime_tab.c */
#include <tommath.h>
#ifdef BN_PRIME_TAB_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
  0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
  0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
#endif
};
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_prime_tab.c */

/* Start: bn_reverse.c */
#include <tommath.h>
#ifdef BN_REVERSE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

    s[ix] = s[iy];
    s[iy] = t;
    ++ix;
    --iy;
  }
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_reverse.c */

/* Start: bn_s_mp_add.c */
#include <tommath.h>
#ifdef BN_S_MP_ADD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  }

  mp_clamp (c);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_s_mp_add.c */

/* Start: bn_s_mp_exptmod.c */
#include <tommath.h>
#ifdef BN_S_MP_EXPTMOD_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *
 * LibTomMath is a library that provides multiple-precision
 * integer arithmetic as well as number theoretic functionality.
 *
 * The library was designed directly after the MPI library by
 * Michael Fromberger but has been written from scratch with
 * additional optimizations in place.
 *
 * The library is free for all purposes without any express
 * guarantee it works.
 *
 * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
 */

#ifdef MP_LOW_MEM
   #define TAB_SIZE 32
#else
   #define TAB_SIZE 256
#endif

int s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode)

  for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
    mp_clear (&M[x]);
  }
  return err;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_s_mp_exptmod.c */

/* Start: bn_s_mp_mul_digs.c */
#include <tommath.h>
#ifdef BN_S_MP_MUL_DIGS_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  mp_exch (&t, c);

  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_s_mp_mul_digs.c */

/* Start: bn_s_mp_mul_high_digs.c */
#include <tommath.h>
#ifdef BN_S_MP_MUL_HIGH_DIGS_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

  }
  mp_clamp (&t);
  mp_exch (&t, c);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_s_mp_mul_high_digs.c */

/* Start: bn_s_mp_sqr.c */
#include <tommath.h>
#ifdef BN_S_MP_SQR_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  mp_clamp (&t);
  mp_exch (&t, b);
  mp_clear (&t);
  return MP_OKAY;
}
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_s_mp_sqr.c */

/* Start: bn_s_mp_sub.c */
#include <tommath.h>
#ifdef BN_S_MP_SUB_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis

  mp_clamp (c);
  return MP_OKAY;
}

#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bn_s_mp_sub.c */

/* Start: bncore.c */
#include <tommath.h>
#ifdef BNCORE_C
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 *

 */

/* Known optimal configurations

 CPU                    /Compiler     /MUL CUTOFF/SQR CUTOFF
-------------------------------------------------------------
 Intel P4 Northwood     /GCC v3.4.1   /        88/       128/LTM 0.32 ;-)
 AMD Athlon64           /GCC v3.4.4   /        80/       120/LTM 0.35
 
*/

int     KARATSUBA_MUL_CUTOFF = 80,      /* Min. number of digits before Karatsuba multiplication is used. */
        KARATSUBA_SQR_CUTOFF = 120,     /* Min. number of digits before Karatsuba squaring is used. */
        
        TOOM_MUL_CUTOFF      = 350,      /* no optimal values of these are known yet so set em high */
        TOOM_SQR_CUTOFF      = 400; 
#endif

/* $Source: /root/tcl/repos-to-convert/tcl/libtommath/pre_gen/mpi.c,v $ */
/* $Revision: 1.1.1.3 $ */
/* $Date: 2005/09/26 16:32:22 $ */

/* End: bncore.c */


/* EOF */

Greg Rose \\
QUALCOMM Australia \\
\end{tabular}
%\end{small}
}
}
\maketitle
This text has been placed in the public domain.  This text corresponds to the v0.36 release of the 
LibTomMath project.

\begin{alltt}
Tom St Denis
111 Banning Rd
Ottawa, Ontario
K2L 1C3

\subsection{Karatsuba Multiplication}
Karatsuba \cite{KARA} multiplication when originally proposed in 1962 was among the first set of algorithms to break the $O(n^2)$ barrier for
general purpose multiplication.  Given two polynomial basis representations $f(x) = ax + b$ and $g(x) = cx + d$, Karatsuba proved with 
light algebra \cite{KARAP} that the following polynomial is equivalent to multiplication of the two integers the polynomials represent.

\begin{equation}
f(x) \cdot g(x) = acx^2 + ((a + b)(c + d) - (ac + bd))x + bd
\end{equation}

Using the observation that $ac$ and $bd$ could be re-used only three half sized multiplications would be required to produce the product.  Applying
this algorithm recursively, the work factor becomes $O(n^{lg(3)})$ which is substantially better than the work factor $O(n^2)$ of the Comba technique.  It turns 
out what Karatsuba did not know or at least did not publish was that this is simply polynomial basis multiplication with the points 
$\zeta_0$, $\zeta_{\infty}$ and $\zeta_{1}$.  Consider the resultant system of equations.

\begin{center}
\begin{tabular}{rcrcrcrc}
$\zeta_{0}$ &      $=$ &  &  &  & & $w_0$ \\
$\zeta_{1}$ &      $=$ & $w_2$ & $+$ & $w_1$ & $+$ & $w_0$ \\
$\zeta_{\infty}$ & $=$ & $w_2$ &  & &  & \\
\end{tabular}
\end{center}

By adding the first and last equation to the equation in the middle the term $w_1$ can be isolated and all three coefficients solved for.  The simplicity
of this system of equations has made Karatsuba fairly popular.  In fact the cutoff point is often fairly low\footnote{With LibTomMath 0.18 it is 70 and 109 digits for the Intel P4 and AMD Athlon respectively.}
making it an ideal algorithm to speed up certain public key cryptosystems such as RSA and Diffie-Hellman.  


\newpage\begin{figure}[!here]
\begin{small}
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_karatsuba\_mul}. \\
\textbf{Input}.   mp\_int $a$ and mp\_int $b$ \\

5.  $y0 \leftarrow b \mbox{ (mod }\beta^B\mbox{)}$ \\
6.  $x1 \leftarrow \lfloor a / \beta^B \rfloor$ (\textit{mp\_rshd}) \\
7.  $y1 \leftarrow \lfloor b / \beta^B \rfloor$ \\
\\
Calculate the three products. \\
8.  $x0y0 \leftarrow x0 \cdot y0$ (\textit{mp\_mul}) \\
9.  $x1y1 \leftarrow x1 \cdot y1$ \\
10.  $t1 \leftarrow x1 + x0$ (\textit{mp\_add}) \\
11.  $x0 \leftarrow y1 + y0$ \\
12.  $t1 \leftarrow t1 \cdot x0$ \\
\\
Calculate the middle term. \\
13.  $x0 \leftarrow x0y0 + x1y1$ \\
14.  $t1 \leftarrow t1 - x0$ (\textit{s\_mp\_sub}) \\
\\
Calculate the final product. \\
15.  $t1 \leftarrow t1 \cdot \beta^B$ (\textit{mp\_lshd}) \\
16.  $x1y1 \leftarrow x1y1 \cdot \beta^{2B}$ \\
17.  $t1 \leftarrow x0y0 + t1$ \\
18.  $c \leftarrow t1 + x1y1$ \\
19.  Clear all of the temporary variables. \\

\index{radix point}
In order to split the two inputs into their respective halves, a suitable \textit{radix point} must be chosen.  The radix point chosen must
be used for both of the inputs meaning that it must be smaller than the smallest input.  Step 3 chooses the radix point $B$ as half of the 
smallest input \textbf{used} count.  After the radix point is chosen the inputs are split into lower and upper halves.  Step 4 and 5 
compute the lower halves.  Step 6 and 7 computer the upper halves.  

After the halves have been computed the three intermediate half-size products must be computed.  Step 8 and 9 compute the trivial products
$x0 \cdot y0$ and $x1 \cdot y1$.  The mp\_int $x0$ is used as a temporary variable after $x1 + x0$ has been computed.  By using $x0$ instead
of an additional temporary variable, the algorithm can avoid an addition memory allocation operation.

The remaining steps 13 through 18 compute the Karatsuba polynomial through a variety of digit shifting and addition operations.

EXAM,bn_mp_karatsuba_mul.c

The new coding element in this routine, not  seen in previous routines, is the usage of goto statements.  The conventional

\subsection{Karatsuba Squaring}
Let $f(x) = ax + b$ represent the polynomial basis representation of a number to square.  
Let $h(x) = \left ( f(x) \right )^2$ represent the square of the polynomial.  The Karatsuba equation can be modified to square a 
number with the following equation.

\begin{equation}
h(x) = a^2x^2 + \left ((a + b)^2 - (a^2 + b^2) \right )x + b^2
\end{equation}

Upon closer inspection this equation only requires the calculation of three half-sized squares: $a^2$, $b^2$ and $(a + b)^2$.  As in 
Karatsuba multiplication, this algorithm can be applied recursively on the input and will achieve an asymptotic running time of 
$O \left ( n^{lg(3)} \right )$.

If the asymptotic times of Karatsuba squaring and multiplication are the same, why not simply use the multiplication algorithm 
instead?  The answer to this arises from the cutoff point for squaring.  As in multiplication there exists a cutoff point, at which the 
time required for a Comba based squaring and a Karatsuba based squaring meet.  Due to the overhead inherent in the Karatsuba method, the cutoff 
point is fairly high.  For example, on an AMD Athlon XP processor with $\beta = 2^{28}$, the cutoff point is around 127 digits.  

3.  $B \leftarrow \lfloor a.used / 2 \rfloor$ \\
4.  $x0 \leftarrow a \mbox{ (mod }\beta^B\mbox{)}$ (\textit{mp\_mod\_2d}) \\
5.  $x1 \leftarrow \lfloor a / \beta^B \rfloor$ (\textit{mp\_lshd}) \\
\\
Calculate the three squares. \\
6.  $x0x0 \leftarrow x0^2$ (\textit{mp\_sqr}) \\
7.  $x1x1 \leftarrow x1^2$ \\
8.  $t1 \leftarrow x1 + x0$ (\textit{s\_mp\_add}) \\
9.  $t1 \leftarrow t1^2$ \\
\\
Compute the middle term. \\
10.  $t2 \leftarrow x0x0 + x1x1$ (\textit{s\_mp\_add}) \\
11.  $t1 \leftarrow t1 - t2$ \\
\\
Compute final product. \\
12.  $t1 \leftarrow t1\beta^B$ (\textit{mp\_lshd}) \\
13.  $x1x1 \leftarrow x1x1\beta^{2B}$ \\
14.  $t1 \leftarrow t1 + x0x0$ \\
15.  $b \leftarrow t1 + x1x1$ \\
16.  Return(\textit{MP\_OKAY}). \\

This algorithm computes the square of an input $a$ using the Karatsuba technique.  This algorithm is very similar to the Karatsuba based
multiplication algorithm with the exception that the three half-size multiplications have been replaced with three half-size squarings.

The radix point for squaring is simply placed exactly in the middle of the digits when the input has an odd number of digits, otherwise it is
placed just below the middle.  Step 3, 4 and 5 compute the two halves required using $B$
as the radix point.  The first two squares in steps 6 and 7 are rather straightforward while the last square is of a more compact form.

By expanding $\left (x1 + x0 \right )^2$, the $x1^2$ and $x0^2$ terms in the middle disappear, that is $(x0 - x1)^2 - (x1^2 + x0^2)  = 2 \cdot x0 \cdot x1$.
Now if $5n$ single precision additions and a squaring of $n$-digits is faster than multiplying two $n$-digit numbers and doubling then
this method is faster.  Assuming no further recursions occur, the difference can be estimated with the following inequality.

Let $p$ represent the cost of a single precision addition and $q$ the cost of a single precision multiplication both in terms of time\footnote{Or
machine clock cycles.}. 

\begin{equation}

\begin{tabular}{l}
\hline Algorithm \textbf{mp\_montgomery\_setup}. \\
\textbf{Input}.   mp\_int $n$ ($n > 1$ and $(n, 2) = 1$) \\
\textbf{Output}.  $\rho \equiv -1/n_0 \mbox{ (mod }\beta\mbox{)}$ \\
\hline \\
1.  $b \leftarrow n_0$ \\
2.  If $b$ is even return(\textit{MP\_VAL}) \\
3.  $x \leftarrow (((b + 2) \mbox{ AND } 4) << 1) + b$ \\
4.  for $k$ from 0 to $\lceil lg(lg(\beta)) \rceil - 2$ do \\
\hspace{3mm}4.1  $x \leftarrow x \cdot (2 - bx)$ \\
5.  $\rho \leftarrow \beta - x \mbox{ (mod }\beta\mbox{)}$ \\
6.  Return(\textit{MP\_OKAY}). \\
\hline
\end{tabular}
\end{center}

Greg Rose \\
QUALCOMM Australia \\
\end{tabular}
%\end{small}
}
}
\maketitle
This text has been placed in the public domain.  This text corresponds to the v0.36 release of the 
LibTomMath project.

\begin{alltt}
Tom St Denis
111 Banning Rd
Ottawa, Ontario
K2L 1C3