Line data Source code
1 : #include <tommath.h>
2 : #ifdef BN_MP_REDUCE_2K_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, tomstdenis@gmail.com, http://libtom.org
16 : */
17 :
18 : /* reduces a modulo n where n is of the form 2**p - d */
19 0 : int mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d)
20 : {
21 : mp_int q;
22 : int p, res;
23 :
24 0 : if ((res = mp_init(&q)) != MP_OKAY) {
25 0 : return res;
26 : }
27 :
28 0 : p = mp_count_bits(n);
29 0 : top:
30 : /* q = a/2**p, a = a mod 2**p */
31 0 : if ((res = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
32 0 : goto ERR;
33 : }
34 :
35 0 : if (d != 1) {
36 : /* q = q * d */
37 0 : if ((res = mp_mul_d(&q, d, &q)) != MP_OKAY) {
38 0 : goto ERR;
39 : }
40 : }
41 :
42 : /* a = a + q */
43 0 : if ((res = s_mp_add(a, &q, a)) != MP_OKAY) {
44 0 : goto ERR;
45 : }
46 :
47 0 : if (mp_cmp_mag(a, n) != MP_LT) {
48 0 : s_mp_sub(a, n, a);
49 0 : goto top;
50 : }
51 :
52 0 : ERR:
53 0 : mp_clear(&q);
54 0 : return res;
55 : }
56 :
57 : #endif
58 :
59 : /* $Source: /cvs/libtom/libtommath/bn_mp_reduce_2k.c,v $ */
60 : /* $Revision: 1.4 $ */
61 : /* $Date: 2006/12/28 01:25:13 $ */
|