diff options
Diffstat (limited to 'src/algebra/brill.spad.pamphlet')
| -rw-r--r-- | src/algebra/brill.spad.pamphlet | 161 |
1 files changed, 161 insertions, 0 deletions
diff --git a/src/algebra/brill.spad.pamphlet b/src/algebra/brill.spad.pamphlet new file mode 100644 index 00000000..ae69e86c --- /dev/null +++ b/src/algebra/brill.spad.pamphlet @@ -0,0 +1,161 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra brill.spad} +\author{Frederic Lehobey, James H. Davenport} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{package BRILL BrillhartTests} +<<package BRILL BrillhartTests>>= +)abbrev package BRILL BrillhartTests +++ Author: Frederic Lehobey, James H. Davenport +++ Date Created: 28 June 1994 +++ Date Last Updated: 11 July 1997 +++ Basic Operations: brillhartIrreducible? +++ Related Domains: +++ Also See: +++ AMS Classifications: +++ Keywords: factorization +++ Examples: +++ References: +++ [1] John Brillhart, Note on Irreducibility Testing, +++ Mathematics of Computation, vol. 35, num. 35, Oct. 1980, 1379-1381 +++ [2] James Davenport, On Brillhart Irreducibility. To appear. +++ [3] John Brillhart, On the Euler and Bernoulli polynomials, +++ J. Reine Angew. Math., v. 234, (1969), pp. 45-64 + +BrillhartTests(UP): Exports == Implementation where + N ==> NonNegativeInteger + Z ==> Integer + UP: UnivariatePolynomialCategory Z + + Exports ==> with + brillhartIrreducible?: UP -> Boolean -- See [1] + ++ brillhartIrreducible?(p) returns \spad{true} if p can be shown to be + ++ irreducible by a remark of Brillhart, \spad{false} is inconclusive. + brillhartIrreducible?: (UP,Boolean) -> Boolean -- See [1] + ++ brillhartIrreducible?(p,noLinears) returns \spad{true} if p can be + ++ shown to be irreducible by a remark of Brillhart, \spad{false} else. + ++ If noLinears is \spad{true}, we are being told p has no linear factors + ++ \spad{false} does not mean that p is reducible. + brillhartTrials: () -> N + ++ brillhartTrials() returns the number of tests in + ++ \spadfun{brillhartIrreducible?}. + brillhartTrials: N -> N + ++ brillhartTrials(n) sets to n the number of tests in + ++ \spadfun{brillhartIrreducible?} and returns the previous value. + noLinearFactor?: UP -> Boolean -- See [3] p. 47 + ++ noLinearFactor?(p) returns \spad{true} if p can be shown to have no + ++ linear factor by a theorem of Lehmer, \spad{false} else. I insist on + ++ the fact that \spad{false} does not mean that p has a linear factor. + + Implementation ==> add + + import GaloisGroupFactorizationUtilities(Z,UP,Float) + + squaredPolynomial(p:UP):Boolean == + d := degree p + d = 0 => true + odd? d => false + squaredPolynomial reductum p + + primeEnough?(n:Z,b:Z):Boolean == + -- checks if n is prime, with the possible exception of + -- factors whose product is at most b + import Float + bb: Float := b::Float + for i in 2..b repeat + while (d:= n exquo i) case Integer repeat + n:=d::Integer + bb:=bb / i::Float + bb < 1$Float => return false + --- we over-divided, so it can't be prime + prime? n + + brillharttrials: N := 6 + brillhartTrials():N == brillharttrials + + brillhartTrials(n:N):N == + (brillharttrials,n) := (n,brillharttrials) + n + + brillhartIrreducible?(p:UP):Boolean == + brillhartIrreducible?(p,noLinearFactor? p) + + brillhartIrreducible?(p:UP,noLinears:Boolean):Boolean == -- See [1] + zero? brillharttrials => false + origBound := (largeEnough := rootBound(p)+1) + -- see remarks 2 and 4 + even0 := even? coefficient(p,0) + even1 := even? p(1) + polyx2 := squaredPolynomial(p) + prime? p(largeEnough) => true + not polyx2 and prime? p(-largeEnough) => true +-- one? brillharttrials => false + (brillharttrials = 1) => false + largeEnough := largeEnough+1 + primeEnough?(p(largeEnough),if noLinears then 4 else 2) => true + not polyx2 and + primeEnough?(p(-largeEnough),if noLinears then 4 else 2) => true + if odd? largeEnough then + if even0 then largeEnough := largeEnough+1 + else + if even1 then largeEnough := largeEnough+1 + count :=(if polyx2 then 2 else 1)*(brillharttrials-2)+largeEnough + for i in (largeEnough+1)..count repeat + small := if noLinears then (i-origBound)**2 else (i-origBound) + primeEnough?(p(i),small) => return true + not polyx2 and primeEnough?(p(-i),small) => return true + false + + noLinearFactor?(p:UP):Boolean == + (odd? leadingCoefficient p) and (odd? coefficient(p,0)) and (odd? p(1)) + +@ +\section{License} +<<license>>= +--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. +--All rights reserved. +-- +--Redistribution and use in source and binary forms, with or without +--modification, are permitted provided that the following conditions are +--met: +-- +-- - Redistributions of source code must retain the above copyright +-- notice, this list of conditions and the following disclaimer. +-- +-- - Redistributions in binary form must reproduce the above copyright +-- notice, this list of conditions and the following disclaimer in +-- the documentation and/or other materials provided with the +-- distribution. +-- +-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the +-- names of its contributors may be used to endorse or promote products +-- derived from this software without specific prior written permission. +-- +--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +@ +<<*>>= +<<license>> + +<<package BRILL BrillhartTests>> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} |