--* From BMT%WATSON.vnet.ibm.com@yktvmh.watson.ibm.com Thu Jun 24 21:29:00 1993 --* Received: from yktvmh.watson.ibm.com by radical.watson.ibm.com (AIX 3.2/UCB 5.64/900524) --* id AA21659; Thu, 24 Jun 1993 21:29:00 -0400 --* Received: from watson.vnet.ibm.com by yktvmh.watson.ibm.com (IBM VM SMTP V2R3) --* with BSMTP id 9903; Thu, 24 Jun 93 21:29:49 EDT --* Received: from YKTVMH by watson.vnet.ibm.com with "VAGENT.V1.0" --* id --* for asbugs@watson; Thu, 24 Jun 93 21:29:49 -0400 --* Received: from YKTVMH by watson.vnet.ibm.com with "VAGENT.V1.0" --* id 2292; Thu, 24 Jun 1993 21:29:48 EDT --* Received: from cyst.watson.ibm.com by yktvmh.watson.ibm.com (IBM VM SMTP V2R3) --* with TCP; Thu, 24 Jun 93 21:29:48 EDT --* Received: from spadserv.watson.ibm.com by cyst.watson.ibm.com (AIX 3.2/UCB 5.64/900528) --* id AA51296; Thu, 24 Jun 1993 21:30:04 -0400 --* Received: by spadserv.watson.ibm.com (AIX 3.2/UCB 5.64/900524) --* id AA26491; Thu, 24 Jun 1993 21:32:33 -0400 --* Date: Thu, 24 Jun 1993 21:32:33 -0400 --* From: bmt@spadserv.watson.ibm.com --* X-External-Networks: yes --* Message-Id: <9306250132.AA26491@spadserv.watson.ibm.com> --* To: asbugs@watson.ibm.com --* Subject: assertion failed, genfoam.c line 1436 [intfact2.as][28.I (current)] --@ Fixed by: PAB Fri Aug 5 20:33:15 EDT 1994 --@ Tested by: enum1.as --@ Summary: Enumerations being hashed incorrectly, if at all -- PI: now I get the following output: #if 0 3 5 list(47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3) Looking in List(Record(TupleArgs) : ) for cons with code 795653584 Export not found This is the "list of record bug". #endif --> testcomp -l asdem --> testrun -l asdem --Copyright The Numerical Algorithms Group Limited 1991. #include "aslib.as" #library DemoLib "asdem" import from DemoLib macro Boolean == Bit B == Bit N == Integer I == Integer min(aa,bb) == if aa < bb then aa else bb one? aa == aa = 1 Outport == OutPort facFlags ==> 'nil, sqfr, irred, prime' FFE(S) ==> Record(flg:facFlags, fctr:S, xpnt:Integer) Factored(S: BasicType with 1:% ) : with makeFR: (S, List FFE(S)) -> % factorList: % -> List FFE(S) unit: % -> S apply: (Outport, %) -> Outport == add Rep ==> Record(unit:S, faclist:List FFE(S)) import from Rep makeFR(u:S, lffe:List FFE(S)):% == per [u, lffe] factorList(x:%):List FFE(S) == apply(rep(x),faclist) unit(x:%):S == apply(rep(x),unit) apply(p:Outport, f:%): Outport == import from String import from S import from List FFE(S) import from FFE(S) import from 'xpnt' import from 'fctr' import from I if unit(f) ~= 1 then p:=p(unit f) for fac in factorList f repeat p:=p(" ")((fac.fctr)@S) if fac.xpnt ~= 1@I then p:=p("^")((fac.xpnt)@I) p --% IntegerFactorizationPackage -- recoded MBM Nov/87 +++ This Package contains basic methods for integer factorization. +++ The factor operation employs trial division up to 10,000. It +++ then tests to see if n is a perfect power before using Pollards +++ rho method. Because Pollards method may fail, the result +++ of factor may contain composite factors. We should also employ +++ Lenstra's elliptic curve method. B ==> Bit FF ==> Factored I LMI ==> ListMultiDictionary I IntegerFactorizationPackage: with factor : I -> FF ++ factor(n) returns the full factorization of integer n squareFree : I -> FF ++ squareFree(n) returns the square free factorization of integer n BasicMethod : I -> FF ++ BasicMethod(n) returns the factorization ++ of integer n by trial division PollardSmallFactor: I -> Partial(I) ++ PollardSmallFactor(n) returns a factor ++ of n or "failed" if no one is found == add import from Segment I import from IntegerRoots import from IntegerPrimesPackage import from Partial I import from 'nil,sqfr,irred,prime' import from FFE(I) import from List(FFE(I)) import from FF import from 'xpnt' concat!(l:List FFE I, v:FFE I):List FFE I == concat!(l, cons(v,nil)) BasicSieve: (I, I) -> FF squareFree(n:I):FF == if n<0 then (m := -n; u:I := -1) else (m := n; u := 1) (m > 1) and (not(failed? (v := perfectSqrt m))) => l := factorList(sv := squareFree(retract v)) for rec in generator l repeat rec.xpnt := 2 * rec.xpnt makeFR(u * unit sv, l) lim := 1 + approxNthRoot(m,3) lim > 100000 => makeFR(u, factorList factor m) x := BasicSieve(m, lim) y := one? unit x => factorList x concat_!(factorList x, [sqfr,unit(x),1]$FFE(I)) makeFR(u, y) -- Pfun(y: I,n: I): I == (y**2 + 5) rem n PollardSmallFactor(n:I):Partial(I) == -- Use the Brent variation m := 100 y:I := random(n)$RandomNumberSource r:I := 1 q:I := 1 G:I := 1 while G <= 1 repeat x:I := y for i in 1..r repeat y := (y*y+5) rem n q := (q*abs(x-y)) rem n k:I := 0 while not( (k>=r) or (G>1)) repeat ys:I := y for i in 1..min(m,r-k) repeat y := (y*y+5) rem n q := q*abs(x-y) rem n G := gcd(q,n) k := k+m r := 2*r if G=n then while G<=1 repeat ys := (ys*ys+5) rem n G := gcd(abs(x-ys),n) G=n => failed G::Partial(I) BasicSieve(r:I, lim:I):FF == import from List(I) l:List(I) := [1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6] concat_!(l, rest rest rest l) d := 2 n := r ls := empty()$List(FFE(I)) for s in l repeat d > lim => return makeFR(n, ls) if n1 then ls := concat_!(ls, [prime,n,1]$FFE(I)) return makeFR(1, ls) m:I:=0 for mm in 1.. while zero?(n rem d) repeat (n := n quo d; m:=mm) if m>0 then ls := concat_!(ls, [prime,d, m]$FFE(I)) d := d+s never BasicMethod(n:I):FF == local u:I if n<0 then (m := -n; u := -1) else (m := n; u := 1) x := BasicSieve(m, 1 + approxSqrt(m)$IntegerRoots) makeFR(u, factorList x) factor(m:I):FF == local u:I zero? m => makeFR(m,nil) if negative? m then (n := -m; u := -1) else (n := m; u := 1) bfac := BasicSieve(n, 10000) flb := factorList bfac import from List(FFE I) import from String one?(n := unit bfac) => makeFR(u, flb) a:LMI := dictionary() -- numbers yet to be factored b:LMI := dictionary() -- prime factors found f:LMI := dictionary() -- number which could not be factored insert_!(n, a) while not empty? a repeat n := inspect a; c:SingleInteger := count(n, a); remove_!(n, a) prime?(n)$IntegerPrimesPackage => insert_!(n, b, c) -- test for a perfect power (s :Record(base:I, exponent:I) := perfectNthRoot n).exponent > 1 => insert_!(s.base, a, c * retract s.exponent) not(failed? (dd := PollardSmallFactor n)) => d := retract dd for m:SingleInteger in 0$SingleInteger.. while zero?(n rem d) repeat n := n quo d insert_!(d, a, retract(m) * c) if n > 1 then insert_!(n, a, c) -- an elliptic curve factorization attempt should be made here insert_!(n, f, c) -- insert prime factors found while not empty? b repeat n := inspect b; c := count(n, b); remove_!(n, b) flb := concat_!(flb, [prime,n,c::I]$FFE(I)) -- insert non-prime factors found while not empty? f repeat n := inspect f; c := count(n, f); remove_!(n, f) flb := concat_!(flb, [nil,n,c::I]$FFE(I)) makeFR(u, flb) #assert TestRun #if TestRun import from I a:I:=3 print(a)() import from IntegerPrimesPackage print(nextPrime a)() import from List(I) print(primes(3,50))() import from IntegerFactorizationPackage import from Factored(I) a:=50 print(factor a)() print(factor 6)() print(factor 2349587234)() print(factor 23434534)() #endif