imod.c

Arithmetic for integers of almost unlimited size for C and C++. Developed and copyrighted by Ra

    cIasint(&r, 1);
    cI(&rsquare);
    cI(&rcube);
    cI(&u);
    cI(&v);
    cI(&d);
    IslasD(&r, BitsPerDigit * a->length);
    Ixgcd(&d, &u, &v, &r, a);
    if (!Ieq1(&d))
	Merror("cMod: d!=1");
    Ineg(&v);
    while (Ilt0(&v))
	IplasI(&v, &r);
    while (IgeI(&v, &r))
	ImiasI(&v, &r);
    mod->nprime = v.vec[0];
    IasImuI(&rsquare, &r, &r);
    IreasI(&rsquare, a);
    IasImuI(&rcube, &rsquare, &r);
    IreasI(&rcube, a);
    mod->rsquare = newmvec(mod);
    mod->rcube = newmvec(mod);
    for (i = 0; i < rsquare.length; i++)
	mod->rsquare[i] = rsquare.vec[i];
    while (i < mod->length)
	mod->rsquare[i++] = 0;
    for (i = 0; i < rcube.length; i++)
	mod->rcube[i] = rcube.vec[i];
    while (i < mod->length)
	mod->rcube[i++] = 0;
    dI(&r);
    dI(&rsquare);
    dI(&rcube);
    dI(&u);
    dI(&v);
    dI(&d);
}				/* cMod */

/***********************************************************
** EXTERN_FUNCTION(void dMod, (ModulusType *));
**	Destructor Modulus
*/
void 
dMod(mod)
    ModulusType *mod;
{
    int k;
    void *u, *v;

/*	Hier soll jetzt der komplette Speicher der Listen
 *	memsingfree und memdoubfree zurueckgegeben werden, ebenso
 *	die Vektoren in mod.
 */

    delmvec(mod->rcube, mod);
    delmvec(mod->rsquare, mod);
    delmvec(mod->vec, mod);
    dI(&mod->ModIval);
    k = mod->length;
    u = mod->memsingfree;
    while (u)
    {
	v = u;
	Ifree(u);
	u = *((pointer *) v);
    }
    u = mod->memdoubfree;
    while (u)
    {
	v = u;
	Ifree(u);
	u = *((pointer *) v);
    }
}				/* dMod */

/***********************************************************
** EXTERN_FUNCTION(void IasMod, (Integer *, const ModulusType *));
**	Modulus value
*/
void 
IasMod(a, m)
    Integer *a;
    const ModulusType *m;
{
    IasI(a, &m->ModIval);
}				/* IasMod */

/***********************************************************
** EXTERN_FUNCTION(const ModulusType * Mmod, (const Minteger *));
**	Reference Modulus
*/
const ModulusType *
Mmod(a)
    const Minteger *a;
{
    return a->mod;
}				/* Mmod */

/***********************************************************
** EXTERN_FUNCTION(void cM, (Minteger *, ModulusType *));
**	Creator Minteger
*/
void 
cM(a, mod)
    Minteger *a;
    ModulusType *mod;
{
    a->mod = mod;
    a->val = newmvec(mod);
    mvecas0(a->val, mod->length);
}				/* cM */

/***********************************************************
** EXTERN_FUNCTION(void cMasI, (Minteger *, const Integer *,
**	ModulusType *));
**	Creator Minteger, Init Integer
*/
void 
cMasI(r, a, mod)
    Minteger *r;
    const Integer *a;
    ModulusType *mod;
{
    Integer rem;
    int i, k;
    DigitType *t;
    r->mod = mod;
    k = mod->length;
    r->val = newmvec(mod);
    cIasI(&rem, a);
    IreasI(&rem, &(mod->ModIval));
    for (i = 0; i < rem.length; i++)
	r->val[i] = rem.vec[i];
    while (i < k)
	r->val[i++] = 0;
    dI(&rem);
    t = newmdoubvec(mod);
    mvecmul(t, r->val, mod->rsquare, k);
    omvecred(t, mod->vec, mod->nprime, k);
    mvecas(r->val, &t[k], k);
    delmdoubvec(t, mod);
}				/* cMasI */

