diff options
Diffstat (limited to 'src/algebra/cyclotom.spad.pamphlet')
| -rw-r--r-- | src/algebra/cyclotom.spad.pamphlet | 109 |
1 files changed, 109 insertions, 0 deletions
diff --git a/src/algebra/cyclotom.spad.pamphlet b/src/algebra/cyclotom.spad.pamphlet new file mode 100644 index 00000000..1d8c77df --- /dev/null +++ b/src/algebra/cyclotom.spad.pamphlet @@ -0,0 +1,109 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra cyclotom.spad} +\author{The Axiom Team} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{package CYCLOTOM CyclotomicPolynomialPackage} +<<package CYCLOTOM CyclotomicPolynomialPackage>>= +)abbrev package CYCLOTOM CyclotomicPolynomialPackage +++ This package \undocumented{} +CyclotomicPolynomialPackage: public == private where + SUP ==> SparseUnivariatePolynomial(Integer) + LSUP ==> List(SUP) + NNI ==> NonNegativeInteger + FR ==> Factored SUP + IFP ==> IntegerFactorizationPackage Integer + + public == with + cyclotomicDecomposition: Integer -> LSUP + ++ cyclotomicDecomposition(n) \undocumented{} + cyclotomic: Integer -> SUP + ++ cyclotomic(n) \undocumented{} + cyclotomicFactorization: Integer -> FR + ++ cyclotomicFactorization(n) \undocumented{} + + private == add + cyclotomic(n:Integer): SUP == + x,y,z,l: SUP + g := factors factor(n)$IFP + --Now, for each prime in the factorization apply recursion + l := monomial(1,1) - monomial(1,0) + for u in g repeat + l := (monicDivide(multiplyExponents(l,u.factor::NNI),l)).quotient + if u.exponent>1 then + l := multiplyExponents(l,((u.factor)**((u.exponent-1)::NNI))::NNI) + l + + cyclotomicDecomposition(n:Integer):LSUP == + x,y,z: SUP + l,ll,m: LSUP + rr: Integer + g := factors factor(n)$IFP + l := [monomial(1,1) - monomial(1,0)] + --Now, for each prime in the factorization apply recursion + for u in g repeat + m := [(monicDivide( + multiplyExponents(z,u.factor::NNI),z)).quotient for z in l] + for rr in 1..(u.exponent-1) repeat + l := append(l,m) + m := [multiplyExponents(z,u.factor::NNI) for z in m] + l := append(l,m) + l + + cyclotomicFactorization(n:Integer):FR == + f : SUP + fr : FR := 1$FR + for f in cyclotomicDecomposition(n) repeat + fr := fr * primeFactor(f,1$Integer) + fr + +@ +\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 CYCLOTOM CyclotomicPolynomialPackage>> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} |