1 2(SDEFUN |GAUSSFAC;reduction| ((|u| |Integer|) (|p| |Integer|) ($ |Integer|)) 3 (COND ((EQL |p| 0) |u|) ('T (SPADCALL |u| |p| (QREFELT $ 7))))) 4 5(SDEFUN |GAUSSFAC;merge| 6 ((|p| |Integer|) (|q| |Integer|) ($ |Union| (|Integer|) "failed")) 7 (COND ((EQL |p| |q|) (CONS 0 |p|)) ((EQL |p| 0) (CONS 0 |q|)) 8 ((EQL |q| 0) (CONS 0 |p|)) ('T (CONS 1 "failed")))) 9 10(SDEFUN |GAUSSFAC;exactquo| 11 ((|u| |Integer|) (|v| |Integer|) (|p| |Integer|) 12 ($ |Union| (|Integer|) "failed")) 13 (SPROG ((#1=#:G417 NIL)) 14 (COND ((EQL |p| 0) (SPADCALL |u| |v| (QREFELT $ 9))) 15 ((EQL (REM |v| |p|) 0) (CONS 1 "failed")) 16 ('T 17 (CONS 0 18 (SPADCALL 19 (QCAR 20 (PROG2 21 (LETT #1# 22 (SPADCALL |v| |p| |u| (QREFELT $ 12))) 23 (QCDR #1#) 24 (|check_union2| (QEQCAR #1# 0) 25 (|Record| 26 (|:| |coef1| (|Integer|)) 27 (|:| |coef2| (|Integer|))) 28 (|Union| 29 (|Record| 30 (|:| |coef1| (|Integer|)) 31 (|:| |coef2| (|Integer|))) 32 "failed") 33 #1#))) 34 |p| (QREFELT $ 7))))))) 35 36(SDEFUN |GAUSSFAC;findelt| ((|q| |Integer|) ($ |Integer|)) 37 (SPROG 38 ((|t| (|FMod|)) (|s| (|FMod|)) (#1=#:G437 NIL) (|i| NIL) 39 (|qq1| (|FMod|)) (|r1| (|Union| (|Integer|) "failed")) 40 (|r| #2=(|Integer|)) (#3=#:G412 NIL) (|q1| #2#)) 41 (SEQ (LETT |q1| (- |q| 1)) (LETT |r| |q1|) 42 (LETT |r1| (SPADCALL |r| 4 (QREFELT $ 9))) 43 (SEQ G190 (COND ((NULL (NULL (QEQCAR |r1| 1))) (GO G191))) 44 (SEQ 45 (LETT |r| 46 (PROG2 (LETT #3# |r1|) 47 (QCDR #3#) 48 (|check_union2| (QEQCAR #3# 0) (|Integer|) 49 (|Union| (|Integer|) "failed") 50 #3#))) 51 (EXIT (LETT |r1| (SPADCALL |r| 2 (QREFELT $ 9))))) 52 NIL (GO G190) G191 (EXIT NIL)) 53 (LETT |s| (SPADCALL 1 |q| (QREFELT $ 18))) 54 (LETT |qq1| (SPADCALL |q1| |q| (QREFELT $ 18))) 55 (SEQ (LETT |i| 2) G190 56 (COND 57 ((NULL 58 (COND 59 ((SPADCALL |s| (|spadConstant| $ 14) (QREFELT $ 20)) 'T) 60 ('T (SPADCALL |s| |qq1| (QREFELT $ 20))))) 61 (GO G191))) 62 (SEQ 63 (EXIT 64 (LETT |s| 65 (SPADCALL (SPADCALL |i| |q| (QREFELT $ 18)) 66 (PROG1 (LETT #1# |r|) 67 (|check_subtype2| (>= #1# 0) 68 '(|NonNegativeInteger|) 69 '(|Integer|) #1#)) 70 (QREFELT $ 22))))) 71 (LETT |i| (|inc_SI| |i|)) (GO G190) G191 (EXIT NIL)) 72 (LETT |t| |s|) 73 (SEQ G190 74 (COND 75 ((NULL (SPADCALL |t| |qq1| (QREFELT $ 23))) (GO G191))) 76 (SEQ (LETT |s| |t|) 77 (EXIT (LETT |t| (SPADCALL |t| 2 (QREFELT $ 25))))) 78 NIL (GO G190) G191 (EXIT NIL)) 79 (EXIT (SPADCALL |s| (QREFELT $ 26)))))) 80 81(SDEFUN |GAUSSFAC;sumsq1| ((|p| . #1=(|Integer|)) ($ |List| (|Integer|))) 82 (SPROG ((|s| (|Integer|)) (|u| #1#) (|w| (|Integer|))) 83 (SEQ (LETT |s| (|GAUSSFAC;findelt| |p| $)) (LETT |u| |p|) 84 (SEQ G190 (COND ((NULL (> (EXPT |u| 2) |p|)) (GO G191))) 85 (SEQ (LETT |w| (REM |u| |s|)) (LETT |u| |s|) 86 (EXIT (LETT |s| |w|))) 87 NIL (GO G190) G191 (EXIT NIL)) 88 (EXIT (LIST |u| |s|))))) 89 90(SDEFUN |GAUSSFAC;intfactor| 91 ((|n| |Integer|) ($ |Factored| (|Complex| (|Integer|)))) 92 (SPROG 93 ((|r| 94 (|List| 95 (|Record| (|:| |flag| (|Union| "nil" "sqfr" "irred" "prime")) 96 (|:| |factor| (|Complex| (|Integer|))) 97 (|:| |exponent| (|NonNegativeInteger|))))) 98 (|z| #1=(|Complex| (|Integer|))) (|sz| (|List| (|Integer|))) 99 (|unity| #1#) (|exp| (|NonNegativeInteger|)) (#2=#:G461 NIL) 100 (|term| NIL) (|lfn| (|Factored| (|Integer|)))) 101 (SEQ (LETT |lfn| (SPADCALL |n| (QREFELT $ 29))) (LETT |r| NIL) 102 (LETT |unity| 103 (SPADCALL (SPADCALL |lfn| (QREFELT $ 30)) 0 104 (QREFELT $ 16))) 105 (SEQ (LETT |term| NIL) (LETT #2# (SPADCALL |lfn| (QREFELT $ 34))) 106 G190 107 (COND 108 ((OR (ATOM #2#) (PROGN (LETT |term| (CAR #2#)) NIL)) 109 (GO G191))) 110 (SEQ (LETT |n| (QVELT |term| 1)) 111 (LETT |exp| (QVELT |term| 2)) 112 (EXIT 113 (COND 114 ((EQL |n| 2) 115 (SEQ 116 (LETT |r| 117 (CONS 118 (VECTOR (CONS 3 "prime") (QREFELT $ 17) 119 (* 2 |exp|)) 120 |r|)) 121 (EXIT 122 (LETT |unity| 123 (SPADCALL |unity| 124 (SPADCALL 125 (SPADCALL 0 -1 (QREFELT $ 16)) 126 (REM |exp| 4) (QREFELT $ 35)) 127 (QREFELT $ 36)))))) 128 ((EQL (REM |n| 4) 3) 129 (LETT |r| 130 (CONS 131 (VECTOR (CONS 3 "prime") 132 (SPADCALL |n| 0 (QREFELT $ 16)) 133 |exp|) 134 |r|))) 135 ('T 136 (SEQ (LETT |sz| (|GAUSSFAC;sumsq1| |n| $)) 137 (LETT |z| 138 (SPADCALL 139 (SPADCALL |sz| 1 (QREFELT $ 38)) 140 (SPADCALL |sz| 2 (QREFELT $ 38)) 141 (QREFELT $ 16))) 142 (EXIT 143 (LETT |r| 144 (CONS 145 (VECTOR (CONS 3 "prime") |z| |exp|) 146 (CONS 147 (VECTOR (CONS 3 "prime") 148 (SPADCALL |z| (QREFELT $ 39)) 149 |exp|) 150 |r|))))))))) 151 (LETT #2# (CDR #2#)) (GO G190) G191 (EXIT NIL)) 152 (EXIT (SPADCALL |unity| |r| (QREFELT $ 43)))))) 153 154(SDEFUN |GAUSSFAC;factor;CF;7| 155 ((|m| |Complex| (|Integer|)) ($ |Factored| (|Complex| (|Integer|)))) 156 (SPROG 157 ((|unity| (|Complex| (|Integer|))) 158 (|result| 159 (|List| 160 (|Record| (|:| |flag| (|Union| "nil" "sqfr" "irred" "prime")) 161 (|:| |factor| (|Complex| (|Integer|))) 162 (|:| |exponent| (|NonNegativeInteger|))))) 163 (|z| (|Complex| (|Integer|))) 164 (|part| 165 (|Record| 166 (|:| |flag| (|Union| #1="nil" #2="sqfr" #3="irred" #4="prime")) 167 (|:| |factor| (|Complex| (|Integer|))) 168 (|:| |exponent| (|NonNegativeInteger|)))) 169 (|g0| (|Complex| (|Integer|))) (|exp| #5=(|NonNegativeInteger|)) 170 (|n| (|Integer|)) (#6=#:G482 NIL) (|term| NIL) 171 (|factn| 172 (|List| 173 (|Record| (|:| |flag| (|Union| #1# #2# #3# #4#)) 174 (|:| |factor| (|Integer|)) (|:| |exponent| #5#)))) 175 (|r| #7=(|Factored| (|Complex| (|Integer|)))) (|b| (|Integer|)) 176 (#8=#:G412 NIL) (|a| (|Integer|)) (|d| (|Integer|)) (|ris| #7#)) 177 (SEQ 178 (COND 179 ((SPADCALL |m| (|spadConstant| $ 45) (QREFELT $ 46)) 180 (SPADCALL (|spadConstant| $ 45) 1 (QREFELT $ 47))) 181 (#9='T 182 (SEQ (LETT |a| (SPADCALL |m| (QREFELT $ 48))) 183 (LETT |b| (SPADCALL |m| (QREFELT $ 49))) 184 (EXIT 185 (COND ((EQL |b| 0) (|GAUSSFAC;intfactor| |a| $)) 186 ((EQL |a| 0) 187 (SEQ (LETT |ris| (|GAUSSFAC;intfactor| |b| $)) 188 (LETT |unity| 189 (SPADCALL (SPADCALL |ris| (QREFELT $ 50)) 190 (SPADCALL 0 1 (QREFELT $ 16)) 191 (QREFELT $ 36))) 192 (EXIT 193 (SPADCALL |unity| 194 (SPADCALL |ris| (QREFELT $ 51)) 195 (QREFELT $ 43))))) 196 (#9# 197 (SEQ (LETT |d| (GCD |a| |b|)) (LETT |result| NIL) 198 (LETT |unity| (|spadConstant| $ 52)) 199 (COND 200 ((SPADCALL |d| 1 (QREFELT $ 53)) 201 (SEQ 202 (LETT |a| 203 (PROG2 204 (LETT #8# 205 (SPADCALL |a| |d| 206 (QREFELT $ 9))) 207 (QCDR #8#) 208 (|check_union2| (QEQCAR #8# 0) 209 (|Integer|) 210 (|Union| (|Integer|) 211 #10="failed") 212 #8#))) 213 (LETT |b| 214 (PROG2 215 (LETT #8# 216 (SPADCALL |b| |d| 217 (QREFELT $ 9))) 218 (QCDR #8#) 219 (|check_union2| (QEQCAR #8# 0) 220 (|Integer|) 221 (|Union| (|Integer|) 222 #10#) 223 #8#))) 224 (LETT |r| (|GAUSSFAC;intfactor| |d| $)) 225 (LETT |result| (SPADCALL |r| (QREFELT $ 51))) 226 (LETT |unity| (SPADCALL |r| (QREFELT $ 50))) 227 (EXIT 228 (LETT |m| 229 (SPADCALL |a| |b| (QREFELT $ 16))))))) 230 (LETT |n| (+ (EXPT |a| 2) (EXPT |b| 2))) 231 (LETT |factn| 232 (SPADCALL (SPADCALL |n| (QREFELT $ 29)) 233 (QREFELT $ 34))) 234 (LETT |part| 235 (VECTOR (CONS 3 "prime") 236 (|spadConstant| $ 45) 0)) 237 (SEQ (LETT |term| NIL) (LETT #6# |factn|) G190 238 (COND 239 ((OR (ATOM #6#) 240 (PROGN (LETT |term| (CAR #6#)) NIL)) 241 (GO G191))) 242 (SEQ (LETT |n| (QVELT |term| 1)) 243 (LETT |exp| (QVELT |term| 2)) 244 (EXIT 245 (COND 246 ((EQL |n| 2) 247 (SEQ 248 (LETT |part| 249 (VECTOR (CONS 3 "prime") 250 (QREFELT $ 17) 251 |exp|)) 252 (LETT |m| 253 (SPADCALL |m| 254 (SPADCALL 255 (QREFELT $ 17) 256 |exp| 257 (QREFELT $ 35)) 258 (QREFELT $ 54))) 259 (EXIT 260 (LETT |result| 261 (CONS |part| |result|))))) 262 ((EQL (REM |n| 4) 3) 263 (SEQ 264 (LETT |g0| 265 (SPADCALL |n| 0 266 (QREFELT $ 16))) 267 (LETT |part| 268 (VECTOR (CONS 3 "prime") |g0| 269 (QUOTIENT2 |exp| 2))) 270 (LETT |m| 271 (SPADCALL |m| |g0| 272 (QREFELT $ 54))) 273 (EXIT 274 (LETT |result| 275 (CONS |part| |result|))))) 276 ('T 277 (SEQ 278 (LETT |z| 279 (SPADCALL |m| 280 (SPADCALL |n| 0 281 (QREFELT 282 $ 16)) 283 (QREFELT $ 55))) 284 (LETT |part| 285 (VECTOR (CONS 3 "prime") |z| 286 |exp|)) 287 (LETT |z| 288 (SPADCALL |z| |exp| 289 (QREFELT $ 35))) 290 (LETT |m| 291 (SPADCALL |m| |z| 292 (QREFELT $ 54))) 293 (EXIT 294 (LETT |result| 295 (CONS |part| 296 |result|)))))))) 297 (LETT #6# (CDR #6#)) (GO G190) G191 298 (EXIT NIL)) 299 (COND 300 ((SPADCALL |m| (|spadConstant| $ 52) 301 (QREFELT $ 56)) 302 (LETT |unity| 303 (SPADCALL |unity| |m| (QREFELT $ 36))))) 304 (EXIT 305 (SPADCALL |unity| |result| 306 (QREFELT $ 43))))))))))))) 307 308(SDEFUN |GAUSSFAC;sumSquares;IL;8| ((|p| |Integer|) ($ |List| (|Integer|))) 309 (COND ((EQL |p| 2) (LIST 1 1)) 310 ((SPADCALL (REM |p| 4) 1 (QREFELT $ 53)) 311 (|error| "no solutions")) 312 ('T (|GAUSSFAC;sumsq1| |p| $)))) 313 314(SDEFUN |GAUSSFAC;prime?;CB;9| ((|a| |Complex| (|Integer|)) ($ |Boolean|)) 315 (SPROG 316 ((|p| (|Integer|)) (|im| (|Integer|)) (|re| (|Integer|)) 317 (|n| (|Integer|))) 318 (SEQ (LETT |n| (SPADCALL |a| (QREFELT $ 59))) 319 (EXIT 320 (COND ((OR (EQL |n| 0) (EQL |n| 1)) NIL) 321 ((SPADCALL |n| (QREFELT $ 61)) 'T) 322 (#1='T 323 (SEQ (LETT |re| (SPADCALL |a| (QREFELT $ 48))) 324 (LETT |im| (SPADCALL |a| (QREFELT $ 49))) 325 (COND 326 ((SPADCALL |re| 0 (QREFELT $ 53)) 327 (COND 328 ((SPADCALL |im| 0 (QREFELT $ 53)) (EXIT NIL))))) 329 (LETT |p| (ABS (+ |re| |im|))) 330 (EXIT 331 (COND ((SPADCALL (REM |p| 4) 3 (QREFELT $ 53)) NIL) 332 (#1# (SPADCALL |p| (QREFELT $ 61)))))))))))) 333 334(DECLAIM (NOTINLINE |GaussianFactorizationPackage;|)) 335 336(DEFUN |GaussianFactorizationPackage| () 337 (SPROG NIL 338 (PROG (#1=#:G492) 339 (RETURN 340 (COND 341 ((LETT #1# 342 (HGET |$ConstructorCache| '|GaussianFactorizationPackage|)) 343 (|CDRwithIncrement| (CDAR #1#))) 344 ('T 345 (UNWIND-PROTECT 346 (PROG1 347 (CDDAR 348 (HPUT |$ConstructorCache| 349 '|GaussianFactorizationPackage| 350 (LIST 351 (CONS NIL 352 (CONS 1 353 (|GaussianFactorizationPackage;|)))))) 354 (LETT #1# T)) 355 (COND 356 ((NOT #1#) 357 (HREM |$ConstructorCache| 358 '|GaussianFactorizationPackage|)))))))))) 359 360(DEFUN |GaussianFactorizationPackage;| () 361 (SPROG ((|dv$| NIL) ($ NIL) (|pv$| NIL)) 362 (PROGN 363 (LETT |dv$| '(|GaussianFactorizationPackage|)) 364 (LETT $ (GETREFV 63)) 365 (QSETREFV $ 0 |dv$|) 366 (QSETREFV $ 3 (LETT |pv$| (|buildPredVector| 0 0 NIL))) 367 (|haddProp| |$ConstructorCache| '|GaussianFactorizationPackage| NIL 368 (CONS 1 $)) 369 (|stuffDomainSlots| $) 370 (SETF |pv$| (QREFELT $ 3)) 371 (QSETREFV $ 13 372 (|ModularRing| (|Integer|) (|Integer|) 373 (CONS (|function| |GAUSSFAC;reduction|) $) 374 (CONS (|function| |GAUSSFAC;merge|) $) 375 (CONS (|function| |GAUSSFAC;exactquo|) $))) 376 (QSETREFV $ 17 (SPADCALL 1 1 (QREFELT $ 16))) 377 $))) 378 379(MAKEPROP '|GaussianFactorizationPackage| '|infovec| 380 (LIST 381 '#(NIL NIL NIL NIL NIL NIL (|Integer|) (0 . |positiveRemainder|) 382 (|Union| $ '"failed") (6 . |exquo|) 383 (|Record| (|:| |coef1| $) (|:| |coef2| $)) (|Union| 10 '"failed") 384 (12 . |extendedEuclidean|) '|FMod| (19 . |One|) (|Complex| 6) 385 (23 . |complex|) '|fact2| (29 . |reduce|) (|Boolean|) (35 . =) 386 (|NonNegativeInteger|) (41 . ^) (47 . ~=) (|PositiveInteger|) 387 (53 . ^) (59 . |coerce|) (|Factored| 6) 388 (|IntegerFactorizationPackage| 6) (64 . |factor|) (69 . |unit|) 389 (|Union| '"nil" '"sqfr" '"irred" '"prime") 390 (|Record| (|:| |flag| 31) (|:| |factor| 6) (|:| |exponent| 21)) 391 (|List| 32) (74 . |factorList|) (79 . ^) (85 . *) (|List| 6) 392 (91 . |elt|) (97 . |conjugate|) 393 (|Record| (|:| |flag| 31) (|:| |factor| 15) (|:| |exponent| 21)) 394 (|List| 40) (|Factored| 15) (102 . |makeFR|) (108 . |Zero|) 395 (112 . |Zero|) (116 . =) (122 . |primeFactor|) (128 . |real|) 396 (133 . |imag|) (138 . |unit|) (143 . |factorList|) (148 . |One|) 397 (152 . ~=) (158 . |quo|) (164 . |gcd|) (170 . ~=) 398 |GAUSSFAC;factor;CF;7| |GAUSSFAC;sumSquares;IL;8| (176 . |norm|) 399 (|IntegerPrimesPackage| 6) (181 . |prime?|) 400 |GAUSSFAC;prime?;CB;9|) 401 '#(|sumSquares| 186 |prime?| 191 |factor| 196) 'NIL 402 (CONS (|makeByteWordVec2| 1 '(0)) 403 (CONS '#(NIL) 404 (CONS 405 '#((|Join| 406 (|mkCategory| 407 (LIST 408 '((|factor| 409 ((|Factored| (|Complex| (|Integer|))) 410 (|Complex| (|Integer|)))) 411 T) 412 '((|sumSquares| 413 ((|List| (|Integer|)) (|Integer|))) 414 T) 415 '((|prime?| 416 ((|Boolean|) (|Complex| (|Integer|)))) 417 T)) 418 (LIST) NIL NIL))) 419 (|makeByteWordVec2| 62 420 '(2 6 0 0 0 7 2 6 8 0 0 9 3 6 11 0 421 0 0 12 0 13 0 14 2 15 0 6 6 16 2 422 13 0 6 6 18 2 13 19 0 0 20 2 13 0 423 0 21 22 2 13 19 0 0 23 2 13 0 0 424 24 25 1 13 6 0 26 1 28 27 6 29 1 425 27 6 0 30 1 27 33 0 34 2 15 0 0 426 21 35 2 15 0 0 0 36 2 37 6 0 6 38 427 1 15 0 0 39 2 42 0 15 41 43 0 13 428 0 44 0 15 0 45 2 15 19 0 0 46 2 429 42 0 15 21 47 1 15 6 0 48 1 15 6 430 0 49 1 42 15 0 50 1 42 41 0 51 0 431 15 0 52 2 6 19 0 0 53 2 15 0 0 0 432 54 2 15 0 0 0 55 2 15 19 0 0 56 1 433 15 6 0 59 1 60 19 6 61 1 0 37 6 434 58 1 0 19 15 62 1 0 42 15 57))))) 435 '|lookupComplete|)) 436 437(MAKEPROP '|GaussianFactorizationPackage| 'NILADIC T) 438