;;; -*-  Mode: Lisp; Package: Maxima; Syntax: Common-Lisp; Base: 10 -*- ;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;     The data in this file contains enhancments.                    ;;;;;
;;;                                                                    ;;;;;
;;;  Copyright (c) 1984,1987 by William Schelter,University of Texas   ;;;;;
;;;     All rights reserved                                            ;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;     (c) Copyright 1981 Massachusetts Institute of Technology         ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(in-package "MAXIMA")
(macsyma-module factor)

;;; This is the FACTOR package. 

;;;      THIS IS THE NEW FACTORING PACKAGE. THE FUNCTION
;;;	 FACTOR72 TAKES A PRIMITIVE SQUARE-FREE POLY AS INPUT THE OUTPUT IS A
;;;	 LIST OF FACTORS THE FUNCTION FACTOR1972 IS ABOVE FACTOR72 AND IT
;;;	 TAKES CARE OF REPEATED FACTORS OVER THE GAUSSIAN INTEGERS BEFORE
;;;	 CALLING FACTOR72 THE FUNCTION Z1 TAKES TWO FACTORS IN ONE VARIABLE
;;;	 AND ONE POLY IN SEVERAL VARIABLES AS INPUT Z1 TAKES THESE FACTORS IN
;;;	 ONE VARIABLES AND BUILDS OUT OF THEM TWO FACTORS OF THE GIVEN POLY IN
;;;	 SEVERAL VARIABLES

(LOAD-MACSYMA-MACROS RATMAC)

