001/*
002 * $Id$
003 */
004
005package edu.jas.ufd;
006
007
008import java.io.Serializable;
009import java.util.List;
010import java.util.SortedMap;
011
012import edu.jas.poly.GenPolynomial;
013import edu.jas.structure.GcdRingElem;
014
015
016/**
017 * Factorization algorithms interface.
018 * <p>
019 * <b>Usage:</b> To create objects that implement the <code>Factorization</code>
020 * interface use the <code>FactorFactory</code>. It will select an appropriate
021 * implementation based on the types of polynomial coefficients C. To obtain an
022 * implementation use <code>getImplementation()</code>, it returns an object of
023 * a class which extends the <code>FactorAbstract</code> class which implements
024 * the <code>Factorization</code> interface.
025 * <p>
026 * 
027 * <pre>
028 * Factorization&lt;CT&gt; engine;
029 * engine = FactorFactory.&lt;CT&gt; getImplementation(cofac);
030 * c = engine.factors(a);
031 * </pre>
032 * <p>
033 * For example, if the coefficient type is BigInteger, the usage looks like
034 * 
035 * <pre>
036 * BigInteger cofac = new BigInteger();
037 * Factorization&lt;BigInteger&gt; engine;
038 * engine = FactorFactory.getImplementation(cofac);
039 * Sm = engine.factors(poly);
040 * </pre>
041 * 
042 * @author Heinz Kredel
043 * @see edu.jas.ufd.FactorFactory#getImplementation
044 */
045
046public interface Factorization<C extends GcdRingElem<C>> extends Serializable {
047
048
049    /**
050     * GenPolynomial test if is irreducible.
051     * @param P GenPolynomial.
052     * @return true if P is irreducible, else false.
053     */
054    public boolean isIrreducible(GenPolynomial<C> P);
055
056
057    /**
058     * GenPolynomial test if a non trivial factorization exists.
059     * @param P GenPolynomial.
060     * @return true if P is reducible, else false.
061     */
062    public boolean isReducible(GenPolynomial<C> P);
063
064
065    /**
066     * GenPolynomial test if is squarefree.
067     * @param P GenPolynomial.
068     * @return true if P is squarefree, else false.
069     */
070    public boolean isSquarefree(GenPolynomial<C> P);
071
072
073    /**
074     * GenPolynomial factorization of a squarefree polynomial.
075     * @param P squarefree and primitive! or monic! GenPolynomial.
076     * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i.
077     */
078    public List<GenPolynomial<C>> factorsSquarefree(GenPolynomial<C> P);
079
080
081    /**
082     * GenPolynomial factorization.
083     * @param P GenPolynomial.
084     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
085     *         p_i**e_i.
086     */
087    public SortedMap<GenPolynomial<C>, Long> factors(GenPolynomial<C> P);
088
089
090    /**
091     * GenPolynomial factorization ignoring multiplicities.
092     * @param P GenPolynomial.
093     * @return [p_1, ..., p_k] with P = prod_{i=1,...,k} p_i**{e_i} for some
094     *         e_i.
095     */
096    public List<GenPolynomial<C>> factorsRadical(GenPolynomial<C> P);
097
098
099    /**
100     * GenPolynomial greatest squarefree divisor.
101     * @param P GenPolynomial.
102     * @return squarefree(P).
103     */
104    public GenPolynomial<C> squarefreePart(GenPolynomial<C> P);
105
106
107    /**
108     * GenPolynomial squarefree factorization.
109     * @param P GenPolynomial.
110     * @return [p_1 -&gt; e_1, ..., p_k -&gt; e_k] with P = prod_{i=1,...,k}
111     *         p_i^{e_i} and p_i squarefree.
112     */
113    public SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P);
114
115
116    /**
117     * GenPolynomial is factorization.
118     * @param P GenPolynomial
119     * @param F = [p_1,...,p_k].
120     * @return true if P = prod_{i=1,...,r} p_i, else false.
121     */
122    public boolean isFactorization(GenPolynomial<C> P, List<GenPolynomial<C>> F);
123
124
125    /**
126     * GenPolynomial is factorization.
127     * @param P GenPolynomial.
128     * @param F = [p_1 -&gt; e_1, ..., p_k -&gt; e_k].
129     * @return true if P = prod_{i=1,...,k} p_i**e_i , else false.
130     */
131    public boolean isFactorization(GenPolynomial<C> P, SortedMap<GenPolynomial<C>, Long> F);
132
133}