/
MUPFAC.c,v
65 lines (51 loc) · 1.17 KB
/
MUPFAC.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
head 1.1;
access;
symbols;
locks
saclib:1.1; strict;
comment @ * @;
1.1
date 95.09.05.13.30.07; author Mark; state new;
branches;
next ;
desc
@Modular univariate polynomial factorization.
@
1.1
log
@Initial revision
@
text
@/*===========================================================================
F <- MUPFAC(p,A)
Modular univariate polynomial factorization.
Inputs
p : a medium prime.
A : in Z/(p)[x]. A is squarefree and deg(A) >= 2.
Output
F : a list of the distinct monic irreducible factors of A.
===========================================================================*/
#include "saclib.h"
Word MUPFAC(p,A)
Word p,A;
{
Word Ap,B1,F,G,G1,b,d,f;
Step1: /* Make monic. */
Ap = MPMON(1,p,A);
Step2: /* Distinct-degree factorization. */
G = MMPDDF(p,Ap);
Step3: /* Split equal-degree factors. */
F = NIL;
while (G != NIL) {
ADV(G,&G1,&G);
ADV2(G1,&f,&b,&G1);
d = PDEG(b);
if (d > f) { /* split equal degree factors */
B1 = MMPFBL(p,b,f);
F = CONC(B1,F); }
else
F = COMP(b,F); }
Return: /* Prepare for return. */
return(F);
}
@