(DECLARE-TOP(*LEXPR $FACTOR)
	 (SPECIAL *STOP* TRL* *XN SHARPCONT SUBVAR1 ANOTYPE INVC FCTC
		  SUBVAL1 VAR MCFLAG ALCINV *AB* MONIC* INTBS*
		  *PRIME *G* MODULU* NEGFLAG PLIM LISTELM MANY* *INL3
		  *SHARPA *SHARPB LIMK SPLIT* ALC IND P L DOSIMP *ODR*
		  *I* MCFLAG ELM NE RES FACT1 FACT2 SUBVAR
		 SUBVAL OVARLIST VALIST DLP NN* DF1 DF2 DN* FCS* UU*)
	 (GENPREFIX FCT)
	 (FIXNUM #-cl (LOG2))) 

(declare-top(special afixn fctcfixn invcfixn))
(defmacro afixn (row col) `(arraycall fixnum afixn ,row ,col))
(defmacro fctcfixn (ind) `(arraycall fixnum fctcfixn ,ind))
(defmacro invcfixn (ind) `(arraycall fixnum invcfixn ,ind))

;; Internal specials

(DEFMVAR GAUSS NIL)
(DEFMVAR *MIN* NIL)
(DEFMVAR *MX* NIL)
(DEFMVAR MINPOLY* NIL)
(DEFMVAR MPLC* NIL)
(DEFMVAR MM* 1)
(DEFMVAR ALPHA NIL)
(DEFMVAR SMALLPRIMES '(3 5 7 11. 13. 17. 19. 23. 29. 31. 37.
			 41. 43. 47. 53. 59. 61.))

;; External specials

(DEFMVAR $NALGFAC T "If t use bmt's algebraic factoring algorithm")
(DEFMVAR $NEWFAC NIL)

(DEFUN CSQFRP ($FACTORFLAG)
  (NULL (zl-DELETE 1 (ODDELM (CDR (CFACTOR $FACTORFLAG))))))

(DEFUN PRIMCYCLO (N &AUX *G* (NL (CFACTORW N)))
  (SETQ NL (SLOOP FOR (C E) ON NL BY 'CDDR
		 NCONC (*MAKE-LIST E C)))
  (let ((res (CYCLOTOMIC (LIST N NL))))
    (cond ((consp res) (p-terms res))
	  ((eql 0 res) nil)
	  (t (list 0 res)))))

(DEFUN FACTXN+-1 (P) 
       (LET ((*G* (CAR P))
	     ($FACTORFLAG T)) 
	    (COND ((EQUAL 1 (CADR P)) (LIST P))
		  ((EQUAL (CDDR P) '(1 0 1))
		   (FACTXN+1 (CADR P))) 
		  ((EQUAL (CDDR P) '(1 0 -1))
		   (FACTXN-1 (CADR P)))))) 

(DEFMFUN CFACTORW (N) (LET (($FACTORFLAG T)) (CFACTOR N)))

(DEFUN FACTXN-1 (N)
       (COND ((EVENP N)
	      (APPEND (FACTXN-1 (// N 2)) (FACTXN+1 (// N 2))))
	     (T (MAPCAR #'CYCLOTOMIC (DIVISORS (CFACTOR N)))))) 

(defun factxn+1 (n)
  (cond (gauss
	 (let* ((gauss nil) (facl (factxn+1 n)))
	   (cond ((oddp n) facl)
		 (t (let (($gcd '$subres)
			  (pfac (list *g* (// n 2) 1 0 alpha)))
		      (mapcan #'(lambda (q) (firstn 2 (pgcdcofacts q pfac)))
			      facl))))))
	(t (let ((m 1) (nl (reverse (cfactor n))))
	     (when (equal 2 (cadr nl))
		   (setq m (expt 2 (car nl)))
		   (setq nl (cddr nl)))
	     (setq m (list *g* m -1))
	     (if (null nl) (ncons (list *g* n 1 0 1))
		 (mapcar #'(lambda (p) (pabs (pcsubst p m (car p))))
			 (mapcar #'cyclotomic (divisors (reverse nl)))))))))


(DEFUN CYCLP (N IND)
  (SLOOP FOR I downFROM (f1- N) TO 0
	NCONC (LIST (f* IND I) 1)))

(DEFUN CSF (L) 
       (COND ((NULL L) NIL) (T (LIST* (CAR L) 1 (CSF (CDR L))))))

(DEFUN CONDENSE (L) 
       (COND ((NULL (CDR L)) L)
	     ((EQ (CAR L) (CADR L)) (CONDENSE (CDR L)))
	     (T (CONS (CAR L) (CONDENSE (CDR L)))))) 

(DEFUN CYCLOTOMIC (NL) 
  (PROG (N DP DPL NUM DEN P) 
	(COND ((EQUAL 1 (CAR NL)) (RETURN (LIST *G* 1 1 0 -1)))
	      ((NULL (CDR (SETQ P (CONDENSE (CADR NL)))))
	       (RETURN (CONS *G*
			     (CYCLP (CAR P)
				    (EXPT (CAR P) (f1- (LENGTH (CADR NL)))))))))
	(SETQ NUM 1 DEN 1 N (CAR NL) DPL (DIVISORS (CSF P)))
   LOOP (COND ((NULL DPL) (RETURN (PQUOTIENT NUM DEN))))
	(SETQ DP (CAR DPL))
	(SETQ DPL (CDR DPL))
	(SETQ P (LIST *G* (QUOTIENT N (CAR DP)) 1 0 -1))
	(COND ((OR (EVENP (LENGTH (CADR DP))) (EQUAL (CAR DP) 1))
	       (SETQ NUM (PTIMES P NUM)))
	      (T (SETQ DEN (PTIMES P DEN))))
	(GO LOOP))) 

(DEFUN DIVISORS (L)
  (if (equal l '(1 1)) (setq l nil))
  (do ((ans (LIST '(1 ()) ))
       (l l (cddr l)))
      ((null l) ans)
    (do ((u ans)
	 (factor (car l))
	 (mult (cadr l) (f1- mult)))
	((zerop mult))
      (SETQ U (MAPCAR #'(LAMBDA (Q) (LIST (TIMES factor (CAR Q))
					  (CONS factor (CADR Q))))
		      U))
      (SETQ ANS (NCONC ANS U)))))


(DEFUN ESTCHECK2 (D LC C) 
       (PROG (P) 
	LOOP (COND ((NULL D) (RETURN NIL)))
	     (SETQ P (CAR D) D (CDR D))
	     (COND ((OR (AND (NOT (EQUAL (REMAINDER C P) 0))
			     (NOT (EQUAL (REMAINDER LC (TIMES P P)) 0)))
			(AND (NOT (EQUAL (REMAINDER LC P) 0))
			     (NOT (EQUAL (REMAINDER C (TIMES P P)) 0))))
		    (RETURN T)))
	     (GO LOOP))) 

(DEFUN ESTCHECK (P) 
       (PROG (LC C D) 
	     (COND ((OR (ATOM P) (NULL (CDDR P)) (EQUAL (PTERM P 0) 0))
		    (RETURN NIL)))
	     (SETQ LC (CADR P))
	     (SETQ P (NREVERSE (CDR (ODDELM (CDR P)))))
	     (SETQ C (CAR P))
	     (SETQ D (CGCDLIST P))
	     (COND ((EQUAL 1 D) (RETURN NIL)))
	     (SETQ D (ODDELM (CFACTORW D)))
	     (RETURN (ESTCHECK2 D LC C)))) 


(DEFUN CGCDLIST (L) 
       (COND ((NULL L) NIL)
	     ((NULL (CDR L)) (ABS (CAR L)))
	     ((OR (zl-MEMBER 1 L) (zl-MEMBER -1 L)) 1)
	     ((NULL (CDDR L)) (GCD (CAR L) (CADR L)))
	     (T (CGCDLIST (CONS (GCD (CAR L) (CADR L)) (CDDR L)))))) 

(DEFUN DROPTERMS (P) 
       (PROG (ANS C) 
	     (COND ((ATOM P) (RETURN P))
		   ((NOT (EQ (CAR P) VAR)) (RETURN (KTERMS P DLP))))
	     (SETQ ANS (CONS (CAR P) ANS) P (CDR P))
	LOOP (COND ((NULL P) (RETURN (COND ((CDR ANS) (NREVERSE ANS)) (T 0)))))
	     (SETQ C (KTERMS (CADR P) DLP))
	     (COND ((NOT (EQUAL C 0)) (SETQ ANS (CONS C (CONS (CAR P) ANS)))))
	     (SETQ P (CDDR P))
	     (GO LOOP))) 

 
(DEFUN RESTORELC (L LC) 
       (PROG (H R ANS VAR C D DEG) 
	     (COND ((EQUAL 1 LC)
		    (COND ((AND (NOT MANY*) ALGFAC* (NOT (EQUAL INTBS* 1)))
			   (RETURN (MAPCAR (FUNCTION INTBASEHK) L)))
			  (T (RETURN (REVERSE L))))))
	     (SETQ R (LCPRODL L) H 1)
	LOOP (COND ((NULL L) (RETURN ANS)))
	     (SETQ D (CAR L) L (CDR L) VAR (CAR D) DEG (CADR D) C (CADDR D))
	     (SETQ D (PTIMES (PTIMES H (CAR R)) (PSIMP VAR (CDDDR D))))
	     (COND (MANY* (SETQ D (DROPTERMS D))))
	     (SETQ D (PPLUS (LIST VAR DEG LC)D))
	     (COND ((AND (NOT MANY*) ALGFAC* (NOT (EQUAL INTBS* 1)))
		    (SETQ D (INTBASEHK D))))
	     (LET ((MODULUS))
		  (SETQ ANS (CONS (CADR (OLDCONTENT D)) ANS)))
	     (SETQ H (PTIMES H C) R (CDR R))
	     (GO LOOP))) 

(DEFUN IREDUP (P)
       (LET ((MM* 1) (ALGFAC*))
	    (COND ((SQFRP P(CAR P))
		   (SETQ P (CATCH 'SPLT (CPBER1 P)))
		   (AND (NULL (CAR P)) (NULL (CDADR P)))))))

(DEFUN ZEROLP (A) (ANDMAPC (FUNCTION ZEROP1) A))


(DEFMFUN TESTDIVIDE (X Y) 
  (LET ((ERRRJFFLAG T))
    (COND (ALGFAC* (ALGTESTD X Y))
	  ((OR (PCOEFP X)
	       (PCOEFP Y)
	       (CATCH 'RATERR (PQUOTIENT (CAR (LAST X)) (CAR (LAST Y)))))
	   (CATCH 'RATERR (PQUOTIENT X Y))))))

(DEFUN ALGTESTD (X Y)
  (AND (DIV-DEG-CHK (NREVERSE (PDEGREEVECTOR X)) (NREVERSE (PDEGREEVECTOR Y))
		    (REVERSE GENVAR))
       (COND ((SETQ X (CATCH 'RATERR (RQUOTIENT X Y)))
	      (SETQ ADN* (f* ADN* (CDR X)))
	      (CAR X)) )))

(DEFUN DIV-DEG-CHK (XL YL GL)
  (COND ((OR (NULL GL) (ALGV (CAR GL))) T)
	((> (CAR YL) (CAR XL)) NIL)
	(T (DIV-DEG-CHK (CDR XL) (CDR YL) (CDR GL)))))

; FUU is used by systems programmers such as BMT and PAULW while debugging.
(DEFUN FUU NIL 
       (SETQ TELLRATLIST NIL VARLIST NIL GENVAR NIL GENPAIRS NIL)) 

(DEFUN LINOUT (U) 
       (PROG (M LINFAC X Y) 
	     (SETQ Y (LIST (SETQ X (CAR U)) 1 1) M MODULUS)
	LOOP (SETQ M (f1- M))
	     (COND ((LESSP M 0) (RETURN (LIST U LINFAC)))
		   ((EQUAL (CADR U) 1) (RETURN (LIST 1 (CONS U LINFAC))))
		   ((ZEROP (PCSUBSTY (CMOD M) X U))
		    (SETQ LINFAC
			  (CONS (APPEND Y
					(COND ((ZEROP M) NIL)
					      (T (LIST 0 (CMOD (f- M))))))
				LINFAC))
		    (SETQ U (CAR (PMODQUO U (CAR LINFAC))))))
	     (GO LOOP))) 
 
(DEFUN ONEVARP (P) 
  (IF ALGFAC* (ANDMAPC #'PACOEFP (CDR P))
      (ANDMAPC #'NUMBERP (CDR P)))) 

(DEFUN PUTODR (L)
       (DO ((L L (CDR L))
	    (I 1 (f1+ I))
	    (ANS))
	   ((NULL L) ANS)
	   (PUSH (CONS (CAR L) I) ANS)))

(DEFUN KTERMS (P K) 
       (DECLARE (FIXNUM K))
       (COND ((PACOEFP P) P)
	     ((= K 0) (CONSTA P))
	     (T (PROG (V ANS W) 
		      (SETQ V (CAR P))
		      (SETQ P (CDR P))
		 LOOP (COND ((NULL P) (RETURN 0))
			    ((> (CAR P) K) (SETQ P (CDDR P)) (GO LOOP)))
		 AG   (COND ((NULL P)
			     (RETURN (PSIMP V ANS))))
		      (SETQ W (KTERMS (CADR P) (f- K  (CAR P))))
		      (COND ((NOT (PZEROP W))
			     (SETQ ANS (NCONC ANS (LIST (CAR P) W)))))
		      (SETQ P (CDDR P))
		      (GO AG))))) 

(DEFUN CONSTA (P)
       (COND ((OR (PCOEFP P) (ALG P)) P)
	     (T (CONSTA (PTERM (CDR P) 0)))))

(DEFUN CONSTACL (P)    ;NO LONGER USED?
       (COND ((ATOM P)
	      (COND ((EQUAL P 1) (THROW 'CNT 1))
		    (T (LIST P))))
	     ((ANDMAPC 'NUMBERP (CDR P))
	      (SETQ P (ODDELM P))
	      (COND ((zl-MEMBER 1 P) (THROW 'CNT 1))
		    (T (CDR P))))
	     (T (APPLY (FUNCTION APPEND)
		       (MAPCAR (FUNCTION CONSTACL) (CDR (ODDELM P)))))))

(DEFUN Z1 (POLY FACT1 FACT2) 
    #-cl 	  (DECLARE(FIXNUM STEPS STEP HSTEPS))
  (PROG (RES HSTEPS STEPS KTERM A B C D *AB* M DF1 DF2 DLR STEP *SHARPA *SHARPB)
	(LET ((MODULUS) (HMODULUS))
	     (SETQMODULUS *PRIME)
	     (SETQ *SHARPB (FACT20 FACT1 FACT2 LIMK)))
	(SETQ *SHARPA (CAR *SHARPB))
	(SETQ *SHARPB (CADR *SHARPB))
	(SETQ *AB* (LIST (LIST 0 *SHARPA *SHARPB)))
	(SETQ STEPS DLP 
	      HSTEPS (// STEPS 2))
	(SETQ RES (PDIFFERENCE (PTIMES (PMOD FACT1) (PMOD FACT2)) (PMOD POLY)))
	(SETQ POLY NIL)
	(SETQ STEP 0)
	(SETQ DF1 FACT1)
	(SETQ DF2 FACT2)
   LOOP (COND ((EQUAL RES 0) (GO OUT)))
	(SETQ STEP (f1+ STEP))
	(COND ((GREATERP STEP STEPS) (GO OUT)))
	(COND ((EQ (CAR RES) VAR) (SETQ C (CDR RES)))
	      (T (SETQ C (LIST 0 RES))))
	(SETQ A 0 B 0)
  NEXTM (COND ((NULL C) (Z2 A B STEP HSTEPS) (GO LOOP)))
	(SETQ M (CAR C) DLR (CADR C))
	(SETQ C (CDDR C))
	(SETQ KTERM (KTERMS DLR STEP) DLR NIL)
	(COND ((EQUAL 0 KTERM) (GO NEXTM)))
	(SETQ D (OBTAINABM M))
	(SETQ B (PPLUS B (PTIMES (CAR D) KTERM)) 
	      A (PPLUS A (PTIMES (CADR D) KTERM)) 
	      KTERM NIL)
	(GO NEXTM)
   OUT  (RETURN (LIST DF1 DF2)))) 

(DEFUN Z2 (A B STEP HSTEPS)
 (UNLESS (AND (EQUAL A 0) (EQUAL B 0))
	 (SETQ STEP
	       (PDIFFERENCE
		(PDIFFERENCE (COND ((NOT (LESSP STEP HSTEPS))
				    (DROPTERMS (PTIMES A B)))
				   (T (PTIMES A B)))
			     (COND ((NOT (LESSP STEP HSTEPS))
				    (DROPTERMS (PTIMES DF1 B)))
				   (T (PTIMES DF1 B))))
		(COND ((NOT (LESSP STEP HSTEPS))
		       (DROPTERMS (PTIMES DF2 A)))
		      (T (PTIMES DF2 A)))))
	 (SETQ RES (PPLUS RES STEP))
	 (SETQ DF1 (PDIFFERENCE DF1 A))
	 (SETQ DF2 (PDIFFERENCE DF2 B))))

(DEFUN OBTAINABM (M) 
       (PROG (ANS) 
	     (COND ((SETQ ANS (CDR (zl-ASSOC M *AB*))) (RETURN ANS)))
	     (SETQ ANS (OBTAINAB (LIST VAR M 1)))
	     (SETQ *AB* (CONS (CONS M ANS) *AB*))
	     (RETURN ANS))) 

(DEFUN FACT20 (F1 G1 LIMK) 
       (PROG (F G A PK B REML QLP H K B1) 
	     (SETQ K 0)
	     (SETQ REML (PPPROG (PMOD F1) (PMOD G1)))
	     (SETQ A (CAR REML))
	     (SETQ B (CADR REML))
	SHARP   (COND ((GREATERP K LIMK) (RETURN (LIST A B))))
	     (SETQ PK MODULUS)
	     (SETQMODULUS (TIMES MODULUS MODULUS))
	     (SETQ F(PMOD F1) G (PMOD G1))
	     (SETQ H (PQUO (PMOD (PDIFFERENCE (PPLUS (PTIMES A F) (PTIMES B G))
					      1))
			   PK))
	     (SETQ QLP (PMODQUO (PTIMES A H) G))
	     (SETQ B1 (PPLUS (PTIMES B H) (PTIMES (CAR QLP) F)))
	     (SETQ A (PDIFFERENCE A (PMOD (PCTIMES PK (CDR QLP)))))
	     (SETQ B (PDIFFERENCE B (PMOD (PCTIMES PK B1))))
	     (SETQ K (f1+ K))
	     (GO SHARP))) 

 

(DEFUN BASELIST (N) (SETQ *I* N) (COMPLETEVECTOR NIL 0 N ELM)) 

(DEFUN INLIST3 (L) 
       (COND ((NULL L) (SETQ *INL3 NIL))
	     ((ZEROP (CAR L)) (CONS 1 (CDR L)))
	     ((EQUAL (CAR L) 1) (CONS -1 (CDR L)))
	     (T (CONS 0 (INLIST3 (CDR L)))))) 

(DEFUN NEWREP (P) 
       (LET ((MODULUS))
	    (IF SUBVAR (PCSUBSTY (MAPCAR #'(LAMBDA (A B) (LIST A 1 1 0 B))
					 SUBVAR SUBVAL)
				 SUBVAR
				 P)
		P)))

(DEFUN OLDREP (P) 
   (LET ((MODULUS))
	(IF SUBVAR (PCSUBSTY (MAPCAR #'(LAMBDA (A B) (LIST A 1 1 0 (MINUS B)))
				     SUBVAR SUBVAL)
			     SUBVAR
			     P)
	    P)))

(DEFUN COMPLETEVECTOR (L N M V)
       (DO ((I M (f1- I)))
	   ((= I N) L)
	   (PUSH V L))) 

(DEFUN DEGVECTOR (L N C) 
       (PROG (LF ANS J) 
	     BK (COND ((NUMBERP C)
		    (RETURN  (LIST (COMPLETEVECTOR L N NN* 0)))))
	     (SETQ J (CDR (zl-ASSOC (CAR C) *ODR*)))
	     ;;; IN CASE (CAR C) IS ALGEBRAIC
             (COND ((NULL J) (SETQ C 0)(GO BK)))	
	     (SETQ C (CDR C))
	     (SETQ LF (COMPLETEVECTOR L N J 0))
	LOOP (COND ((NULL C) (RETURN ANS)))
	     (SETQ ANS
		   (NCONC (DEGVECTOR (CONS (CAR C) LF) (f1+ J) (CADR C)) ANS))
	     (COND (*MX* (SETQ ANS (NCONS (MAXLIST ANS))))
		   (*MIN* (SETQ ANS (NCONS (MINLIST ANS)))))
             (SETQ C (CDDR C))
             (GO LOOP)))

(DEFUN UNION1 (A B)
       (DO ((A A (CDR A))
	    (ANS B))
	   ((NULL A) ANS)
	   (OR (zl-MEMBER (CAR A) ANS)
	       (SETQ ANS (CONS (CAR A) ANS)))))

(DEFUN OBTAINAB (U) 
       (PROG (C QL)
	     (SETQ C (PMOD U))
	     (SETQ QL (PMODQUO (PTIMES *SHARPA C) FACT2))
	     (RETURN (LIST (CDR QL) (PMOD (PPLUS (PTIMES (CAR QL) FACT1)
						 (PTIMES *SHARPB C)))))))

 

(DEFUN PCDIFCONC (V J)
       (DO ((L V (CDDR L)))
	   ((NULL (CDR L))
	    (OR (= J 0)
		(RPLACD L (LIST 0 J)))
	    V)
	   (COND ((= (CADR L) 0)
		  (COND ((= J 0)
			 (RPLACD L NIL))
			((RPLACA (CDDR L) J)))
		  (RETURN V))))) 

(DEFUN ORDE (A L) 
       (COND ((NULL L) (LIST A))
	     (T (COND ((LESSP A (CAR L)) (CONS A L))
		      (T (CONS (CAR L) (ORDE A (CDR L)))))))) 

(DEFUN PQUO (X Y) (LET (MODULUS) (PQUOTIENT X Y))) 

(DEFUN INTERSECT (X Y) 
  (IF X (IF (zl-MEMBER (CAR X) Y) (CONS (CAR X) (INTERSECT (CDR X) Y))
			       (INTERSECT (CDR X) Y))))

;; Like APL IOTA function.
(DEFUN INDEX* (K) 
  (DECLARE (FIXNUM K))
  (IF (< K 2) (LIST 1) (CONS K (INDEX* (f1- K)))))

 
(DEFUN KLIM (U P1) 
       (PROG (BCOEF) 
	     (SETQ BCOEF (MAXCOEFFICIENT U))
	     (SETQ BCOEF (TIMES 5 BCOEF))
	     (COND (ALGFAC* (SETQ BCOEF (TIMES BCOEF INTBS*))))
 	     (COND ((LESSP BCOEF 10000.) (SETQ BCOEF 20000.)))
	     (SETQ LIMK 0)
	TEST (SETQ P1 (TIMES P1 P1))
	     (COND ((GREATERP P1 BCOEF)
		    (SETQ PLIM P1)
		    (RETURN LIMK)))
	     (SETQ LIMK (f1+ LIMK))
	     (GO TEST))) 

(DECLARE-TOP(SPECIAL B B2)) 

(DEFUN CPBERL (U) 
       (PROG (QL D) 
	     (SETQ QL (CATCH 'SPLT (CPBER1 U)) U (CADDR QL))
	     (SETQ D (CAR QL) QL (CADR QL))
	     (COND ((NULL QL)(RETURN D))
		   ((NULL (CDR QL)) (RETURN (CONS U D))))
	     (RETURN (APPEND D 
			     (COND ((OR ALPHA (GREATERP MODULUS 70.))
				    (CPBGZASS QL (PMOD U) (LENGTH QL)))
				   (T (CPBG QL (PMOD U) (LENGTH QL))))))))

;; Returns a list of monomials in G of degree less than N.
(DEFUN POWRS (G N &AUX (ANS (NCONS 1)))
  (DECLARE (FIXNUM N))
  (DO ((I 1 (f1+ I))) ((= I N) ANS)
    (DECLARE (FIXNUM I))
    (PUSH (MAKE-POLY G I 1) ANS)))
 

;; Finds polynomials A and B such that A*F+B*G=1 when MODULUS
;; is non-NIL.  Same algorithm as INVMOD.
(DEFUN PPPROG (F G) 
  (PROG (A1 A2 B1 B2 R1 R2 QL ANS AP BP G1 F1 S) 
	(COND ((GREATERP (CADR G) (CADR F)) (SETQ G1 G) (SETQ F1 F))
	      (T (SETQ G1 F) (SETQ F1 G) (SETQ S T)))
	(SETQ QL (PMODQUO G1 F1))
	(SETQ A1 1)
	(SETQ B1 0)
	(SETQ A2 (PMINUS (CAR QL)))
	(SETQ B2 1)
	(SETQ R1 F1)
	(SETQ R2 (CDR QL))
   TEST (COND ((OR (NUMBERP R2) (AND ALPHA (ALG R2))) (GO END)))
	(SETQ QL (PMODQUO R1 R2))
	(SETQ AP (PDIFFERENCE A1 (PTIMES (CAR QL) A2)))
	(SETQ BP (PDIFFERENCE B1 (PTIMES (CAR QL) B2)))
	(SETQ R1 R2)
	(SETQ R2 (CDR QL))
	(SETQ A1 A2)
	(SETQ B1 B2)
	(SETQ A2 AP)
	(SETQ B2 BP)
	(GO TEST)
   END  (COND ((PZEROP R2)
	       (COND ((EQUAL 1 (SETQ ANS (CADDR R1)))
		      (SETQ ANS (LIST B1 A1)))
		     (T (SETQ ANS (LIST (CAR (PMODQUO B1 ANS))
					(CAR (PMODQUO A1 ANS))))))
	       (GO OUT)))
        (SETQ ANS (LIST (CAR (PMODQUO B2 R2)) (CAR (PMODQUO A2 R2))))
   OUT  (COND ((NOT S) (RETURN (REVERSE ANS))) (T (RETURN ANS))))) 


(DEFUN ZFF (V F G) (COND (MANY* (Z1 V F G)) (T (FACT2Z V F G LIMK)))) 

(DEFUN ZFACT (U FL LIMK MANY*) 
  (PROG (FCS* PRODL) 
	(COND (MANY* (SETQMODULUS PLIM)
		     (SETQ DLP
			   (EVAL (CONS 'MAX
				       (MAPCAR (FUNCTION MULTIDEG)
					       (CDR (ODDELM U))))))))
	(COND ((EQUAL (LENGTH FL) 1) (RETURN (LIST U))))
	(SETQ PRODL (FSPLIT FL 'V))
	(ZFACTSPLIT PRODL U)
	(RETURN FCS*))) 

(DEFUN ZFACTSPLIT (FL V) 
  (PROG (D) 
	(COND ((NULL (CDR FL)) (RETURN (SETQ FCS* (CONS V FCS*))))
	      ((NULL (CDDR FL))
	       (SETQ FL (CADR FL))
	       (RETURN (SETQ FCS* (NCONC (ZFF V (CAR FL) (CADR FL)) FCS*))))
	      (T (SETQ FL (CDR FL))
		 (SETQ D (ZFF V (CAAR FL) (CAADR FL)))
		 (SETQ V NIL)
		 (ZFACTSPLIT (CAR FL) (CAR D))
		 (RETURN (ZFACTSPLIT (CADR FL) (CADR D))))))) 

(DEFUN SPLIT2 (L) 
       (PROG (S N) 
	     (SETQ N (QUOTIENT (LENGTH L) 2))
	     (SETQ S (NCDR L N))
	     (SETQ DN* (COPY1 (CDR S)))
	     (RPLACD S NIL)
	     (SETQ NN* L))) 

(DEFUN FSPLIT (L IND) 
       (PROG (NN* DN*) 
	     (COND ((NULL (CDR L)) (RETURN L))
		   ((NULL (CDDR L))
		    (RETURN (LIST (APPLY (FUNCTION PTIMES) L) L))))
	     (SPLIT2 L)
	     (SETQ NN* (FSPLIT NN* NIL))
	     (SETQ DN* (FSPLIT DN* NIL))
	     (RETURN (LIST (COND (IND IND) (T (PTIMES (CAR NN*) (CAR DN*))))
			   NN*
			   DN*)))) 

;Definition is identical to HAULONG.
;(DEFUN BOUNDFUN (N) (f1+ (LOG2 N))) 

(COMMENT THIS PAGE CONTAINS ROUTINES CHANGED FOR NON-MONIC HACK)

(DEFUN PEXPTMOD (P N Q) 
       (PROG (U X) 
	     (COND ((PCOEFP P) (RETURN (CEXPT P N))))
	     (SETQ Q (CDR Q) X (CAR P))
	     (COND   ((ODDP N) (SETQ P(SETQ U (PGCD1 (CDR P) Q)))(GO B))
		   (T (SETQ U '(0 1))))
	     (SETQ P (CDR P))
	A    (SETQ P (PGCD1 P Q))
	B    (SETQ N (QUOTIENT N 2))
	     (COND ((EQUAL 0 N) (RETURN (CONS X U))))
	     (SETQ P (PTIMES1 P P))
	     (COND ((ODDP N) (SETQ U (PGCD1 (PTIMES1 U P) Q))))
	     (GO A)))

(DEFUN SQFRP (U VAR) 
       (COND ((AND (EQUAL 0 (PTERM (CDR U) 0)) (EQUAL 0 (PTERM (CDR U) 1)))
	      NIL)
	     ((ONEVARP U)
	      (SETQ U (PGCD U (PDERIVATIVE U VAR)))
	      (OR (NUMBERP U) (ALG U)))
	     (T (QUICK-SQFR-CHECK U VAR)))) 

(DEFUN LOGTWO (X) 
       (PROG (ANS) 
	     (COND ((EQUAL X 0) (RETURN 0)) ((EQUAL X 1) (RETURN 1)))
	     (SETQ ANS (LOG2 X))
	     (COND ((GREATERP X (EXPT 2 ANS)) (RETURN (f1+ ANS)))
		   (T (RETURN ANS))))) 

(DECLARE-TOP(SPECIAL P)) 

(DEFUN FIXVL0 (L1 L2 OV) 
       (PROG (A B C) 
	LOOP (COND ((NULL OV) (SETQ SUBVAR A SUBVAL B VALIST C) (RETURN NIL))
		   ((MEMQ (CAR OV) L1)
		    (SETQ A (CONS (CAR OV) A) 
			  B (CONS (ASSSO (CAR OV) L1 L2) B) 
			  C (CONS (CAR B) C)))
		   (T (SETQ C (CONS 0 C))))
	     (SETQ OV (CDR OV))
	     (GO LOOP))) 

(DEFUN ASSSO (A L1 L2) 
       (PROG NIL 
	LOOP (COND ((NULL L1) (RETURN NIL)) ((EQ (CAR L1) A) (RETURN (CAR L2))))
	     (SETQ L1 (CDR L1) L2 (CDR L2))
	     (GO LOOP))) 

(DEFUN ZEROHK (L) 
       (PROG (ANS I) 
	     (COND ((NULL L) (RETURN NIL)))
	AG   (SETQ ANS (CAR L) I (ZEROSHARP ANS))
	LOOP (SETQ L (CDR L))
	     (COND ((NULL L) (RETURN ANS))
		   ((GREATERP (ZEROSHARP (CAR L)) I) (GO AG)))
	     (GO LOOP))) 


(DEFUN MULTFACT (POLY) 
       (PROG (*INL3 *I* *MIN* *MX* NN* *ODR* LC ELM LISTELM PLIM ORIGENVAR NE VAR VALIST VAL1
	      OVARLIST P SUBVAR SUBVAR1 SUBVAL1 SUBVAL DLP)
;	     (declare (special p))
	     (SETQ VAR (CAR POLY) ELM (LISTOVARS POLY) 
		   ORIGENVAR GENVAR 
		   GENVAR (INTERSECT GENVAR (COND (ALGFAC* (zl-DELETE (CAR ALPHA) ELM))(T ELM))) 
		   OVARLIST (REVERSE (CDR (REVERSE GENVAR))) 
		   NN* (f1+ (LENGTH OVARLIST)))
	     (SETQ LISTELM 0)
	     (SETQ LC (CADDR POLY))
	     (SETQ ELM 1 *I* 1 NE 1)
	     (SETQ SUBVAL (REVERSE POLY))
	     (SETQ *ODR*(PUTODR (REVERSE OVARLIST)))
	     (SETQ VAL1
		   (ZEROHK (NCONC (DEGVECTOR NIL 1 LC)
				  (COND ((OR (GREATERP (CADR SUBVAL) 0)
					     (GREATERP (CADDDR SUBVAL) 1))
					 (DEGVECTOR NIL 1 (CAR SUBVAL)))))))
	     (SETQ SUBVAL NIL)
	     (SETQ P POLY)
	     (COND ((NULL VAL1)
		    (SETQ SUBVAR1 OVARLIST)
		    (SETQ SUBVAL1 (POLYSUBST (NZEROS (LENGTH SUBVAR1) NIL)
					     SUBVAR1))
		    (GO TAG)))
	     (FIXVL VAL1 OVARLIST)
	     (FIXVL1 VAL1 OVARLIST)
	     (COND (SUBVAL1 (SETQ SUBVAL1 (POLYSUBST SUBVAL1 SUBVAR1))))
	     (SETQ SUBVAL
		   (POLYSUBST (COMPLETEVECTOR NIL 0 (LENGTH SUBVAL) 1)
			      SUBVAR))
	TAG  (FIXVL SUBVAL1 SUBVAR1)
	     (SETQ SUBVAL1 NIL SUBVAR1 NIL)
	     (FIXVL0 SUBVAR SUBVAL (REVERSE OVARLIST))
	     (COND (ALGFAC* (SETQ GENVAR (CONS (CAR ALPHA) GENVAR))))
	     (SETQ POLY (CPBER3 POLY P))
	     (SETQ GENVAR ORIGENVAR)
	     (RETURN POLY))) 

(DEFUN POLYSUBST (A B)
;  (declare (special p))
       (PROG (LC *INL3 D N MODULUS) 
	     (COND (MODULU* (SETQ MODULUS MODULU*)))
	     (SETQ *INL3 T LC (CADDR P) N (LENGTH A))
	LOOP (SETQ D (PCSUBSTY A B LC))
	     (COND ((EQUAL 0 D) (GO INL)))
	     ((LAMBDA (MODULUS) (SETQ D (PCSUBSTY A B P))) NIL)
	     (COND ((SQFRP (PMOD D) (CAR D)) (SETQ P D) (RETURN A)))
	INL  (SETQ A (INCREASELIST A N))
	     (GO LOOP))) 

(DECLARE-TOP (UNSPECIAL P)) 

(DEFUN ZEROSHARP (L)
       (DO ((N 0) (L L (CDR L)))
	   ((NULL L) N)
	   (IF (ZEROP (CAR L)) (SETQ N (f1+ N))))) 

(DEFUN FIXVL1 (L R) 
       (PROG NIL 
	LOOP (COND ((NULL L)
		    (SETQ SUBVAL1 (NREVERSE SUBVAL1) SUBVAR1 (NREVERSE SUBVAR1))
		    (RETURN NIL))
		   ((ZEROP (CAR L))
		    (SETQ SUBVAL1 (CONS (CAR L) SUBVAL1))
		    (SETQ SUBVAR1 (CONS (CAR R) SUBVAR1))))
	     (SETQ L (CDR L))
	     (SETQ R (CDR R))
	     (GO LOOP))) 

(DEFUN FIXVL (L R) 
       (PROG NIL 
	LOOP (COND ((NULL L)
		    (SETQ SUBVAL (NREVERSE SUBVAL) SUBVAR (NREVERSE SUBVAR))
		    (RETURN NIL))
		   ((NOT (ZEROP (CAR L)))
		    (SETQ SUBVAL (CONS (CAR L) SUBVAL))
		    (SETQ SUBVAR (CONS (CAR R) SUBVAR))))
	     (SETQ L (CDR L))
	     (SETQ R (CDR R))
	     (GO LOOP))) 

(DEFUN LOGN (ARG N) 
       (COND ((GREATERP ARG N) (f1+ (LOGN (QUOTIENT ARG N) N))) (T 0))) 

(DEFUN MAXCOEF (P) (MAXCOEFFICIENT P)) 

(DEFUN INCRLIMK (P) 
       (PROG (V) 
	     (COND (MODULU* (SETQ PLIM MODULU* *PRIME MODULU* LIMK -1) (RETURN NIL))
		   ((NULL LIMK)(SETQ PLIM *ALPHA *PRIME *ALPHA LIMK -1)(RETURN NIL)))
	     (SETQ V (NREVERSE (CDR (REVERSE (PDEGREEVECTOR P)))))
	     (SETQ V
		   (APPLY
		    '*
		    (MAPCAR 
		(FUNCTION
		 (LAMBDA (A B) 
			 (COND ((EQUAL B 0) 1)
			       (T (MAX (TIMES (SIMPBINOCOEF (LIST '(%BINOCOEF)
								  A
								  (QUOTIENT A
									    2))
							    1
							    T)
					      (EXPT B (QUOTIENT A 2)))
				       (EXPT B A))))))
		V
		VALIST)))
	     (SETQ V(MAX 0 (f1- (LOGTWO (LOGN (TIMES (MAX (MAXCOEF P) PLIM) V) PLIM)))))
	     (SETQ LIMK (f+ LIMK V))
	LOOP (COND ((< V 1) (RETURN NIL)))
	     (SETQ V (f1- V))
	     (SETQ PLIM (TIMES PLIM PLIM))
	     (GO LOOP))) 

 

(DEFUN INCREASELIST (L N) 
  (COND (*INL3 (SETQ L (INLIST3 L))))
  (COND (*INL3 L)
	(T (COND ((EQUAL ELM 2)
		  (COND (MODULU*
			 (MERROR "Not enough choices for substitution."))
			(T (RAND N 13.))))
		 ((EQUAL NE N)
		  (SETQ ELM (f1+ ELM))
		  (SETQ NE 1)
		  (COMPLETEVECTOR (BASELIST NE) NE N LISTELM))
		 (T (COND ((EQUAL *I* N)
			   (SETQ NE (f1+ NE))
			   (COMPLETEVECTOR (BASELIST NE) NE N LISTELM))
			  (T (SETQ *I* (f1+ *I*))
			     (REVERSE (CDR (REVERSE (CONS LISTELM
							  L))))))))))) 


;; Returns a list of N random numbers.  If MODULUS is set, then the
;; numbers will be modulo MODULUS.   Otherwise, between 0 and 1000.
(DEFUN RAND (N MODULUS)
  (declare (fixnum n))
  (DO ((I N (f1- I)) (L))
      ((= I 0) (COND (MODULUS (MAPCAR #'CMOD L))
		     (T L)))
      (DECLARE (FIXNUM I))
    (PUSH (RANDOM 1000.) L)))

(DEFUN TRUFAC (V LP OLFACT MANY* MODULUS) 
       (PROG (ANS OLC LC AF QNT FACTOR LFUNCT HMODULUS) 
	     (SETQ LC 1 OLC 1)
	     (SETQMODULUS MODULUS)
	     (SETQ LFUNCT (SETQ OLFACT (CONS NIL OLFACT)))
	TEST (COND
	      ((EQUAL V 1) (SETQ ANS FACTOR) (GO OUT))
	      ((NULL LP)
	       (SETQ 
		ANS
		(COND ((LESSP (LENGTH OLFACT) 4) (CONS V FACTOR))
		      (T (NCONC FACTOR
				(NPROD LC
				       V
				       (CONS ((LAMBDA (MODULUS) 
						      (PTIMES OLC
							      (CADR OLFACT)))
					      PLIM)
					     (CDDR OLFACT)))))))
	       (GO OUT))
	      ((AND (NULL (CDR LP)) (OR (NULL (CDR OLFACT)) (NULL (CDDR OLFACT))))
	       (SETQ ANS (CONS V FACTOR))
	       (GO OUT)))
	     (SETQ AF (CAR LP))
	     (COND ((SETQ QNT ((LAMBDA (MODULUS) (TESTDIVIDE V AF)) MODULU*))
		    (SETQ FACTOR (CONS AF FACTOR))
		    (SETQ LC (PTIMES LC (CADDR AF)))
		    (SETQ V QNT)
		    ((LAMBDA (MODULUS) 
			     (SETQ OLC (PTIMES (CADDR (CADR LFUNCT)) OLC)))
		     PLIM)
		    (RPLACD LFUNCT (CDDR LFUNCT)))
		   (T (SETQ LFUNCT (CDR LFUNCT))))
	     (SETQ LP (CDR LP))
	     (GO TEST)
	OUT  (RETURN ANS))) 

(DEFUN MULTIDEG (P) 
       (PROG (M D) 
	     (COND ((NUMBERP P) (RETURN 0)) ((ONEVARP P) (RETURN (CADR P))))
	     (SETQ P (CDR P) M (CAR P))
	LOOP (COND ((NULL P) (RETURN M)))
	     (SETQ D (PLUS (CAR P) (MULTIDEG (CADR P))) P (CDDR P) M (MAX D M))
	     (GO LOOP))) 

(DEFUN ODDELM (L) 
       (PROG (ANS) 
	LOOP (COND ((NULL L) (RETURN (NREVERSE ANS)))
		   ((NULL (CDR L)) (RETURN (NREVERSE (CONS (CAR L) ANS)))))
	     (SETQ ANS (CONS (CAR L) ANS) L (CDDR L))
	     (GO LOOP))) 




(DEFUN CPBER3 (V U) 
       (PROG (FACTZ ALCINV LC PLIM MONIC* SHARPCONT LIMK VAR VFACT) 
	     (SETQ VAR (CAR U))
	     (COND ((AND ALGFAC* (NOT (ATOM (CADDR U))))
		    (SETQ ALC (CADDR U))
		    (SETQ U (PTIMES U (CAR(SETQ ALCINV(RAINV ALC))) ))
		    (SETQ V (PTIMES V (CAR ALCINV)))
		    (SETQ ADN* (TIMES ADN* (CDR ALCINV)))))
	     (SETQ U (OLDCONTENT U))
	     (SETQ SHARPCONT (CAR U) U (CADR U))
	     (SETQ LC (CADDR V))
	     (COND ((EQUAL LC 1) (SETQ MONIC* T)))
	     (SETQ FACTZ (FACT5 U))
(COMMENT THIS IS THE BARRY TRICK)
             (COND (*STOP* (SETQ *STOP* PLIM) (RETURN (CONS (CAR SUBVAL)  FACTZ))))
	     (SETQ U NIL)
	     (COND ((NULL (CDR FACTZ)) (RETURN (LIST V)))
		   ((AND ALGFAC* (NOT (EQUAL ADN* 1)))
		    (SETQ V (PCTIMES ADN* V) LC (PCTIMES ADN* LC))))
	     (INCRLIMK V)
	     (SETQ MODULUS PLIM)
	     (SETQ U V V (NEWREP V))
	     (COND ((NUMBERP (CAR FACTZ))
		    (SETQ SHARPCONT (PTIMES SHARPCONT (CAR FACTZ)) FACTZ (CDR FACTZ))))
	     (COND ((NOT (EQUAL SHARPCONT 1))
		    (SETQ FACTZ (CONS (PTIMES SHARPCONT (CAR FACTZ)) (CDR FACTZ)))))
	     (SETQ VFACT (ZFACT V FACTZ LIMK T))

	     (SETQ FACTZ (COND (MONIC* (REVERSE VFACT))
			       (T (RESTORELC VFACT (NEWREP LC)))))
             (COND ((AND ALGFAC* (NOT (EQUAL ADN* 1)))
		    (SETQ V (PCTIMES (CRECIP ADN*) V))(SETQ ADN* 1)))
	     (SETQ VFACT (TRUFAC V FACTZ (NREVERSE VFACT) T MODULU*))
	     (SETQ FACTZ NIL)
	     (COND ((NULL (CDR VFACT)) (RETURN (LIST U)))
		   (T (RETURN (MAPCAR (FUNCTION OLDREP) VFACT))))))

 

(DEFUN NPROD (LC U LFUNCT) 
       (PROG (STAGE V D2 AF0 R LCINDEX FACTOR LLC LTUPLE LPROD LINDEX QNT AF
	      FUNCT TUPLE LTEMP LPR F L LI LF MODULUS HMODULUS) 
	     (SETQ LPR (COPY (SETQ LTEMP (CONS NIL NIL))))
	     (SETQ LPROD (CONS NIL LFUNCT))
	     (SETQ D2 (QUOTIENT (CADR U) 2))
	     (REMOV0 LPROD D2)
	     (SETQ LFUNCT (CDR LPROD))
	     (SETQ LINDEX (INDEX* (SETQ R (LENGTH LFUNCT))))
	     (COND ((NOT MONIC*)
		    (SETQ LLC (MAPCAR (FUNCTION CADDR) LFUNCT))
		    (SETQ LCINDEX (COPY1 LINDEX))
		    (REMOV3 LLC LCINDEX)
		    (SETQ V (PTIMES LC (PTIMES (CADDR U) U))))
		   (T (SETQ V U)))
	     (SETQ LTUPLE (CONS NIL (MAPCAR  #'LIST LINDEX)))
	     (SETQ STAGE 1)
	     (SETQ LINDEX (CONS NIL LINDEX))
	     (SETQ LFUNCT (COPY1 LPROD))
	TLOOP(SETQ STAGE (f1+ STAGE))
	CONT (COND ((OR (GREATERP STAGE D2) (GREATERP STAGE (f1- R)))
		    (RETURN (CONS U FACTOR))))
	NEXTUPLE
	     (COND ((OR (NULL LTUPLE) (NULL (CDR LTUPLE)))
		    (RETURN (CONS U FACTOR))))
	     (SETQ LI (CDR LINDEX))
	     (SETQ LF (CDR LFUNCT))
	     (SETQ TUPLE (CADR LTUPLE))
	     (SETQ FUNCT (CADR LPROD))
	     (RPLACD LTUPLE (CDDR LTUPLE))
	     (RPLACD LPROD (CDDR LPROD))
	ILOOP(SETQ L (CAR LI))
	     (SETQ F (CAR LF))
	     (SETQ LI (CDR LI))
	     (SETQ LF (CDR LF))
	     (COND ((AND (NOT (zl-MEMBER L TUPLE))
			 (NOT (GREATERP (PLUS (CADR F) (CADR FUNCT)) D2))
			 (NOT (zl-MEMBER (SETQ L (ORDE L TUPLE)) LTEMP)))
		    (SETQMODULUS PLIM)
		    (SETQ AF0 (SETQ AF (PTIMES(PMOD F) (PMOD FUNCT))))
		    (COND (LLC (SETQ AF (PTIMES (PMOD (LCHK LLC LCINDEX L)) AF))))
		    (COND (MANY* (SETQ AF (DROPTERMS AF)))
			  ((AND ALGFAC* (NOT (EQUAL INTBS* 1)))(SETQ AF (INTBASEHK AF))))
		    (SETQMODULUS NIL)
		    (COND ((SETQ QNT (TESTDIVIDE V AF))
			   (COND (LLC (SETQ AF (OLDCONTENT AF))
				      (SETQ V (PTIMES (CAR AF) QNT)AF (CADR AF))
				      (SETQ U (COND (ALGFAC*(CAR (CATCH 'RATERR (RQUOTIENT U AF))))
						    (T (PQUOTIENT U AF)))))
				 (T (SETQ U QNT V QNT)))
			   (SETQ FACTOR (CONS AF FACTOR))
			   (COND ((EQUAL U 1) (RETURN FACTOR)))
			   (SETQ D2 (QUOTIENT (CADR U) 2))
			   (COND ((LESSP D2 STAGE) (RETURN (CONS U FACTOR))))
			   (REMOV1 L LTUPLE LPROD D2)
			   (REMOV1 L LTEMP LPR D2)
			   (REMOV2 L LINDEX LFUNCT D2)
			   (SETQ R (DIFFERENCE R STAGE))
			   (GO CONT))
			  (T (SETQ LTEMP (NCONC LTEMP (LIST L)))
			     (SETQ LPR (NCONC LPR (LIST AF0)))))))
	     (COND (LI (GO ILOOP)) ((CDR LTUPLE) (GO NEXTUPLE)))
	     (SETQ LTUPLE LTEMP LPROD LPR LTEMP NIL LPR NIL)
	     (GO TLOOP))) 

(DEFUN REMOV2 (A B C D2) 
       (PROG NIL 
	TAG1 (COND ((NULL (CDR B)) (RETURN NIL))
		   ((OR (zl-MEMBER (CADR B) A) (GREATERP (CADADR C) D2))
		    (RPLACD B (CDDR B))
		    (RPLACD C (CDDR C))
		    (GO TAG1)))
	     (SETQ B (CDR B))
	     (SETQ C (CDR C))
	     (GO TAG1))) 

(DEFUN REMOV1 (A LT1 LP1 D2) 
       (PROG NIL 
	TAG1 (COND ((NULL (CDR LT1)) (RETURN NIL))
		   ((AND (NOT (GREATERP (CADADR LP1) D2))
			 (NULL (INTERSECT A (CADR LT1))))
		    (SETQ LT1 (CDR LT1))
		    (SETQ LP1 (CDR LP1))
		    (GO TAG1)))
	     (RPLACD LT1 (CDDR LT1))
	     (RPLACD LP1 (CDDR LP1))
	     (GO TAG1))) 

(DEFUN REMOV0 (LF D2) 
       (PROG (D)(SETQ D LF) 
	TAG  (COND ((NULL (CDR LF)) (RETURN NIL))
		   ((GREATERP (CADADR LF) D2)(SETQ D2 (CADDR (CADR LF))) (RPLACD LF (CDDR LF))
(COND ((EQUAL D2 1) NIL)(T (RPLACD D (CONS (PTIMES D2 (CADR D)) (CDDR D)))))
(RETURN NIL)))
	     (SETQ LF (CDR LF))
	     (GO TAG)))

(DEFUN REMOV3 (A B) 
       (PROG NIL 
LOOP	     (COND ((NULL (CDR A)) (RETURN NIL))
		   ((EQUAL (CADR A) 1)
		    (RPLACD A (CDDR A))
		    (RPLACD B (CDDR B))(GO LOOP)))
	     (SETQ A (CDR A) B (CDR B))(GO LOOP))) 

(DEFUN LCHK (A B C) 
       (PROG (ANS) 
	     (SETQ ANS 1)
	LOOP (COND ((NULL A) (RETURN ANS))
		   ((NOT (zl-MEMBER (CAR B) C)) (SETQ ANS (PTIMES ANS (CAR A)))))
	     (SETQ A (CDR A) B (CDR B))
	     (GO LOOP))) 

 

(DEFUN LCPRODL (L) 
       (PROG (ANS D) 
	     (SETQ D 1 L (REVERSE L) ANS '(1))
	LOOP (COND ((NULL (CDR L)) (RETURN ANS)))
	     (SETQ D (PTIMES D (CADDAR L)))
	     (SETQ L (CDR L))
	     (SETQ ANS (CONS D ANS))
	     (GO LOOP))) 


(DEFUN FACT5 (POLY) 
       (PROG (QL TRL* LINFAC UU* LC DEG FACTP FACTZ MODULUS MONIC*  SPLIT* VAR
	      ANOTYPE FCTC INVC AFIXN FCTCFIXN INVCFIXN) 
	     (SETQ VAR (CAR POLY))
	     (COND ((NULL (CDDDR POLY)) (RETURN (LIST POLY))))
	     (COND((AND ALGFAC* (NOT (ATOM (CADDR POLY))))
		   (SETQ ALC (CADDR POLY))
		   (SETQ POLY (RATTIMES (CONS POLY 1) (SETQ ALCINV(RAINV ALC)) T))
		   (SETQ ADN*(TIMES ADN* (CDR POLY)))
		   (SETQ POLY (CAR POLY))))
	     (COND((AND ALGFAC* MINPOLY* (OR $NALGFAC (EQUAL (CDR MINPOLY*) '(4 1 0 1))))
		   (SETQ QL 'SPLITCASE) (GO TAG0)))
	     (SETQ UU* POLY)
	     (COND ((EQUAL (SETQ LC (CADDR UU*)) 1) (SETQ MONIC* T)))
	     (SETQ DEG (CADR POLY))
	     (COND ((NOT ALGFAC*)
		    (SETQ FCTCFIXN (*ARRAY NIL 'fixnum DEG)
			  INVCFIXN (*ARRAY NIL 'fixnum DEG)
			  AFIXN (*ARRAY NIL 'fixnum DEG DEG)))
		   (T (SETQ FCTC (*ARRAY NIL T DEG)
			    INVC (*ARRAY NIL T DEG)
			    ANOTYPE (*ARRAY NIL T DEG DEG)
			    FCTCFIXN (*ARRAY NIL 'fixnum MM*)
			    INVCFIXN (*ARRAY NIL 'fixnum MM*)
			    AFIXN (*ARRAY NIL 'fixnum MM* MM*))))
	     (COND (MODULU* (RETURN (FACT5MOD POLY))))
	     (COND ((NOT (ATOM (SETQ QL (CHOOZP UU*))))
		    (SETQ LINFAC (CAR QL) UU* (CADDR QL) QL (CADR QL))))
	     (SETQ *PRIME MODULUS)
TAG0	     (COND ((EQ QL 'SPLITCASE) 
		    (SETQ POLY(NALGFAC POLY (CONS (CAR ALPHA) (CDR MINPOLY*))))
		    (SETQ PLIM *ALPHA *PRIME PLIM LIMK -1)
		    (RETURN POLY))
		   ((NULL (CDR (APPEND LINFAC QL)))
		    (SETQ POLY (LIST POLY))
		    (GO OUT))
		   ((EQUAL UU* 1) (SETQ FACTP NIL) (GO ON)))
	     (COND  (ALGFAC* (SETQ FACTP (CPBGZASS QL  UU* (LENGTH QL))))
		   ((NOT (EQUAL UU* 1))
		    (SETQ FACTP (CPBG QL  UU* (LENGTH QL)))))
	     (SETQ UU* NIL)
	ON   (SETQ FACTP (NCONC FACTP LINFAC) 
		    LINFAC NIL
 FACTP (CONS (PCTIMES (PMOD LC) (CAR FACTP)) (CDR FACTP)))
	     (SETQ LIMK (KLIM POLY MODULUS))
	     (SETQ FACTZ (ZFACT POLY FACTP LIMK NIL)FACTP NIL)
	     (SETQ POLY (TRUFAC POLY
				((LAMBDA (MODULUS) (RESTORELC FACTZ LC)) PLIM)
				(NREVERSE FACTZ)
				NIL
				NIL))
	     (SETQ MODULUS NIL)
;(COND ((NULL (CDR POLY))(GO OUT)) not needed and doesn't work?
;(ALGFAC* (SETQ ADN* (PTIMES ADN*(PQUOTIENT 
;(APPLY (FUNCTION TIMES) (MAPCAR (FUNCTION CADDR) POLY)) (TIMES ADN* LC))))))
	OUT  (RETURN POLY)))



(DEFUN FACT5MOD (U)
       (PROG (LC POLY)
	     (SETQ POLY (COPY1 U))
	     (SETQMODULUS MODULU*)
	     (SETQ POLY (PMOD POLY))	     
	     (SETQ LC (CADDR POLY))
	     (PMONICIZE (CDR POLY))
	     (SETQ POLY(CPBERL POLY))
	     (COND ((NULL (CDR POLY))
		    (RETURN (LIST U)))
		   (T (RETURN (COND ((EQUAL LC 1) POLY)
				    (T (CONS LC POLY))))))))


(DEFUN CPBG (QLIST V M)
     (declare (fixnum m))
       (PROG (Y VJ FACTORS U W (J 0)
	      (P1  (// MODULUS 2))
	      (P2 1)
	      FNJ FNQ OLDFAC) 
	     (DECLARE (FIXNUM J P1 P2))
	     (COND ((= M 1) (RETURN (LIST V))))
	     (SETQ P1 (// MODULUS 2))
	     (SETQ P2 1)
	     (SETQ QLIST (CDR (NREVERSE QLIST)))
	     (SETQ OLDFAC (LIST NIL V))
	     (SETQ V NIL)
	TAG3 (SETQ VJ (NCONC (CAR QLIST) (LIST 0 0)))
	     (SETQ QLIST (CDR QLIST))
	     (SETQ J (f- P1))
	     (SETQ OLDFAC (NCONC OLDFAC FNQ))
	     (SETQ FNQ NIL)
	INCRJ(SETQ FACTORS (NCONC OLDFAC FNJ))
	     (SETQ FNJ NIL)
	     (PCDIFCONC VJ J)
	TAG2 (SETQ U (CADR FACTORS))
	     (SETQ W (PGCDU VJ U))
	     (COND ((OR (NUMBERP W) (= (CADR W) (CADR U))) (GO AGG)))
	     (SETQ Y (CAR (PMODQUO U W)))
	     (SETQ FNQ (CONS (COPY1 W) FNQ))
	     (SETQ FNJ (CONS Y FNJ))
	     (SETQ P2 (f1+ P2))
	     (RPLACD FACTORS (CDDR FACTORS))
	     (COND ((EQUAL P2 M) (GO OUT)) (T (GO TAG1)))
	AGG  (SETQ FACTORS (CDR FACTORS))
	TAG1 (COND ((CDR FACTORS) (GO TAG2))
		   ((< J P1) (SETQ J (f1+ J)) (GO INCRJ))
		   (QLIST (GO TAG3)))
	OUT  (RETURN (NCONC FNQ FNJ (CDR OLDFAC)))))
 



(DEFUN FACT2Z (U F G LIMK) 
       (PROG (A A1 W PK MPK B C R P QL QLP H (K 0) B1)
	            (DECLARE (FIXNUM K))
	     (SETQ P MODULUS)
	     (SETQ R (PPPROG F G))
	     (SETQ A (CAR R))
	     (SETQ B (CADR R))
	     (LET ((MODULUS NIL))
	       (SETQ R (PDIFFERENCE (PTIMES F G) U)))
	  SHARP (COND ((OR (EQUAL R 0) (> K LIMK)) (GO ON)))
	     (SETQ PK MODULUS MPK (MINUS PK))
	     (SETQ MODULUS (TIMES MODULUS MODULUS))
	     (SETQ W (PMOD R))
	     (COND ((EQUAL W 0) (GO TAG1)))
	     (SETQ C (NPQUO W PK))(SETQ W NIL)
	     (SETQ QL (PMODQUO (PTIMES A C) G))
	     (SETQ A1 (NPCTIMES MPK
				(PPLUS (PTIMES (CAR QL) F)
				       (PTIMES B C))))
	     (SETQ B1 (NPCTIMES MPK (CDR QL)))
	     (LET ((MODULUS PLIM)) 
	       (SETQ R (PPLUS (PPLUS R (PTIMES A1 B1))
			      (PPLUS (PTIMES A1 G) (PTIMES B1 F))))
	       (SETQ F (PPLUS F A1))
	       (SETQ G (PPLUS G B1)))
	     (SETQ A1 NIL B1 NIL)
TAG1         (COND ((OR (EQUAL R 0)(> (SETQ K(f1+ K)) LIMK)) (GO ON)))
             (SETQ H (NPQUO (PPLUS (PPLUS (PTIMES A F)
					  (PTIMES B G))
				   -1)
			    PK))
	     (SETQ QLP (PMODQUO (PTIMES A H) G))
	     (SETQ B1 (PPLUS (PTIMES B H) (PTIMES (CAR QLP) F)))
	     (SETQ A (PPLUS A (NPCTIMES MPK (CDR QLP))))
	     (SETQ B (PPLUS B (NPCTIMES MPK B1)))
	     (SETQ H NIL B1 NIL QLP NIL)
	     (GO SHARP)
        ON   (SETQMODULUS P)
	     (RETURN (LIST F G))))



(DEFUN NPCTIMES (C P)
       (SETQ P (NPCTIMES1 C P))
       (COND ((AND (NOT (ATOM P)) (NULL (CDR P))) 0)
	     (T P)))

(DEFUN NPQUO (P C)
       (PROG (U MODULUS)
	     (COND ((EQUAL C 1)(RETURN P))
		   ((PCOEFP P)(RETURN (QUOTIENT P C))))
	     (SETQ U P)
	LOOP (COND ((NULL (CDR U))(RETURN P)))
	     (SETQ U (CDDR U))
	     (RPLACA U (COND ((PCOEFP (CAR U))
			      (QUOTIENT (CAR U) C))
			     (T (NPQUO (COPY1 (CAR U)) C))))
	     (GO LOOP)))

(DEFUN NPCTIMES1 (C P)
       (PROG (U A)
	     (COND((EQUAL C 1)(RETURN P))
		  ((PCOEFP P)(RETURN (CTIMES C P))))
	     (SETQ U P)
	LOOP (COND ((NULL (CDR U))(RETURN P)))
	     (SETQ A (COND ((PCOEFP (CADDR U)) (CTIMES C (CADDR U)))
			   (T (NPCTIMES C (COPY1 (CADDR U))))))
	     (COND ((EQUAL A 0) (RPLACD U (CDDDR U)))
		   (T (SETQ U (CDDR U))
		      (RPLACA U A)))
	     (GO LOOP)))

(DEFUN X**Q1 (TERM U M P) 
       (DECLARE (FIXNUM M))
       (PROG ((I 1) )
	     (declare (fixnum i))
	     (SETQ TRL* (LIST TERM))
	LOOP (COND ((= I M) (RETURN (PEXPTMOD TERM P U))))
	     (SETQ TERM (PEXPTMOD TERM P U))
	     (SETQ TRL* (CONS TERM TRL*))
	     (SETQ I (f1+ I))
	     (GO LOOP)))

;(DECLARE (ARRAY* (NOTYPE A 2 INVC 1 FCTC 1)))

(DEFUN CPTOMF (P U N) 
       (DECLARE (FIXNUM N P  ))
       (PROG (L S *XN (J 0) (I 0) IND (N-1(f1- n)) )
	     (declare (fixnum i j))
	LOOP (SETQ J (f1+ J))
	     (COND ((= J N) (RETURN NIL))
		   (IND (GO SA))
		   ((> (f* P J) N-1)
		    (SETQ *XN (MAPCAR (FUNCTION -) (P2CPOL (CDDR U) N-1))
			  S (COPY *XN)
			  IND T)
		    (SETQ I (f- (f* P J) N))
		    (GO SA1)))
	     (SETQ S (P2CPOL (LIST VAR (f* P J) 1) N-1))
	     (GO ST)
	SA   (SETQ I P)
	SA1  (COND ((= I 0) (GO ST)))
	     (CPTIMESX S)
	     (SETQ I (f1- I))
	     (GO SA1)
	ST   (COND ((AND (= J 1)
			 (EQUAL '(1 0) (NCDR S (f1- (LENGTH S) )))
			 (= 1 (APPLY (FUNCTION +) S)))
		    (RETURN (SETQ SPLIT* T))))
	     (SETQ L S)
	     (SETQ I N-1)
	sharp2  (COND ((NULL L) (GO ON)))
	     (STORE (AFIXN J I) (CAR L))
	     (SETQ L (CDR L))
	     (SETQ I (f1- I))
	     (GO sharp2)
	ON   (STORE (AFIXN J J) (f- (AFIXN J J) 1))
	     (GO LOOP)))

(DEFUN P2CPOL (P N) 
       (DECLARE (FIXNUM N))
       (PROG (L) 
	     (SETQ P (CDR P))
	LOOP (COND ((= N -1) (RETURN (NREVERSE L)))
		   ((OR (NULL P) (> N (CAR P))) (SETQ L (CONS 0 L)))
		   ((= N (CAR P))
		    (SETQ L (CONS (CADR P) L))
		    (SETQ P (CDDR P))))
	     (SETQ N (f1- N))
	     (GO LOOP)))

(DEFUN CPTIMESX (P) 
       (PROG (XN Q LC) 
	     (SETQ XN *XN Q P LC (CAR P))
	LOOP (COND ((CDR Q)
		    (RPLACA Q (CPLUS (CADR Q) (CTIMES LC (CAR XN))))
		    (SETQ Q (CDR Q) XN (CDR XN)))
		   (T (RPLACA Q (CTIMES LC (CAR XN))) (RETURN P)))
	     (GO LOOP)))


(DEFUN CMNULLF (N) 
       (DECLARE (FIXNUM N))
       (PROG (NULLSP MONE (K 1) (J 0) S  ( N-1 (f1- N))  NULLV VJ M AKS)
	     (declare (fixnum k j n-1))
	     #-cl ;too hard to sort these out now.
            (DECLARE (FIXNUM AKS M N J S K SUB1N VJ))
	     (SETQ MONE (CMOD -1))
	     (DO ((I 0 (f1+ I))) ((> I N-1))
		 (STORE (FCTCFIXN I) -1)
		 (STORE (INVCFIXN I) -1))
	     (SETQ  NULLSP (LIST 1))
	N2   (COND ((> K N-1) (RETURN NULLSP)))
	     (SETQ J 0)
	N3A  (COND ((> J N-1) (GO NULL))
		   ((OR (= (AFIXN K J) 0) (> (FCTCFIXN J) -1))
		    (SETQ J (f1+ J))
		    (GO N3A)))
	     (STORE (INVCFIXN K) J)
	     (STORE (FCTCFIXN J) K)
	     (SETQ M (AFIXN K J))
	     (SETQ M (CRECIP (CTIMES MONE M)))
	     (DO ((S K (f1+ S))) ((> S N-1))
		 (STORE (AFIXN S J) (CTIMES M (AFIXN S J))))
	     (COMMENT (GO THROUGH COLUMNS))
	     (SETQ S 0)
	sharp2  (COND ((> S N-1) (GO NEXTK)))
	     (COMMENT (GO THROUGH ROWS IN EACH COLUMN))
	     (COND ((= S J) NIL)
		   (T (SETQ AKS (AFIXN K S))
		      (DO ((I K (f1+ I))) ((> I N-1))
			  (STORE (AFIXN I S)
				 (CPLUS (AFIXN I S)
					(CTIMES (AFIXN I J) AKS))))))
	     (SETQ S (f1+ S))
	     (GO sharp2)
	NULL (SETQ NULLV NIL)
	     (DO ((S 0 (f1+ S))) ((> S N-1))
		 (COND ((= S K) (SETQ NULLV (CONS S (CONS 1 NULLV))))
		       ((> (INVCFIXN S) -1)
			(SETQ VJ (AFIXN K (INVCFIXN S)))
			(COND ((= VJ 0) NIL)
			      (T (SETQ NULLV (CONS S (CONS VJ NULLV))))))))
	     (COND ((EQUAL (CAR NULLV) 0) (SETQ NULLV (CADR NULLV)))
		   ((SETQ NULLV (CONS VAR NULLV))))
	     (SETQ NULLSP (CONS NULLV NULLSP))
	NEXTK(SETQ K (f1+ K))
	     (GO N2)))


(DEFUN CHOOZP (V) 
       #-cl (DECLARE (FIXNUM NCONT N NF MINCONT LMIN ALGCONT))
       (PROG (LCHAR1 U TR N (NCONT 1) BMOD B1 B MINCONT (LMIN 0) (NF 0)
	      (DEG  (CADR V)) (ALGCONT 0))
	     (declare (special ncont lmin nf deg algcont))
	     (SETQ NF (HAULONG  DEG))
	     (SETQ LCHAR1 (COND (GAUSS '(3 7 11. 19. 23. 29. 31. 37.))
				(T SMALLPRIMES)))
	TEST (SETQ MODULUS (CAR LCHAR1))
	     (SETQ U (PMOD V))
	     (COND ((OR (ZEROP (REMAINDER SHARPCONT MODULUS))
			(AND (NOT MONIC*)
			     (OR (PCOEFP U)
				 (> DEG (CADR U)))))
		    (GO NEXTP)))
	     (COND ((OR (NULL (SQFRP U VAR))
			(AND ALGFAC*
			     (NOT GAUSS)
  			     (NOT (IREDUP (PMOD MINPOLY*)))
			     ))
		     (SETQ ALGCONT(f1+ ALGCONT))
		    (GO NEXTP)))
	     (PMONICIZE (CDR U))
	     (SETQ B1 (CATCH 'SPLT (CPBER1 U)))(SETQ ALGCONT 0)
	     (SETQ NCONT (f1+ NCONT))
	     (SETQ N (f+ (LENGTH (CAR B1)) (LENGTH (CADR B1))))
	     (COND ((OR (ZEROP LMIN) (< N LMIN))
		    (SETQ LMIN N  MINCONT 1 BMOD MODULUS B B1)
		    (COND (ALGFAC* (SETQ TR TRL*))))
		   ((= N LMIN) (SETQ MINCONT (f1+ MINCONT))))
	     (COND ((OR (> NCONT NF) (NOT(> N NF)) (= MINCONT 3)) (GO OUT)))
	NEXTP(SETQ LCHAR1 (CDR LCHAR1))
	     (COND ((NULL LCHAR1)
		    (COND ((NOT (ZEROP LMIN)) (GO OUT))
			  (T (MERROR "Factor ran out of primes."))))
		   ((> ALGCONT 6)
		    (COND ((ZIREDUP MINPOLY*)(SETQ TRL* TR)(SETQ MODULUS NIL)
					     (RETURN 'SPLITCASE))
		      (T (MERROR "The minimal poly must be irreducible over the integers.")))))
	     (GO TEST)
	OUT  (SETQ MODULUS BMOD TRL* TR)
	     (RETURN B)))
 

(DEFUN CPBQ1 (A N) 
       (DECLARE (FIXNUM  N ))
       (PROG () 
	     (SETQ SPLIT* NIL)
	     (COND ((NOT (INTEGERP MODULUS)) (*ARRAY 'A T N N)))
	     (COND ((OR ALGFAC* (NOT (INTEGERP MODULUS)))
		    (CPTOM MODULUS MM* A N))
		   (T (CPTOMF MODULUS A N)))
	     (COND (SPLIT*
		    (RETURN (POWRS (CAR A) (CADR A)))))
	     (RETURN (COND ((OR ALGFAC* (NOT (INTEGERP MODULUS)))
			    (CMNULL N))
			   (T (CMNULLF N))))))
 

(DEFUN CPBER1 (U) 
       (PROG (LINFAC) 
	     (SETQ VAR (CAR U))
	     (SETQ LINFAC
		   (LINOUT U)
		   U
		   (CAR LINFAC)
		   LINFAC
		   (CADR LINFAC))
	     (COND ((EQUAL U 1) (RETURN (LIST LINFAC NIL U))))
	     (RETURN (LIST LINFAC (CPBQ1 U (CADR U)) U))))
  

(DEFUN FACTOR1972 (P) 
       (LET ((MODULU* MODULUS) MANY* *STOP* MODULUS HMODULUS MCFLAG NEGFLAG) 
	    (COND ((OR (ATOM P) (NUMBERP P)(AND ALGFAC* (ALG P))) (LIST P))
		  (T (FACTOR72 P)))))

(DEFUN FACTOR72 (P) 
  (LET ((SHARPCONT 1) PLIM) 
       (SETQ P (COND ((ONEVARP P) (MAPCAR (FUNCTION POSIZE) (FACT5 P)))
		     ((AND $NEWFAC (NULL MODULUS) (NOT ALGFAC*))
		      (SETQ MANY* T) (NMULTFACT P))
		     (T (SETQ MANY* T) (MULTFACT P))))
       (COND (NEGFLAG (CONS (PMINUS (CAR P)) (CDR P))) (T P))))

(DEFUN POSIZE (P) 
       (COND ((PMINUSP P) (SETQ NEGFLAG (NOT NEGFLAG)) (PMINUS P)) (T P))) 


;;moved to rat3c.lisp
;#+LISPM
;(eval-when (load)
;(DO ((I 0 (f1+ I))				;GENERATES 20 LARGEST
;	     (P (LSH -1 -1) (NEWPRIME P)))		;PRIMES < WORD
;	    ((= I 20.)))

;)

;(DEFMVAR *ALPHA (CAR BIGPRIMES))