119819Sdist /* 219819Sdist * Copyright (c) 1980 Regents of the University of California. 319819Sdist * All rights reserved. The Berkeley software License Agreement 419819Sdist * specifies the terms and conditions for redistribution. 519819Sdist */ 69944Ssam 719819Sdist #ifndef lint 8*26858Sdonn static char sccsid[] = "@(#)gcd.c 5.2 (Berkeley) 03/13/86"; 919819Sdist #endif not lint 1019819Sdist 119944Ssam #include <mp.h> 129944Ssam gcd(a,b,c) MINT *a,*b,*c; 139944Ssam { MINT x,y,z,w; 149944Ssam x.len=y.len=z.len=w.len=0; 159944Ssam move(a,&x); 169944Ssam move(b,&y); 179944Ssam while(y.len!=0) 189944Ssam { mdiv(&x,&y,&w,&z); 199944Ssam move(&y,&x); 209944Ssam move(&z,&y); 219944Ssam } 229944Ssam move(&x,c); 239944Ssam xfree(&x); 249944Ssam xfree(&y); 259944Ssam xfree(&z); 269944Ssam xfree(&w); 279944Ssam return; 289944Ssam } 299944Ssam invert(a, b, c) MINT *a, *b, *c; 309944Ssam { MINT x, y, z, w, Anew, Aold; 319944Ssam int i = 0; 329944Ssam x.len = y.len = z.len = w.len = Aold.len = 0; 339944Ssam Anew.len = 1; 34*26858Sdonn Anew.val = xalloc(1, "invert"); 359944Ssam *Anew.val = 1; 369944Ssam move(b, &x); 379944Ssam move(a, &y); 389944Ssam while(y.len != 0) 399944Ssam { mdiv(&x, &y, &w, &z); 409944Ssam move(&Anew, &x); 419944Ssam mult(&w, &Anew, &Anew); 429944Ssam madd(&Anew, &Aold, &Anew); 439944Ssam move(&x, &Aold); 449944Ssam move(&y, &x); 459944Ssam move(&z, &y); 469944Ssam i++; 479944Ssam } 489944Ssam move(&Aold, c); 499944Ssam if( (i&01) == 0) msub(b, c, c); 509944Ssam xfree(&x); 519944Ssam xfree(&y); 529944Ssam xfree(&z); 539944Ssam xfree(&w); 549944Ssam xfree(&Aold); 559944Ssam xfree(&Anew); 569944Ssam } 57