On Conditional Probabilities of Factoring Quadratics

Thomas Beatty, Gabriela von Linden

Department of Mathematics, Florida Gulf Coast University, Fort Myers, FL, USA.

DOI: 10.4236/apm.2020.103008                

Abstract

Factoring quadratics over Z is a staple of introductory algebra and textbooks tend to create the impression that doable factorizations are fairly common. To the contrary, if coefficients of a general quadratic are selected randomly without restriction, the probability that a factorization exists is zero. We achieve a specific quantification of the probability of factoring quadratics by taking a new approach that considers the absolute size of coefficients to be a parameter n. This restriction allows us to make relative likelihood estimates based on finite sample spaces. Our probability estimates are then conditioned on the size parameter n and the behavior of the conditional estimates may be studied as the parameter is varied. Specifically, we enumerate how many formal factored expressions could possibly correspond to a quadratic for a given size parameter. The conditional probability of factorization as a function of n is just the ratio of this enumeration to the total number of possible quadratics consistent with n. This approach is patterned after the well-known case where factorizations are carried out over a finite field. We review the finite field method as background for our method of dealing with Z [x]. The monic case is developed independently of the general case because it is simpler and the resulting probability estimating formula is more accurate. We conclude with a comparison of our theoretical probability estimates with exact data generated by a computer search for factorable quadratics corresponding to various parameter values.

Keywords

Factorization, Polynomial, Quadratic, Integers, Rational Numbers, Monic, Modular Arithmetic, Conditional Probability

1. Introduction

This paper presents the preliminary results of a broader program to estimate the probabilities of factoring more general polynomials over $\mathbb{Z}$. We anticipate that subsequent research will develop along the lines suggested by the quadratic case investigated here, specifically by using the method of parameterizing the maximum absolute value of coefficients and correlating the conditional probabilities of factorization with the size of the parameter.

The probability that a given general quadratic $\alpha x^2+\beta x+\gamma \in \mathbb{Z}\left[x\right]$ can be factored depends heavily on the commensurability of the coefficients [1] [2] [3]. Loosely speaking, if the coefficients are all about the same size in absolute value, and that size is small, the existence of a factorization is relatively more likely than otherwise. Our intention is to quantify this phenomenon. Dealing with the infinite number of choices available for coefficients is a problem. We sidestep this obstacle by adapting the method used to determine the probability of factorization of quadratics over finite fields. Briefly, we establish a cutoff, or size parameter n, for the absolute value of any coefficients appearing in any of the quadratics we wish to study. This makes the number of quadratics under consideration finite as well as the number of formal factored expressions that could possibly yield such a quadratic. Then the classical probability is just the ratio of the number of admissible factored expressions to the total number of quadratics which conform to the cutoff. This probability $P\left(n\right)$ is, of course, a conditional probability given that the coefficients do not exceed n in absolute value. So the infinite character of the problem is initially made finitary where calculations can be done and then can be recovered by allowing n to approach infinity.

We consider three cases, the first of which, factoring quadratics over finite fields, is well-known [4]. For factoring quadratics over $\mathbb{Z}$, we split the discussion into two parts: 1) the monic case, and 2) the general case. For simplicity we consider quadratics in $\mathbb{Z}\left[x\right]$ that have non-negative roots.

Figure 1 shows factorization probabilities calculated by the computer search. Currently we have no formula that estimates the case $a{x}^2+bx+c\in \mathbb{Z}\left[x\right]$ with $\alpha \ne 0$ other than curve fitting. The trend in the graph in Figure 1 is borne out by the following proposition.

Proposition 0

If $a\mathrm{,}b\mathrm{,}c\in \mathbb{Z}$ are selected randomly without restriction, then the probability of factoring $a{x}^2+bx+c$ over $\mathbb{Z}$ is zero.

Proof. Suppose we are given $a{x}^2+bx+c$ with $a\mathrm{,}b\mathrm{,}c\in \mathbb{Z}$ selected at random. This quadratic factors over $\mathbb{Q}$, hence $\mathbb{Z}$ by Gauss’ Lemma, if the discriminant $\Delta =b^2-4ac$ is a perfect square. We ask what is the probability that $\Delta$ is a perfect square if a and b have been selected and c is provisionally allowed to range over $\left[-n\mathrm{,}n\right]$ for some $n\in \mathbb{N}$. Then there are $2n+1$ possible values of $\Delta$ spread over an interval of length $\left|8an\right|$. The largest possible number of perfect squares in such an interval would occur when none of the interval intersected the open left half line and where the arithmetic density of squares was the greatest. This would occur if the interval were exactly $\left[\mathrm{0,}\left|8an\right|\right]$. The number of squares in this interval does not exceed $\sqrt{\left|8an\right|}$. The classical probability that

