3 * Chinese Remainder Theorem computations (Gauss's algorithm)
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 #ifndef CATACOMB_MPCRT_H
29 #define CATACOMB_MPCRT_H
35 /*----- Header files ------------------------------------------------------*/
43 #ifndef CATACOMB_MPBARRETT_H
44 # include "mpbarrett.h"
47 /*----- Data structures ---------------------------------------------------*/
49 typedef struct mpcrt_mod {
50 mp *m; /* %$n_i$% -- the modulus */
51 mp *n; /* %$N_i = n / n_i$% */
52 mp *ni; /* %$M_i = N_i^{-1} \bmod n_i$% */
53 mp *nni; /* %$N_i M_i \bmod m$% */
56 typedef struct mpcrt {
57 size_t k; /* Number of distinct moduli */
58 mpbarrett mb; /* Barrett context for product */
59 mpcrt_mod *v; /* Vector of information for each */
62 /*----- Functions provided ------------------------------------------------*/
64 /* --- @mpcrt_create@ --- *
66 * Arguments: @mpcrt *c@ = pointer to CRT context
67 * @mpcrt_mod *v@ = pointer to vector of moduli
68 * @size_t k@ = number of moduli
69 * @mp *n@ = product of all moduli (@MP_NEW@ if unknown)
73 * Use: Initializes a context for solving Chinese Remainder Theorem
74 * problems. The vector of moduli can be incomplete. Omitted
75 * items must be left as null pointers. Not all combinations of
76 * missing things can be coped with, even if there is
77 * technically enough information to cope. For example, if @n@
78 * is unspecified, all the @m@ values must be present, even if
79 * there is one modulus with both @m@ and @n@ (from which the
80 * product of all moduli could clearly be calculated).
83 extern void mpcrt_create(mpcrt */*c*/, mpcrt_mod */*v*/,
84 size_t /*k*/, mp */*n*/);
86 /* --- @mpcrt_destroy@ --- *
88 * Arguments: @mpcrt *c@ - pointer to CRT context
92 * Use: Destroys a CRT context, releasing all the resources it holds.
95 extern void mpcrt_destroy(mpcrt */*c*/);
97 /* --- @mpcrt_solve@ --- *
99 * Arguments: @mpcrt *c@ = pointer to CRT context
100 * @mp *d@ = fake destination
101 * @mp **v@ = array of residues
103 * Returns: The unique solution modulo the product of the individual
104 * moduli, which leaves the given residues.
106 * Use: Constructs a result given its residue modulo an array of
107 * coprime integers. This can be used to improve performance of
108 * RSA encryption or Blum-Blum-Shub generation if the factors
109 * of the modulus are known, since results can be computed mod
110 * each of the individual factors and then combined at the end.
111 * This is rather faster than doing the full-scale modular
115 extern mp *mpcrt_solve(mpcrt */*c*/, mp */*d*/, mp **/*v*/);
117 /*----- That's all, folks -------------------------------------------------*/