libsunec/impl/mpi.c

3  * Use is subject to license terms.
16  * along with this library; if not, write to the Free Software Foundation,
52   This table is used to compute output lengths for the mp_toradix()
78 /* Value to digit maps for radix conversion   */
193 /* {{{ mp_copy(from, to) */
196   mp_copy(from, to)
198   Copies the mp_int 'from' to the mp_int 'to'.  It is presumed that
199   'to' has already been initialized (if not, use mp_init_copy()
200   instead). If 'from' and 'to' are identical, nothing happens.
203 mp_err mp_copy(const mp_int *from, mp_int *to)
205   ARGCHK(from != NULL && to != NULL, MP_BADARG);
207   if(from == to)
215       If the allocated buffer in 'to' already has enough space to hold
216       all the used digits of 'from', we'll re-use it to avoid hitting
218       to grow anyway, so we just allocate a hunk and make the copy as
221     if(ALLOC(to) >= USED(from)) {
222       s_mp_setz(DIGITS(to) + USED(from), ALLOC(to) - USED(from));
223       s_mp_copy(DIGITS(from), DIGITS(to), USED(from));
231       if(DIGITS(to) != NULL) {
233         s_mp_setz(DIGITS(to), ALLOC(to));
235         s_mp_free(DIGITS(to), ALLOC(to));
238       DIGITS(to) = tmp;
239       ALLOC(to) = ALLOC(from);
243     USED(to) = USED(from);
244     SIGN(to) = SIGN(from);
313   Set mp to zero.  Does not change the allocated size of the structure,
840     const mp_int *xch = b;      /* switch a and b, to do fewer outer loops */
978   /* now add the squares of the digits of a to sqr. */
1047       /* r was set to a above. */
1120   Compute c = a ** b, that is, raise a to the b power.  Uses a
1226      If |a| > m, we need to divide to get the remainder and take the
1229      If |a| < m, we don't need to do any division, just copy and adjust
1232      If |a| == m, we can simply set the result to zero.
1234      This order is intended to minimize the average path length of the
1309   approximation technique to determine this value; the result has the
1315   It is a range error to pass a negative value.
1369   /* Copy result to output parameter */
1723   This just converts z to an mp_int, and uses the existing comparison
1724   routines.  This is sort of inefficient, but it's not clear to me how
1782   binary algorithm due to Josef Stein in 1961 (via Knuth).
2015   /* copy results to output */
2171 ** Compute x = (a ** -1) mod p.  This is similar to Montgomery reduction.
2347   mp_int oddPart, evenPart;     /* parts to combine via CRT. */
2382   /* Use Chinese Remainer theorem to compute a**-1 mod m. */
2422   This is equivalent to the question of whether (a, m) = 1.  If not,
2563   Read an integer from the given string, and set mp to the resulting
2564   value.  The input is presumed to be in base 10.  Leading non-digit
2713     /* Add trailing NUL to end the string        */
2755   not attempt to modify or free the memory associated with this
2782 /* Make sure there are at least 'min' digits allocated to mp              */
2788     /* Set min to next nearest default precision block size */
2818     /* Make sure there is room to increase precision  */
2839 /* Set 'count' digits pointed to by dp to be zeroes                       */
2859 /* Copy 'count' digits from sp to dp                                      */
2879 /* Allocate ni records of nb bytes each, and return a pointer to that     */
2901 /* Free the memory pointed to by ptr                                      */
2956    alternative to multiplication by powers of the radix
2957    The value of USED(mp) must already have been set to the value for
2996   amounts to a bitwise shift of the value.
3008   /* bits to be shifted out of the top word */
3050   /* Shortcut when all digits are to be shifted off */
3080 /* Divide by two -- take advantage of radix properties to do it fast      */
3128   amounts to a bitwise AND of the value, and does not require the full
3158   amounts to a bitwise shift of the value, and does not require the
3190   leading digit of b to be at least half the radix, which we
3230 /* Add d to |mp| in place                                                 */
3509     Add up all digits up to the precision of b.  If b had initially
3512     less precision, we'll have to make sure the carry out is duly
3554      allocator unless we're sure we have to?
3602     Add up all digits up to the precision of b.  If b had initially
3605     less precision, we'll have to make sure the carry out is duly
3642      allocator unless we're sure we have to?
3685     Add up all digits up to the precision of b.  If b had initially
3688     less precision, we'll have to make sure the carry out is duly
3725      allocator unless we're sure we have to?
3763     Subtract and propagate borrow.  Up to the precision of b, this
3765     carries get to the right place.  This saves having to pad b out to
3766     the precision of a just to make the loops work right...
3837     Subtract and propagate borrow.  Up to the precision of b, this
3839     carries get to the right place.  This saves having to pad b out to
3840     the precision of a just to make the loops work right...
4066 /* Add the squares of the digits of a to the digits of b. */
4119     /* now add to ps */
4247   /* Normalize to optimize guessing       */
4300     /* See what that multiplies out to                   */
4305        If it's too big, back it off.  We should not have to do this
4307        method by which this could be reduced to a maximum of once, but
4309      * When using s_mpv_div_2dx1d, we may have to do this 3 times.
4327       have to check for failures here
4378   can nearly halve the time required to do modular exponentiation,
4379   as compared to using the full integer divide to reduce.
4409   /* If x < 0, add b^(k+1) to it */
4595   Convert the given character to its digit value, in the given radix.
4600   expected to know what you're up to.
4636   Convert val to a radix-r digit, if possible.  If val is out of range
4641   expected to know what you're doing.
4665    Return an estimate for how long a string is needed to hold a radix
4813         if (x & 0x80) { /* add one leading zero to make output positive.  */