Figure 1. $P\left(n\right)$ is the probability of factoring $a{x}^2+bx+c$ with $\left|a\right|\mathrm{,}\left|b\right|\mathrm{,}\left|c\right|\le n$.

one of these squares coincides with a value of $\Delta$ is therefore no more than $\frac{\sqrt{\left|8an\right|}}{2n+1}<\sqrt{2}\left|a\right|\frac{1}{\sqrt{n}}$. As the provisional restriction that $c\in \left[-n\mathrm{,}n\right]$ is relaxed by allowing $n\to \infty$, we see $\sqrt{2}\left|a\right|\frac{1}{\sqrt{n}}\to 0$. It follows that the probability that $\Delta$ is a perfect square, and therefore $a{x}^2+bx+c$ is factorable over $\mathbb{Z}$, is zero in the limit, which corresponds to no restrictions at all on c. Since this is true for any triple $\left(a\mathrm{,}b\mathrm{,}c\right)$, the proposition is established.

We wish to have a more granular understanding of the way in which factorability depends on commensurability of coefficients. Our approach to this question is motivated by solving the factorization probability problem in the context of finite fields, which we review below.

2. Factoring Over $GF(pn)$

Suppose we are given a random monic quadratic over the finite field $GF\left(p\right)$. What is the likelihood that it factors [5] ?

2.1. Proposition 1

If $f\left(x\right)=x^2+\alpha x+\beta$ and $\alpha \mathrm{,}\beta \in GF\left(p\right)$, then the probability $P_p$ of factoring $f\left(x\right)$ over $GF\left(p\right)$ is $\frac{1}{2}+\frac{1}{2p}$.

Proof. There are $p^2$ possible pairs of coefficients, hence $p^2$ distinct quadratics. On the other hand, if f factors as $\left(x-r_1\right)\left(x-r_2\right)$, then there are p factorizations where $r_1=r_2$ and $\left(\begin{array}{c}p\\ 2\end{array}\right)$ distinct factorizations where $r_1\ne r_2$, allowing for interchanging the factors. $P_p$ is the ratio of possible factorizations to possible quadratics, so $P_p=\frac{p+\frac{p\left(p-1\right)}{2}}{p^2}=\frac{1}{2}+\frac{1}{2p}$.

Now let us generalize to an arbitrary quadratic.

2.2. Corollary 1-1

If $f\left(x\right)=\lambda x^2+\alpha x+\beta$ and $\lambda \left(\ne 0\right)\mathrm{,}\alpha \mathrm{,}\beta \in GF\left(p\right)$, then the probability $P_p$ of factoring $f\left(x\right)$ over $GF\left(p\right)$ is $\frac{1}{2}+\frac{1}{2p}$.

Proof. Evidently there are $\left(p-1\right)p^2$ possible triples of coefficients, but we can mimic the above proof by rewriting $f\left(x\right)=\lambda \left(x^2+{\lambda }^{-1}\alpha x+{\lambda }^{-1}\beta \right)=\lambda \left(x^2+{\alpha }^{\prime }x+{\beta }^{\prime }\right)$. Now the possible factorizations would look like $\lambda \left(x-r_1\right)\left(x-r_2\right)$. Once again, the probability of factoring a random quadratic, not necessarily monic, would be $P_p=\frac{\left(p-1\right)\left(\frac{p^2+p}{2}\right)}{\left(p-1\right)p^2}=\frac{1}{2}+\frac{1}{2p}$.

2.3. Corollary 1-2

If $f\left(x\right)=\lambda x^2+\alpha x+\beta$ and $\lambda \left(\ne 0\right)\mathrm{,}\alpha \mathrm{,}\beta \in GF\left(p^n\right)$, then the probability $P_{p^n}$ of factoring $f\left(x\right)$ over $GF\left(p^n\right)$ is $\frac{1}{2}+\frac{1}{2p^n}$.

Proof. Following the proof for the preceding, we have $\left(p^n-1\right)p^{2n}$ possible triples of coefficients, and $\left(p^n-1\right)\left[p^n+\frac{p^n\left(p^n-1\right)}{2}\right]=\left(p^n-1\right)\left(\frac{p^{2n}+p^n}{2}\right)$ possible factorizations. Hence $P_{p^n}=\frac{\left(p^n-1\right)\left(\frac{p^{2n}+p^n}{2}\right)}{\left(p^n-1\right)p^{2n}}=\frac{1}{2}+\frac{1}{2p^n}$.

