Mercurial > dropbear

comparison libtommath/bn_mp_dr_reduce.c @ 399:a707e6148060

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge of '5fdf69ca60d1683cdd9f4c2595134bed26394834' and '6b61c50f4cf888bea302ac8fcf5dbb573b443251'
author Matt Johnston <matt@ucc.asn.au>
date Sat, 03 Feb 2007 08:20:34 +0000
parents 5ff8218bcee9
children 60fc6476e044
comparison
equal deleted inserted replaced
394:17d097fc111c 399:a707e6148060
1 #include <tommath.h>
2 #ifdef BN_MP_DR_REDUCE_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4 *
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
7 *
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
11 *
12 * The library is free for all purposes without any express
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://math.libtomcrypt.com
16 */
17
18 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm.
19 *
20 * Based on algorithm from the paper
21 *
22 * "Generating Efficient Primes for Discrete Log Cryptosystems"
23 * Chae Hoon Lim, Pil Joong Lee,
24 * POSTECH Information Research Laboratories
25 *
26 * The modulus must be of a special format [see manual]
27 *
28 * Has been modified to use algorithm 7.10 from the LTM book instead
29 *
30 * Input x must be in the range 0 <= x <= (n-1)**2
31 */
32 int
33 mp_dr_reduce (mp_int * x, mp_int * n, mp_digit k)
34 {
35 int err, i, m;
36 mp_word r;
37 mp_digit mu, *tmpx1, *tmpx2;
38
39 /* m = digits in modulus */
40 m = n->used;
41
42 /* ensure that "x" has at least 2m digits */
43 if (x->alloc < m + m) {
44 if ((err = mp_grow (x, m + m)) != MP_OKAY) {
45 return err;
46 }
47 }
48
49 /* top of loop, this is where the code resumes if
50 * another reduction pass is required.
51 */
52 top:
53 /* aliases for digits */
54 /* alias for lower half of x */
55 tmpx1 = x->dp;
56
57 /* alias for upper half of x, or x/B**m */
58 tmpx2 = x->dp + m;
59
60 /* set carry to zero */
61 mu = 0;
62
63 /* compute (x mod B**m) + k * [x/B**m] inline and inplace */
64 for (i = 0; i < m; i++) {
65 r = ((mp_word)*tmpx2++) * ((mp_word)k) + *tmpx1 + mu;
66 *tmpx1++ = (mp_digit)(r & MP_MASK);
67 mu = (mp_digit)(r >> ((mp_word)DIGIT_BIT));
68 }
69
70 /* set final carry */
71 *tmpx1++ = mu;
72
73 /* zero words above m */
74 for (i = m + 1; i < x->used; i++) {
75 *tmpx1++ = 0;
76 }
77
78 /* clamp, sub and return */
79 mp_clamp (x);
80
81 /* if x >= n then subtract and reduce again
82 * Each successive "recursion" makes the input smaller and smaller.
83 */
84 if (mp_cmp_mag (x, n) != MP_LT) {
85 s_mp_sub(x, n, x);
86 goto top;
87 }
88 return MP_OKAY;
89 }
90 #endif
91
92 /* $Source: /cvs/libtom/libtommath/bn_mp_dr_reduce.c,v $ */
93 /* $Revision: 1.3 $ */
94 /* $Date: 2006/03/31 14:18:44 $ */