diff options
Diffstat (limited to 'src/algebra/intfact.spad.pamphlet')
| -rw-r--r-- | src/algebra/intfact.spad.pamphlet | 30 |
1 files changed, 10 insertions, 20 deletions
diff --git a/src/algebra/intfact.spad.pamphlet b/src/algebra/intfact.spad.pamphlet index 8e21b097..a1e08c3b 100644 --- a/src/algebra/intfact.spad.pamphlet +++ b/src/algebra/intfact.spad.pamphlet @@ -112,13 +112,11 @@ IntegerPrimesPackage(I:IntegerNumberSystem): with -- for most n this probability is much greater than 3/4 t := powmod(p, q, n) -- neither of these cases tells us anything --- if not (one? t or t = nm1) then - if not ((t = 1) or t = nm1) then + if not (one? t or t = nm1) then for j in 1..k-1 repeat oldt := t t := mulmod(t, t, n) --- one? t => return true - (t = 1) => return true + one? t => return true -- we have squared someting not -1 and got 1 t = nm1 => leave @@ -131,13 +129,11 @@ IntegerPrimesPackage(I:IntegerNumberSystem): with t := powmod(p, q, n) -- neither of these cases tells us anything if t=nm1 then count2Order(1):=count2Order(1)+1 --- if not (one? t or t = nm1) then - if not ((t = 1) or t = nm1) then + if not (one? t or t = nm1) then for j in 1..k-1 repeat oldt := t t := mulmod(t, t, n) --- one? t => return true - (t = 1) => return true + one? t => return true -- we have squared someting not -1 and got 1 t = nm1 => rootsMinus1:=union(rootsMinus1,oldt) @@ -150,8 +146,7 @@ IntegerPrimesPackage(I:IntegerNumberSystem): with prime? n == n < two => false n < nextSmallPrime => member?(n, smallPrimes) --- not one? gcd(n, productSmallPrimes) => false - not (gcd(n, productSmallPrimes) = 1) => false + not one? gcd(n, productSmallPrimes) => false n < nextSmallPrimeSquared => true nm1 := n-1 @@ -277,8 +272,7 @@ IntegerRoots(I:IntegerNumberSystem): Exports == Implementation where perfectNthRoot n == -- complexity (log log n)**2 (log n)**2 m:NNI --- one? n or zero? n or n = -1 => [n, 1] - (n = 1) or zero? n or n = -1 => [n, 1] + one? n or zero? n or n = -1 => [n, 1] e:NNI := 1 p:NNI := 2 while p::I <= length(n) + 1 repeat @@ -290,15 +284,13 @@ IntegerRoots(I:IntegerNumberSystem): Exports == Implementation where approxNthRoot(a, n) == -- complexity (log log n) (log n)**2 zero? n => error "invalid arguments" --- one? n => a - (n = 1) => a + one? n => a n=2 => approxSqrt a negative? a => odd? n => - approxNthRoot(-a, n) 0 zero? a => 0 --- one? a => 1 - (a = 1) => 1 + one? a => 1 -- quick check for case of large n ((3*n) quo 2)::I >= (l := length a) => two -- the initial approximation must be >= the root @@ -389,8 +381,7 @@ IntegerFactorizationPackage(I): Exports == Implementation where lim > (100000::I) => makeFR(u, factorList factor m) x := BasicSieve(m, lim) y := --- one?(m:= unit x) => factorList x - ((m:= unit x) = 1) => factorList x + one?(m:= unit x) => factorList x (v := perfectSqrt m) case I => concat_!(factorList x, ["sqfr",v,2]$FFE) concat_!(factorList x, ["sqfr",m,1]$FFE) @@ -484,8 +475,7 @@ IntegerFactorizationPackage(I): Exports == Implementation where else (n := m; u := 1) b := BasicSieve(n, 10000::I) flb := factorList b --- one?(n := unit b) => makeFR(u, flb) - ((n := unit b) = 1) => makeFR(u, flb) + one?(n := unit b) => 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 |