2.4. Corollary 1-3

The limit as $p\to \infty$ of the probability $P_{p^n}$ of factoring a quadratic over $GF\left(p^n\right)$ is $\frac{1}{2}$.

Proof. This follows immediately from the fact that the limit as $p\to \infty$ of the expression in Corollary 1-2 is independent of n.

The situation we see embodied in Proposition 1 and its corollaries is somewhat unexpected (at least the first time it is considered) and in any case very different from factoring over $\mathbb{Z}$. It is a mildly entertaining exercise in experimental mathematics to choose a large prime p and ask a computer algebra system to factor several random quadratics with large coefficients modulo p. Superficially, since p is large, it seems that the chances for a factorization would be about the same as if the factorization were to be done over $\mathbb{Z}$, namely poor. But in the long run, about half of the test examples result in factorizations. Although it would defeat the whole purpose of our discussion of the enumeration method for factorization probabilities in the finite field case, a short proof of Proposition 1 can be gotten directly from number theory. The quadratic equation $x^2+\alpha x+\beta =0$ can be simplified by completing the square, leaving a constant on the right hand side. Among the $p-1$ non-zero least residues modulo p,exactly $\frac{p-1}{2}$ are quadratic residues. The constant needs to be a quadratic residue so that roots can be found to construct a factorization. Zero is always a quadratic residue, so there are $\frac{p-1}{2}+1=\frac{p+1}{2}$ quadratic residues in all. On the other hand, there are p least residues modulo p, hence the probability that a randomly chosen least residue is in fact a quadratic residue is $\frac{p+1}{2p}=\frac{1}{2}+\frac{1}{2p}$ as above.

3. Factoring Over $\mathbb{Z}$ -Monic Case

We would like to adapt the same argument for factoring over $\mathbb{Z}$ as we used for finite fields, namely counting up the number of possible distinct factorizations and dividing by the number of distinct quadratic expressions to get a probability of being able to factor. Since $\mathbb{Z}$ is infinite this plan is immediately hobbled [6]. Consider the polynomial $x^2+ax+1$, where $\alpha$ is random. There are only two hopes for factorization: $\alpha =\pm 2$. Yet there are infinitely many choices for $\alpha$, so the probability of factorization is evidently zero. To salvage any insight from this state of affairs, we have to content ourselves with a conditional probability based on limiting how “random” a random quadratic can be. A reasonable choice is to insist that its coefficients be commensurable with its possible zeroes. Clearly $x^2+37x+1$ does not have this property, which is informal at the moment, but which will soon be made precise. On the other hand, both $x^2+x+1$ and $x^2+2x+1$ seem to have it. In one case there is a factorization, in the other not. This conditional probability will be based on a relative likelihood calculation where the commensurability condition is quantified by a parameter. As the parameter increases, the commensurability decreases, and the probability of factorization will tend to zero. The point of our approach is to model the detailed behavior of this process. To introduce the specifics in a simple context, we first consider monic quadratics with the restriction that they have non-negative roots.

Let us define a “window of feasibility” $W\left(n\right)$ in the plane as the rectangle of grid points $\left[\mathrm{0,}n+1\right]\times \left[\mathrm{0,}n\right]\subset {\mathbb{Z}}^2$. Suppose we are given a random $p\left(x\right)\in \mathbb{Z}\left[x\right]$ of the form $x^2-\alpha x+\beta$ with $\alpha \mathrm{,}\beta \ge 0$ and $\beta \le n$. If $p\left(x\right)$ factors as $\left(x-r_1\right)\left(x-r_2\right)$ both roots are nonnegative and $\alpha =r_1+r_2$ and $\beta =r_1{r}_2$. If $\beta >0$ these conditions imply that $\alpha \le n+1$, and in the event $\beta =0$ we impose this condition arbitrarily to ensure that all $p\left(x\right)$ satisfying these conditions can be mapped in the obvious way to $\left(\alpha \mathrm{,}\beta \right)\in W\left(n\right)$. At the moment we have every point in $W\left(n\right)$ as the image of some $p\left(x\right)$ with $\alpha \mathrm{,}\beta \ge 0$. Clearly this is a bijective mapping. We call $W\left(n\right)$ a window of feasibility since any $p\left(x\right)$ with $0<\beta \le n$ and $\alpha >n+1$ is necessarily impossible to factor. The motivation for constructing the window is to exclude those cases which overwhelm ordinary probability calculations. A quadratic inside the window may or may not be factorable, but if not, the reason will not be due to incommensurability of coefficients. Figure 2 shows this situation.

