+++ /dev/null
-/* -*-c-*-
- *
- * $Id$
- *
- * Chinese Remainder Theorem computations (Gauss's algorithm)
- *
- * (c) 1999 Straylight/Edgeware
- */
-
-/*----- Licensing notice --------------------------------------------------*
- *
- * This file is part of Catacomb.
- *
- * Catacomb is free software; you can redistribute it and/or modify
- * it under the terms of the GNU Library General Public License as
- * published by the Free Software Foundation; either version 2 of the
- * License, or (at your option) any later version.
- *
- * Catacomb is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU Library General Public License for more details.
- *
- * You should have received a copy of the GNU Library General Public
- * License along with Catacomb; if not, write to the Free
- * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
- * MA 02111-1307, USA.
- */
-
-/*----- Header files ------------------------------------------------------*/
-
-#include "mp.h"
-#include "mpcrt.h"
-#include "mpmul.h"
-#include "mpbarrett.h"
-
-/*----- Main code ---------------------------------------------------------*/
-
-/* --- @mpcrt_create@ --- *
- *
- * Arguments: @mpcrt *c@ = pointer to CRT context
- * @mpcrt_mod *v@ = pointer to vector of moduli
- * @size_t k@ = number of moduli
- * @mp *n@ = product of all moduli (@MP_NEW@ if unknown)
- *
- * Returns: ---
- *
- * Use: Initializes a context for solving Chinese Remainder Theorem
- * problems. The vector of moduli can be incomplete. Omitted
- * items must be left as null pointers. Not all combinations of
- * missing things can be coped with, even if there is
- * technically enough information to cope. For example, if @n@
- * is unspecified, all the @m@ values must be present, even if
- * there is one modulus with both @m@ and @n@ (from which the
- * product of all moduli could clearly be calculated).
- */
-
-void mpcrt_create(mpcrt *c, mpcrt_mod *v, size_t k, mp *n)
-{
- size_t i;
-
- /* --- Simple initialization things --- */
-
- c->k = k;
- c->v = v;
-
- /* --- Work out @n@ if I don't have it already --- */
-
- if (n != MP_NEW)
- n = MP_COPY(n);
- else {
- mpmul mm;
- mpmul_init(&mm);
- for (i = 0; i < k; i++)
- mpmul_add(&mm, v[i].m);
- n = mpmul_done(&mm);
- }
-
- /* --- A quick hack if %$k = 2$% --- */
-
- if (k == 2) {
-
- /* --- The %$n / n_i$% values are trivial in this case --- */
-
- if (!v[0].n)
- v[0].n = MP_COPY(v[1].m);
- if (!v[1].n)
- v[1].n = MP_COPY(v[0].m);
-
- /* --- Now sort out the inverses --- *
- *
- * @mp_gcd@ will ensure that the first argument is negative.
- */
-
- if (!v[0].ni && !v[1].ni) {
- mp *g = MP_NEW;
- mp_gcd(&g, &v[0].ni, &v[1].ni, v[0].n, v[1].n);
- assert(MP_EQ(g, MP_ONE));
- mp_drop(g);
- v[0].ni = mp_add(v[0].ni, v[0].ni, v[1].n);
- } else {
- int i, j;
- mp *x;
-
- if (!v[0].ni)
- i = 0, j = 1;
- else
- i = 1, j = 0;
-
- x = mp_mul(MP_NEW, v[j].n, v[j].ni);
- x = mp_sub(x, x, MP_ONE);
- mp_div(&x, 0, x, v[i].n);
- v[i].ni = x;
- }
- }
-
- /* --- Set up the Barrett context --- */
-
- mpbarrett_create(&c->mb, n);
-
- /* --- Walk through filling in @n@, @ni@ and @nnir@ --- */
-
- for (i = 0; i < k; i++) {
- if (!v[i].n)
- mp_div(&v[i].n, 0, n, v[i].m);
- if (!v[i].ni)
- v[i].ni = mp_modinv(MP_NEW, v[i].n, v[i].m);
- if (!v[i].nni)
- v[i].nni = mp_mul(MP_NEW, v[i].n, v[i].ni);
- }
-
- /* --- Done --- */
-
- mp_drop(n);
-}
-
-/* --- @mpcrt_destroy@ --- *
- *
- * Arguments: @mpcrt *c@ - pointer to CRT context
- *
- * Returns: ---
- *
- * Use: Destroys a CRT context, releasing all the resources it holds.
- */
-
-void mpcrt_destroy(mpcrt *c)
-{
- size_t i;
-
- for (i = 0; i < c->k; i++) {
- if (c->v[i].m) mp_drop(c->v[i].m);
- if (c->v[i].n) mp_drop(c->v[i].n);
- if (c->v[i].ni) mp_drop(c->v[i].ni);
- if (c->v[i].nni) mp_drop(c->v[i].nni);
- }
- mpbarrett_destroy(&c->mb);
-}
-
-/* --- @mpcrt_solve@ --- *
- *
- * Arguments: @mpcrt *c@ = pointer to CRT context
- * @mp *d@ = fake destination
- * @mp **v@ = array of residues
- *
- * Returns: The unique solution modulo the product of the individual
- * moduli, which leaves the given residues.
- *
- * Use: Constructs a result given its residue modulo an array of
- * coprime integers. This can be used to improve performance of
- * RSA encryption or Blum-Blum-Shub generation if the factors
- * of the modulus are known, since results can be computed mod
- * each of the individual factors and then combined at the end.
- * This is rather faster than doing the full-scale modular
- * exponentiation.
- */
-
-mp *mpcrt_solve(mpcrt *c, mp *d, mp **v)
-{
- mp *a = MP_ZERO;
- mp *x = MP_NEW;
- size_t i;
-
- for (i = 0; i < c->k; i++) {
- x = mp_mul(x, c->v[i].nni, v[i]);
- x = mpbarrett_reduce(&c->mb, x, x);
- a = mp_add(a, a, x);
- }
- if (x)
- MP_DROP(x);
- a = mpbarrett_reduce(&c->mb, a, a);
- if (d != MP_NEW)
- MP_DROP(d);
- return (a);
-}
-
-/*----- Test rig ----------------------------------------------------------*/
-
-#ifdef TEST_RIG
-
-static int verify(size_t n, dstr *v)
-{
- mpcrt_mod *m = xmalloc(n * sizeof(mpcrt_mod));
- mp **r = xmalloc(n * sizeof(mp *));
- mpcrt c;
- mp *a, *b;
- size_t i;
- int ok = 1;
-
- for (i = 0; i < n; i++) {
- r[i] = *(mp **)v[2 * i].buf;
- m[i].m = *(mp **)v[2 * i + 1].buf;
- m[i].n = 0;
- m[i].ni = 0;
- m[i].nni = 0;
- }
- a = *(mp **)v[2 * n].buf;
-
- mpcrt_create(&c, m, n, 0);
- b = mpcrt_solve(&c, MP_NEW, r);
-
- if (!MP_EQ(a, b)) {
- fputs("\n*** failed\n", stderr);
- fputs("n = ", stderr);
- mp_writefile(c.mb.m, stderr, 10);
- for (i = 0; i < n; i++) {
- fprintf(stderr, "\nr[%u] = ", i);
- mp_writefile(r[i], stderr, 10);
- fprintf(stderr, "\nm[%u] = ", i);
- mp_writefile(m[i].m, stderr, 10);
- fprintf(stderr, "\nN[%u] = ", i);
- mp_writefile(m[i].n, stderr, 10);
- fprintf(stderr, "\nM[%u] = ", i);
- mp_writefile(m[i].ni, stderr, 10);
- }
- fputs("\nresult = ", stderr);
- mp_writefile(b, stderr, 10);
- fputs("\nexpect = ", stderr);
- mp_writefile(a, stderr, 10);
- fputc('\n', stderr);
- ok = 0;
- }
-
- for (i = 0; i < n; i++)
- mp_drop(r[i]);
- mp_drop(a);
- mp_drop(b);
- mpcrt_destroy(&c);
- xfree(m);
- xfree(r);
- assert(mparena_count(MPARENA_GLOBAL) == 0);
- return (ok);
-}
-
-static int crt1(dstr *v) { return verify(1, v); }
-static int crt2(dstr *v) { return verify(2, v); }
-static int crt3(dstr *v) { return verify(3, v); }
-static int crt4(dstr *v) { return verify(4, v); }
-static int crt5(dstr *v) { return verify(5, v); }
-
-static test_chunk tests[] = {
- { "crt-1", crt1, { &type_mp, &type_mp,
- &type_mp, 0 } },
- { "crt-2", crt2, { &type_mp, &type_mp,
- &type_mp, &type_mp,
- &type_mp, 0 } },
- { "crt-3", crt3, { &type_mp, &type_mp,
- &type_mp, &type_mp,
- &type_mp, &type_mp,
- &type_mp, 0 } },
- { "crt-4", crt4, { &type_mp, &type_mp,
- &type_mp, &type_mp,
- &type_mp, &type_mp,
- &type_mp, &type_mp,
- &type_mp, 0 } },
- { "crt-5", crt5, { &type_mp, &type_mp,
- &type_mp, &type_mp,
- &type_mp, &type_mp,
- &type_mp, &type_mp,
- &type_mp, &type_mp,
- &type_mp, 0 } },
- { 0, 0, { 0 } }
-};
-
-int main(int argc, char *argv[])
-{
- sub_init();
- test_run(argc, argv, tests, SRCDIR "/tests/mpcrt");
- return (0);
-}
-
-#endif
-
-/*----- That's all, folks -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff