9512fe850e98fdd448c638ca63fdd92a8a510255ahl/* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
9512fe850e98fdd448c638ca63fdd92a8a510255ahl/* All Rights Reserved */
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl/*
9512fe850e98fdd448c638ca63fdd92a8a510255ahl * Copyright (c) 1980 Regents of the University of California.
9512fe850e98fdd448c638ca63fdd92a8a510255ahl * All rights reserved. The Berkeley software License Agreement
9512fe850e98fdd448c638ca63fdd92a8a510255ahl * specifies the terms and conditions for redistribution.
9512fe850e98fdd448c638ca63fdd92a8a510255ahl */
9512fe850e98fdd448c638ca63fdd92a8a510255ahl/* Portions Copyright(c) 1988, Sun Microsystems Inc. */
9512fe850e98fdd448c638ca63fdd92a8a510255ahl/* All Rights Reserved */
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl/*
9512fe850e98fdd448c638ca63fdd92a8a510255ahl * Copyright (c) 1997, by Sun Microsystems, Inc.
9512fe850e98fdd448c638ca63fdd92a8a510255ahl * All rights reserved.
9512fe850e98fdd448c638ca63fdd92a8a510255ahl */
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl#ident "%Z%%M% %I% %E% SMI" /* SVr4.0 1.1 */
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl/* LINTLIBRARY */
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl#include <mp.h>
9512fe850e98fdd448c638ca63fdd92a8a510255ahl#include "libmp.h"
9512fe850e98fdd448c638ca63fdd92a8a510255ahl#include <sys/types.h>
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahlvoid
9512fe850e98fdd448c638ca63fdd92a8a510255ahlmp_gcd(MINT *a, MINT *b, MINT *c)
9512fe850e98fdd448c638ca63fdd92a8a510255ahl{
9512fe850e98fdd448c638ca63fdd92a8a510255ahl MINT x, y, z, w;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl x.len = y.len = z.len = w.len = 0;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(a, &x);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(b, &y);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl while (y.len != 0) {
9512fe850e98fdd448c638ca63fdd92a8a510255ahl mp_mdiv(&x, &y, &w, &z);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(&y, &x);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(&z, &y);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl }
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(&x, c);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_xfree(&x);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_xfree(&y);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_xfree(&z);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_xfree(&w);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl}
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahlvoid
9512fe850e98fdd448c638ca63fdd92a8a510255ahlmp_invert(MINT *x1, MINT *x0, MINT *c)
9512fe850e98fdd448c638ca63fdd92a8a510255ahl{
9512fe850e98fdd448c638ca63fdd92a8a510255ahl MINT u2, u3;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl MINT v2, v3;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl MINT zero;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl MINT q, r;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl MINT t;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl MINT x0_prime;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl static MINT *one = NULL;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl /*
9512fe850e98fdd448c638ca63fdd92a8a510255ahl * Minimize calls to allocators. Don't use pointers for local
9512fe850e98fdd448c638ca63fdd92a8a510255ahl * variables, for the one "initialized" multiple precision
9512fe850e98fdd448c638ca63fdd92a8a510255ahl * variable, do it just once.
9512fe850e98fdd448c638ca63fdd92a8a510255ahl */
9512fe850e98fdd448c638ca63fdd92a8a510255ahl if (one == NULL)
9512fe850e98fdd448c638ca63fdd92a8a510255ahl one = mp_itom(1);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl zero.len = q.len = r.len = t.len = 0;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl x0_prime.len = u2.len = u3.len = 0;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(x0, &u3);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(x0, &x0_prime);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl v2.len = v3.len = 0;
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(one, &v2);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(x1, &v3);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
23b5c241225a8ade2b6b9f06ebb891ee459e3b02tomee while (mp_mcmp(&v3, &zero) != 0) {
23b5c241225a8ade2b6b9f06ebb891ee459e3b02tomee /* invariant: x0*u1 + x1*u2 = u3 */
23b5c241225a8ade2b6b9f06ebb891ee459e3b02tomee /* invariant: x0*v1 + x2*v2 = v3 */
23b5c241225a8ade2b6b9f06ebb891ee459e3b02tomee /* invariant: x(n+1) = x(n-1) % x(n) */
23b5c241225a8ade2b6b9f06ebb891ee459e3b02tomee mp_mdiv(&u3, &v3, &q, &r);
23b5c241225a8ade2b6b9f06ebb891ee459e3b02tomee _mp_move(&v3, &u3);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(&r, &v3);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl
9512fe850e98fdd448c638ca63fdd92a8a510255ahl mp_mult(&q, &v2, &t);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl mp_msub(&u2, &t, &t);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(&v2, &u2);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(&t, &v2);
9512fe850e98fdd448c638ca63fdd92a8a510255ahl }
9512fe850e98fdd448c638ca63fdd92a8a510255ahl /* now x0*u1 + x1*u2 == 1, therefore, (u2*x1) % x0 == 1 */
9512fe850e98fdd448c638ca63fdd92a8a510255ahl _mp_move(&u2, c);
if (mp_mcmp(c, &zero) < 0) {
mp_madd(&x0_prime, c, c);
}
_mp_xfree(&zero);
_mp_xfree(&v2);
_mp_xfree(&v3);
_mp_xfree(&u2);
_mp_xfree(&u3);
_mp_xfree(&q);
_mp_xfree(&r);
_mp_xfree(&t);
}