Note that a grid point of the form $\left(\alpha \mathrm{,0}\right)$ corresponds to the quadratic $x^2-\alpha x=x\left(x-\alpha \right)$, so factorization is always possible. A grid point of the form $\left(\mathrm{0,}\beta \right)$, provided $\beta >0$ corresponds to the quadratic $x^2+\beta$, which never factors.

Now denote by $F\left(n\right)$ the grid points in $W\left(n\right)$ corresponding to factorable polynomials. A factorable quadratic mapped to $\left(\alpha \mathrm{,}\beta \right)$ must have $\alpha =r_1+r_2$ and $\beta =r_1{r}_2$ for some $r_1\mathrm{,}{r}_2$. Let us then plot pairs of roots on the $W\left(n\right)$ grid and define $\varphi \left(r_1\mathrm{,}{r}_2\right)=\left(\alpha \mathrm{,}\beta \right)$ as the mapping that associates a root pair to the quadratic which factors with those roots. We will see shortly that there are substantial limitations on which points in $W\left(n\right)$ can be root pairs. In other words,

Figure 2. Window of Feasibility for $n=9$. Grid points in shaded area are possible root pairs.

the domain of $\varphi$ will be relatively small, so surjectivity will clearly be out of the question. We would like $\varphi$ to be injective, and since $\varphi \left(r_1\mathrm{,}{r}_2\right)=\varphi \left(r_2\mathrm{,}{r}_1\right)$ we impose the condition $r_2\le r_1$ without loss of generality. Graphically, this amounts to eliminating all root pairs strictly above the line $r_2=r_1$. Now $W\left(n\right)\backslash \left\{\left(r_1\mathrm{,}{r}_2\right)\mathrm{<mo>\; :\; </mo>}{r}_2\le r_1\right\}$ is still not $F\left(n\right)$ since there is another important condition on the root pairs, namely $r_1{r}_2\le n$. The only admissible root pair grid points whenever $r_2>0$ are also below the hyperbola $r_2=\frac{n}{r_1}$. This is also true trivially if $r_2=0$ so the hyperbola is an upper bound for all root pairs corresponding to factorable quadratics. Now we estimate the number of points in $F\left(n\right)$ by calculating the area inside the region of the plane defined by the line $r_2=0$, the line $r_2=r_1$, and the hyperbola $r_2=\frac{n}{r_1}$. The area of this region is $A={\displaystyle \underset{0}{\overset{\sqrt{n}}{\int }}\left(r_1\right)\text{d}{r}_1}+{\displaystyle \underset{\sqrt{n}}{\overset{n+1}{\int }}\left(\frac{n}{r_1}\right)\text{d}{r}_1}=\frac{nlnn+3n}{2}$. We estimate the number of grid points in $F\left(n\right)$ by assuming one grid point per unit of area. This estimate is asymptotically exact. Now $W\left(n\right)$ has $\left(n+1\right)\left(n+2\right)$ total grid points. Finally, our conditional probability estimate is $\frac{nlnn+3n}{2\left(n+1\right)\left(n+2\right)}$. We have proved:

3.1. Proposition 2

Given a random quadratic in $\mathbb{Z}\left[x\right]$ of the form $x^2-\alpha x+\beta$, where $\alpha \mathrm{,}\beta \ge 0$, the approximate probability $P\left(n\right)$ of factorization, subject to the conditions

$\alpha \le n+1$ and $\beta \le n$ for fixed $n\in \mathbb{N}$, is given by $P\left(n\right)=\frac{nlnn+3n}{2\left(n+1\right)\left(n+2\right)}$.

3.2. Corollary 2-1

With the notation of Proposition 2, $P\left(n\right)$ is asymptotically $\frac{lnn}{2n}$.

Proof. Divide numerator and denominator of $\frac{nlnn+3n}{2\left(n+1\right)\left(n+2\right)}$ by n to get $\frac{lnn+3}{2\left(n+3+\frac{2}{n}\right)}$. Note that for large n we have $lnn\gg 3$ and $n\gg 3+\frac{2}{n}$. Hence $n\gg 1$ implies $P\left(n\right)\approx \frac{lnn}{2n}$.

Unsurprisingly, letting $n\to \infty$ corresponds to $\alpha$ and $\beta$ being chosen completely arbitrarily and we confirm that $li{m}_{n\to \infty }P\left(n\right)=0$ by L’Hôpital’s rule. The rate at which the likelihood of factorization declines is $P^{\prime }\left(n\right)\approx -\frac{lnn}{2n^2}$ for large n, as would be expected.

For perspective, if $n=440$, the corresponding likelihood of factorability $P\left(440\right)\approx \mathrm{1\; <mi>\; \%\; </mi>}$.

4. Factoring over $\mathbb{Z}$ -General Case

Consider the lattice cube $L\left(n\right)={\left[\mathrm{0,}n\right]}^3\subset {\mathbb{Z}}^3$ as the three-dimensional analog of the preceding window of feasibility. The general quadratic [7] $p\left(x\right)=\alpha x^2-\beta x+\gamma \in \mathbb{Z}\left[x\right]$ with $\alpha >0,\beta ,\gamma \ge 0$ can be associated injectively with the point $\left(\alpha \mathrm{,}\beta \mathrm{,}\gamma \right)\in L\left(n\right)$ provided $max\left\{\alpha \mathrm{,}\beta \mathrm{,}\gamma \right\}\le n$. Since $\alpha \ne 0$, there are $\left(n-1\right)n^2$ grid points in $L\left(n\right)$ which represent distinct quadratics of this type. We would like to estimate the number of these which are factorable so that we can calculate the conditional probability $P\left(n\right)$ of factorability in the manner of the finite field and monic cases above. Suppose $p\left(x\right)$ does factor in $\mathbb{Z}$ as $\left(ax-b\right)\left(cx-d\right)$, with $a,c>0$ and $b\mathrm{,}d\ge 0$. Note that the greatest common divisor of $\alpha \mathrm{,}\beta$ and $\gamma$ does not appear as a separate factor but is considered to be bundled into the term $\left(ax-b\right)$. Then $\alpha =ac$, $\beta =bc+ad$, and $\gamma =bd$. Since the maximum $\alpha$ is n, it follows that admissible pairs $\left(a\mathrm{,}c\right)$

would satisfy $c\le \frac{n}{a}$. As in the monic case, we embed ${\mathbb{Z}}^2$ in ${ℝ}^2$, calculate the appropriate area under the given hyperbola, and then assume one grid point (admissible pair) per unit of area with the understanding that this is asymptotically correct. The area in the first quadrant of the ac plane is ${\displaystyle {\int }_1^n}\frac{n\left(\delta a\right)}{a}-n=nlnn-n=n\left(lnn-1\right)$. Since the maximum $\gamma$ is n, but either b or d (or both) could be zero, the appropriate area in the first quadrant of the bd plane would be ${\displaystyle {\int }_1^n}\frac{n\left(\delta b\right)}{b}+n=nlnn+n=n\left(lnn+1\right)$. Evidently there are $\left[n\left(lnn-1\right)\right]\cdot \left[n\left(lnn+1\right)\right]=n^2\left({\left(lnn\right)}^2-1\right)=F\left(n\right)$ expressions of the form $\left(ax-b\right)\left(cx-d\right)$ which could factor the quadratic $\alpha x^2-\beta x+\gamma$ subject to the constraints imposed on those coefficients. Certainly not every point in $L\left(n\right)$ corresponds to a factorable quadratic, but we can be assured that any points which are associated with a factorable quadratic have a factorization counted by $F\left(n\right)$. Since the factor pairs commute, we divide $F\left(n\right)$ by two and it follows that the conditional probability of factorization is estimated by $P\left(n\right)=\frac{F\left(n\right)}{2n^3}=\frac{n^2\left({\left(lnn\right)}^2-1\right)}{2n^3}=\frac{{\left(lnn\right)}^2-1}{2n}$.

We have proved:

4.1. Proposition 3

Given a random quadratic in $\mathbb{Z}\left[x\right]$ of the form $\alpha x^2-\beta x+\gamma$, where $\alpha >0,\beta ,\gamma \ge 0$ and $max\left\{\alpha \mathrm{,}\beta \mathrm{,}\gamma \right\}\le n$, an estimate for the probability $P\left(n\right)$ of factorization is given by $P\left(n\right)=\frac{{\left(lnn\right)}^2-1}{2n}$.

4.2. Corollary 3-1

With the notation of Proposition 3, $P\left(n\right)$ is asymptotically $\frac{{\left(lnn\right)}^2}{n}$.

