/usr/share/axiom-20170501/src/algebra/BRILL.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | )abbrev package BRILL BrillhartTests
++ Author: Frederic Lehobey, James H. Davenport
++ Date Created: 28 June 1994
++ Date Last Updated: 11 July 1997
++ 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
++ Description:
++ This package has no description
BrillhartTests(UP) : SIG == CODE where
Z ==> Integer
UP: UnivariatePolynomialCategory Z
N ==> NonNegativeInteger
SIG ==> 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.
CODE ==> 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
(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))
|