annotate bn_mp_dr_reduce.c @ 1:22d5cf7d4b1a libtommath

Renaming branch
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:23:46 +0000
parents
children d29b64170cf0
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 * LibTomMath is a library that provides multiple-precision
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 * integer arithmetic as well as number theoretic functionality.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 * The library was designed directly after the MPI library by
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 * Michael Fromberger but has been written from scratch with
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 * additional optimizations in place.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 * The library is free for all purposes without any express
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11 * guarantee it works.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15 #include <tommath.h>
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 * Based on algorithm from the paper
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 * "Generating Efficient Primes for Discrete Log Cryptosystems"
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 * Chae Hoon Lim, Pil Loong Lee,
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23 * POSTECH Information Research Laboratories
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25 * The modulus must be of a special format [see manual]
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 * Has been modified to use algorithm 7.10 from the LTM book instead
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
28 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29 * Input x must be in the range 0 <= x <= (n-1)**2
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31 int
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 mp_dr_reduce (mp_int * x, mp_int * n, mp_digit k)
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33 {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34 int err, i, m;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35 mp_word r;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
36 mp_digit mu, *tmpx1, *tmpx2;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
37
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
38 /* m = digits in modulus */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39 m = n->used;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
40
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41 /* ensure that "x" has at least 2m digits */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
42 if (x->alloc < m + m) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
43 if ((err = mp_grow (x, m + m)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
44 return err;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
46 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
47
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48 /* top of loop, this is where the code resumes if
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
49 * another reduction pass is required.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51 top:
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52 /* aliases for digits */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
53 /* alias for lower half of x */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
54 tmpx1 = x->dp;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
55
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
56 /* alias for upper half of x, or x/B**m */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
57 tmpx2 = x->dp + m;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
58
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
59 /* set carry to zero */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
60 mu = 0;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
61
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
62 /* compute (x mod B**m) + k * [x/B**m] inline and inplace */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
63 for (i = 0; i < m; i++) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
64 r = ((mp_word)*tmpx2++) * ((mp_word)k) + *tmpx1 + mu;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
65 *tmpx1++ = (mp_digit)(r & MP_MASK);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
66 mu = (mp_digit)(r >> ((mp_word)DIGIT_BIT));
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
67 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
68
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
69 /* set final carry */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
70 *tmpx1++ = mu;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
71
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
72 /* zero words above m */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
73 for (i = m + 1; i < x->used; i++) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
74 *tmpx1++ = 0;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
75 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
76
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
77 /* clamp, sub and return */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
78 mp_clamp (x);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
79
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
80 /* if x >= n then subtract and reduce again
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
81 * Each successive "recursion" makes the input smaller and smaller.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
82 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
83 if (mp_cmp_mag (x, n) != MP_LT) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
84 s_mp_sub(x, n, x);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
85 goto top;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
86 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
87 return MP_OKAY;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
88 }