3 * $Id: mpcrt.h,v 1.1 1999/11/22 20:50:57 mdw Exp $
5 * Chinese Remainder Theorem computations (Gauss's algorithm)
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.1 1999/11/22 20:50:57 mdw
34 * Add support for solving Chinese Remainder Theorem problems.
45 /*----- Header files ------------------------------------------------------*/
57 /*----- Data structures ---------------------------------------------------*/
59 typedef struct mpcrt_mod
{
60 mp
*m
; /* %$n_i$% -- the modulus */
61 mp
*n
; /* %$N_i = n / n_i$% */
62 mp
*ni
; /* %$M_i = N_i^{-1} \bmod n_i$% */
63 mp
*nnir
; /* %$N_i M_i R \bmod m$% */
66 typedef struct mpcrt
{
67 size_t k
; /* Number of distinct moduli */
68 mpmont mm
; /* Montgomery context for product */
69 mpcrt_mod
*v
; /* Vector of information for each */
72 /*----- Functions provided ------------------------------------------------*/
74 /* --- @mpcrt_create@ --- *
76 * Arguments: @mpcrt *c@ = pointer to CRT context
77 * @mpcrt_mod *v@ = pointer to vector of moduli
78 * @size_t k@ = number of moduli
79 * @mp *n@ = product of all moduli (@MP_NEW@ if unknown)
83 * Use: Initializes a context for solving Chinese Remainder Theorem
84 * problems. The vector of moduli can be incomplete. Omitted
85 * items must be left as null pointers. Not all combinations of
86 * missing things can be coped with, even if there is
87 * technically enough information to cope. For example, if @n@
88 * is unspecified, all the @m@ values must be present, even if
89 * there is one modulus with both @m@ and @n@ (from which the
90 * product of all moduli could clearly be calculated).
93 extern void mpcrt_create(mpcrt */
*c*/
, mpcrt_mod */
*v*/
,
94 size_t /*k*/, mp */
*n*/
);
96 /* --- @mpcrt_destroy@ --- *
98 * Arguments: @mpcrt *c@ - pointer to CRT context
102 * Use: Destroys a CRT context, releasing all the resources it holds.
105 extern void mpcrt_destroy(mpcrt */
*c*/
);
107 /* --- @mpcrt_solve@ --- *
109 * Arguments: @mpcrt *c@ = pointer to CRT context
110 * @mp **v@ = array of residues
112 * Returns: The unique solution modulo the product of the individual
113 * moduli, which leaves the given residues.
115 * Use: Constructs a result given its residue modulo an array of
116 * coprime integers. This can be used to improve performance of
117 * RSA encryption or Blum-Blum-Shub generation if the factors
118 * of the modulus are known, since results can be computed mod
119 * each of the individual factors and then combined at the end.
120 * This is rather faster than doing the full-scale modular
124 extern mp
*mpcrt_solve(mpcrt */
*c*/
, mp
**/
*v*/
);
126 /*----- That's all, folks -------------------------------------------------*/