/
FREINV.c,v
73 lines (57 loc) · 1.29 KB
/
FREINV.c,v
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
head 1.1;
access;
symbols;
locks
saclib:1.1; strict;
comment @ * @;
1.1
date 95.08.16.22.32.29; author Mark; state new;
branches;
next ;
desc
@Finite ring element inverse.
@
1.1
log
@Initial revision
@
text
@/*==========================================================================
B <- FREINV(p,M,A)
Finite ring element inverse.
Input
p : a medium prime.
M : in Z/(p)[x], deg(M) > 0. M is in array representation.
A : in Z/(p)[x]/(M). A is in array representation.
Output
B : in Z/(p)[x]. If A is invertible in Z/(p)[x]/(M), then B = A^(-1).
Otherwise, deg(B) = -1.
==========================================================================*/
#include "saclib.h"
Word *FREINV(p,M,A)
Word p,*M,*A;
{
Word *B,r,rp;
Step1: /* Get array for B. */
B = MAPGET(MAPDEG(M)-1);
Step2: /* deg(A) == 0. */
if (MAPDEG(A) == 0) {
if (MAPZERO(A))
MAPDEG(B) = -1;
else {
MAPDEG(B) = 0;
MAPLDCF(B) = MDINV(p,MAPLDCF(A)); }
goto Return; }
Step3: /* Compute resultant and cofactor. */
MMAPRC(p,M,A,B,&r);
Step4: /* r = 0 ? */
if (r == 0) {
MAPDEG(B) = -1;
goto Return; }
Step5: /* Divide cofactor by resultant. */
rp = MDINV(p,r);
MMAPMDP(p,rp,B,B);
Return: /* Prepare for return. */
return(B);
}
@