Table 1. Actual vs. Calculated-Monic Case.

n = coefficient bound; Calc = calculated P(n); Actual = actual P(n) by computer check.

Table 2. Actual vs. Calculated-General Case.

n = coefficient bound; Calc = calculated P(n); Actual = actual P(n) by computer check.

Figure 3. Probability of factoring P(n) vs. absolute coefficient bound n actual vs. calculated.

Proof. For $n\gg e$, $\frac{{\left(lnn\right)}^2-1}{2n}\approx \frac{{\left(lnn\right)}^2}{2n}$.

As expected, $li{m}_{n\to \infty }P\left(n\right)=0$ again by L’Hôpital’s rule.

5. Summary & Conclusions

We have described two methods for estimating the conditional probability that a random quadratic in $\mathbb{Z}\left[x\right]$ with non-negative bounded coefficients can be factored as a function of the bounding parameter. The simpler case is based on mapping monic quadratics injectively to a two-dimensional lattice in ${\mathbb{Z}}^2$ and enumerating the formal expressions that could possibly represent factorizations of them. The ratio of the number of admissible formal factorizations to the total number of points in the lattice defines the conditional probability of factorization for the given coefficient bound. The more complicated case involves mapping general quadratics to a three-dimensional lattice in ${\mathbb{Z}}^3$ and reprising the calculation for the two-dimensional case. Both methods have their provenance in the problem of calculating the likelihood that a quadratic over a finite field may be factored. In the case of finite fields, only a finite number of polynomials are possible and only a finite number of factorizations can be written, making the calculation a simple ratio. This fails, of course, for $\mathbb{Z}$, but the point of our method is to resurrect the utility of finiteness by imposing a size limitation on coefficients [8].

Table 1 presents a comparison of values from the monic formula for conditional probability given by Proposition 2 with a computer generated census of factorable monic quadratics. There is reasonably close agreement, even for small n. The computer algorithm works by simply checking to see if the quadratic formula yields a rational number. Recall if a polynomial in $\mathbb{Z}\left[x\right]$ factors over $\mathbb{Q}$, then it factors over $\mathbb{Z}$.

Table 2 recaps a similar comparison for the general quadratics in Proposition 3. For the sake of simplicity we have ignored double counting certain factored expressions arising from symmetries (for example if $a=c$ ). This overstates the calculated probability of factorization, especially for small n, so we may regard $P\left(n\right)$ in this case as an upper bound for the true probability. In any case, our formula establishes $P\left(\infty \right)=0$.

Below in Figure 3 a graph of the calculated $P\left(n\right)$ versus n is shown as the continuous curve. The separate data points correspond to Table 1. The expected feature that $li{m}_{n\to \infty }P\left(n\right)=0$ is also evident.

To close on a philosophical note, although factorization of random quadratics over $\mathbb{Z}$ has been shown to be a progressively futile exercise, practicing pattern recognition with doable examples for small n is a worthwhile exercise that no doubt pays dividends elsewhere in mathematics.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Burton, D. (2005) Elementary Number Theory. McGraw-Hill Higher Education, Inc., New York, NY.
[2]	Dummit, D.S. and Foote, R.M. (2014) Abstract Algebra. 3rd Edition, John Wiley and Sons, Inc., Hoboken, NJ.
[3]	Gallian, J. (2010) Contemporary Abstract Algebra. 7th Edition, Cengage Learning.
[4]	Morandi, P. (1996) Field and Galois Theory. Springer, Berlin. https://doi.org/10.1007/978-1-4612-4040-2
[5]	Lenstra, A., Lenstra, H. and Lovász, L. (1982) Factoring Polynomials with Rational Coefficients. Mathematische Annalen, 261, 515-534. https://doi.org/10.1007/BF01457454
[6]	Miller, V.S. (1992) Factoring Polynomials via Relation-Finding. In: Dolev, D., Galil, Z. and Rodeh, M., Eds., Theory of Computing and Systems ISTCS 1992, Lecture Notes in Computer Science, Vol. 601, Springer, Berlin, Heidelberg.
[7]	Hart, W., Hoeij, M. and Novocin, A. (2011) Practical Polynomial Factoring in Polynomial Time. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), San Jose, CA, 163-170. https://doi.org/10.1145/1993886.1993914
[8]	Ostrowski, A.M. (1975) On Multiplication and Factorization of Polynomials I, Aequationes Mathematicae, 13, 201-228. https://doi.org/10.1007/BF01836524