\documentclass{article}
\usepackage{open-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
      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}