Mercurial > hg > Members > anatofuz > MoarVM

annotate 3rdparty/libtommath/bn_mp_dr_reduce.c @ 0:2cf249471370

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