/***********************************************************
** EXTERN_FUNCTION(void cMasM, (Minteger *, const Minteger *));
**	Creator Minteger, Init Minteger
*/
void 
cMasM(a, b)
    Minteger *a;
    const Minteger *b;
{
    a->mod = b->mod;
    a->val = newmvec(a->mod);
    mvecas(a->val, b->val, a->mod->length);
}				/* cMasM */

/***********************************************************
** EXTERN_FUNCTION(void dM, (Minteger *));
**	Destructor
*/
void 
dM(a)
    Minteger *a;
{
    delmvec(a->val, a->mod);
}				/* dM */

/***********************************************************
** EXTERN_FUNCTION(void MasM, (Minteger *, const Minteger *));
*/
void 
MasM(a, b)
    Minteger *a;
    const Minteger *b;
{
    mvecas(a->val, b->val, a->mod->length);
}				/* MasM */

/***********************************************************
** EXTERN_FUNCTION(void MasI, (Minteger *, const Integer *));
*/
void 
MasI(r, a)
    Minteger *r;
    const Integer *a;
{
    Integer rem;
    ModulusType *mod;
    int i, k;
    DigitType *t;
    mod = r->mod;
    k = mod->length;
    cIasI(&rem, a);
    IreasI(&rem, &(mod->ModIval));
    for (i = 0; i < rem.length; i++)
	r->val[i] = rem.vec[i];
    while (i < k)
	r->val[i++] = 0;
    dI(&rem);
    t = newmdoubvec(mod);
    mvecmul(t, r->val, mod->rsquare, k);
    omvecred(t, mod->vec, mod->nprime, k);
    mvecas(r->val, &t[k], k);
    delmdoubvec(t, mod);
}				/* MasI */

/***********************************************************
** EXTERN_FUNCTION(void IasM, (Integer *, const Minteger *));
*/
void 
IasM(a, r)
    Integer *a;
    const Minteger *r;
{
    DigitType *t;
    int i, k;
    ModulusType *mod;
    mod = r->mod;
    t = newmdoubvec(mod);
    k = mod->length;
    mvecas(t, r->val, k);
    mvecas0(&t[k], k);
    omvecred(t, mod->vec, mod->nprime, k);
    IasI(a, &mod->ModIval);
    mvecas(a->vec, &t[k], k);
    delmdoubvec(t, mod);
    i = k;
    t = &a->vec[k - 1];
    while ((i > 0) && (!*t))
    {
	t--;
	i--;
    }
    a->length = i;
}				/* IasM */

/***********************************************************
** EXTERN_FUNCTION(BOOLEAN Meq0, (const Minteger *));
*/
BOOLEAN 
Meq0(a)
    const Minteger *a;
{
    int k;
    DigitType *u;
    k = a->mod->length;
    u = a->val;
    for (; k > 0; k--)
	if (*u++)
	    return FALSE;
    return TRUE;
}				/* Meq0 */

/***********************************************************
** EXTERN_FUNCTION(void MasMplM, (Minteger *, const Minteger *,
**	const Minteger *));
*/
void 
MasMplM(sum, a, b)
    Minteger *sum;
    const Minteger *a, *b;
{
    DigitType carry;
    int k = sum->mod->length;
    DigitType *mv = sum->mod->vec;
    carry = mvecadd(sum->val, a->val, b->val, k);
    if (carry || !mvecgt(mv, sum->val, k))
	mvecsub(sum->val, sum->val, mv, k);
}				/* MasMplM */

/***********************************************************
** EXTERN_FUNCTION(void MplasM, (Minteger *, const Minteger *));
*/
void 
MplasM(sum, b)
    Minteger *sum;
    const Minteger *b;
{
    DigitType carry;
    int k = sum->mod->length;
    DigitType *mv = sum->mod->vec;
    carry = mvecadd(sum->val, sum->val, b->val, k);
    if (carry || !mvecgt(mv, sum->val, k))
	mvecsub(sum->val, sum->val, mv, k);
}				/* MplasM */

/***********************************************************
** EXTERN_FUNCTION(void MasMmiM, (Minteger *, const Minteger *,
**	const Minteger *));
*/
void 
MasMmiM(diff, a, b)
    Minteger *diff;
    const Minteger *a, *b;
{
    int k = diff->mod->length;
    if (!mvecgt(b->val, a->val, k))
	mvecsub(diff->val, a->val, b->val, k);
    else
	mveccorsub(diff->val, a->val, b->val, diff->mod->vec, k);
}				/* MasMmiM */

/***********************************************************
** EXTERN_FUNCTION(void MmiasM, (Minteger *, const Minteger *));
*/
void 
MmiasM(diff, b)
    Minteger *diff;
    const Minteger *b;
{
    int k = diff->mod->length;
    if (!mvecgt(b->val, diff->val, k))
	mvecsub(diff->val, diff->val, b->val, k);
    else
	mveccorsub(diff->val, diff->val, b->val, diff->mod->vec, k);
}				/* MmiasM */

/***********************************************************
** EXTERN_FUNCTION(void MasMmuM, (Minteger *, const Minteger *,
**	const Minteger *));
*/
void 
MasMmuM(prod, a, b)
    Minteger *prod;
    const Minteger *a, *b;
{
    mdoubvec t;
    ModulusType *m;
    int k;

    m = prod->mod;
    k = m->length;
    t = newmdoubvec(m);
    mvecmul(t, a->val, b->val, k);
    omvecred(t, m->vec, m->nprime, k);
    mvecas(prod->val, &t[k], k);
    delmdoubvec(t, m);
}				/* MasMmuM */

/***********************************************************
** EXTERN_FUNCTION(void MmuasM, (Minteger *, const Minteger *));
*/
void 
MmuasM(prod, b)
    Minteger *prod;
    const Minteger *b;
{
    mdoubvec t;
    ModulusType *m;
    int k;

    m = prod->mod;
    k = m->length;
    t = newmdoubvec(m);
    mvecmul(t, prod->val, b->val, k);
    omvecred(t, m->vec, m->nprime, k);
    mvecas(prod->val, &t[k], k);
    delmdoubvec(t, m);
}				/* MmuasM */

/***********************************************************
** EXTERN_FUNCTION(BOOLEAN MasinvM, (Minteger *, const Minteger *));
*/
BOOLEAN 
MasinvM(inv, a)
    Minteger *inv;
    const Minteger *a;
{
    mdoubvec t;
    ModulusType *mod;
    int k;

    mod = a->mod;
    k = mod->length;
    if (!mvecinv(inv->val, a->val, mod))
	return FALSE;
    t = newmdoubvec(mod);
    mvecmul(t, inv->val, mod->rcube, k);
    omvecred(t, mod->vec, mod->nprime, k);
    mvecas(inv->val, &t[k], k);
    delmdoubvec(t, mod);
    return TRUE;
}				/* MasinvM */

/***********************************************************
** EXTERN_FUNCTION(void MasMdiM, (Minteger *, const Minteger *,
** const Minteger *));
*/

/***********************************************************
** EXTERN_FUNCTION(void MdiasM, (Minteger *, const Minteger *));
*/

/***********************************************************
** EXTERN_FUNCTION(void Mrandom, (Minteger * a));
*/
void 
Mrandom(a)
    Minteger *a;
{
    int i, k;
    DigitType *pa;
    pa = a->val;
    k = a->mod->length;
    pa[k - 1] = Prandom() % (a->mod->vec[k - 1]);
    for (i = k - 2; i >= 0; i--)
	pa[i] = Prandom();
}				/* Mrandom */