Initial population.

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}