Can this algorithm be fixed?
up vote
1
down vote
favorite
Consider the following algorithm from page 240 of this pdf:
Irreducibility-Test(f)
1 $n ← deg(f)$
2 if $X^{p^n} notequiv X (mod f)$
3 $quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $quad$ do if $X^{p^{n/r}} equiv X (mod f)$
6 $quadquad$ then return "no"
7 return "yes"
Now, this algorithm basically checks if $deg(f)$ is the smallest positive integer $d$ such that $ f ,mid, X^{p^d} - X$. The author says, that this implies irreducibility of $f$ and the algorithm relies on this (lines 4 to 7).
However, the assumed implication isn't right, see the answer to my question.
Is this algorithm simply wrong, or did I get something mixed up? If it is wrong, (how) can it be fixed? If it is correct, where is my misunderstanding?
abstract-algebra algorithms finite-fields irreducible-polynomials
asked Nov 21 at 14:40
polynomial_donut
597216
|
show 5 more comments
up vote
1
down vote
favorite
Consider the following algorithm from page 240 of this pdf:
Irreducibility-Test(f)
1 $n ← deg(f)$
2 if $X^{p^n} notequiv X (mod f)$
3 $quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $quad$ do if $X^{p^{n/r}} equiv X (mod f)$
6 $quadquad$ then return "no"
7 return "yes"
Now, this algorithm basically checks if $deg(f)$ is the smallest positive integer $d$ such that $ f ,mid, X^{p^d} - X$. The author says, that this implies irreducibility of $f$ and the algorithm relies on this (lines 4 to 7).
However, the assumed implication isn't right, see the answer to my question.
Is this algorithm simply wrong, or did I get something mixed up? If it is wrong, (how) can it be fixed? If it is correct, where is my misunderstanding?
abstract-algebra algorithms finite-fields irreducible-polynomials
asked Nov 21 at 14:40
polynomial_donut
597216
3
The linked source has non-congruence in line 2 (which makes more sense).
– Andreas Blass
Nov 21 at 15:12
3
Perhaps replacing line 5 by "do if $gcd(x^{p^{n/r}}-x,f)neq 1$" would suffice ? Just a silly thought...
– user120527
Nov 21 at 15:22
@user120527 I think I don't completely get the reasoning behind your suggestion (completely on me, probably). From my understanding, lines 4-6 work to sort out reducible polynomials, but not necessarily all of them - with your line change, irreducible polynomials still 'reach the end', but I don't quite see how all reducible ones would be sorted out.
– polynomial_donut
Nov 21 at 19:05
This algorithm gives the wrong answer if and only if $f$ is a square-free product of lower degree irreducible polynomials $f(x)=p_1(x)p_2(x)cdots p_k(x)$, $p_i$ irreducible for all $i$, such that $n$ is the least common multiple of the degree os the factors $p_i(x)$.
– Jyrki Lahtonen
Nov 22 at 6:28
1
Anyway, as Eric Wofsey's answer explains, any product of a linear, an irreducible quadratic and an irreducible cubic will pass this test $n=3+2+1=6=lcm{3,2,1}$. Similarly a product of distinct irreducible polynomials of degrees $5,2,2,1$ will pass the test as $5+2+2+1=10=lcm{5,2,2,1}$. I don't see a remedy other than to calculate $gcd(f,x^{p^{n/r}}-x)$ in step 5 rather than simply check non-divisibility.
– Jyrki Lahtonen
Nov 22 at 6:45
|
show 5 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Consider the following algorithm from page 240 of this pdf:
Irreducibility-Test(f)
1 $n ← deg(f)$
2 if $X^{p^n} notequiv X (mod f)$
3 $quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $quad$ do if $X^{p^{n/r}} equiv X (mod f)$
6 $quadquad$ then return "no"
7 return "yes"
Now, this algorithm basically checks if $deg(f)$ is the smallest positive integer $d$ such that $ f ,mid, X^{p^d} - X$. The author says, that this implies irreducibility of $f$ and the algorithm relies on this (lines 4 to 7).
However, the assumed implication isn't right, see the answer to my question.
Is this algorithm simply wrong, or did I get something mixed up? If it is wrong, (how) can it be fixed? If it is correct, where is my misunderstanding?
abstract-algebra algorithms finite-fields irreducible-polynomials
asked Nov 21 at 14:40
polynomial_donut
597216
Consider the following algorithm from page 240 of this pdf:
Irreducibility-Test(f)
1 $n ← deg(f)$
2 if $X^{p^n} notequiv X (mod f)$
3 $quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $quad$ do if $X^{p^{n/r}} equiv X (mod f)$
6 $quadquad$ then return "no"
7 return "yes"
Now, this algorithm basically checks if $deg(f)$ is the smallest positive integer $d$ such that $ f ,mid, X^{p^d} - X$. The author says, that this implies irreducibility of $f$ and the algorithm relies on this (lines 4 to 7).
However, the assumed implication isn't right, see the answer to my question.
Is this algorithm simply wrong, or did I get something mixed up? If it is wrong, (how) can it be fixed? If it is correct, where is my misunderstanding?
abstract-algebra algorithms finite-fields irreducible-polynomials
abstract-algebra algorithms finite-fields irreducible-polynomials
asked Nov 21 at 14:40
polynomial_donut
597216
asked Nov 21 at 14:40
polynomial_donut
597216
edited Nov 21 at 16:11
asked Nov 21 at 14:40
polynomial_donut
597216
asked Nov 21 at 14:40
polynomial_donut
597216
asked Nov 21 at 14:40
polynomial_donut
597216
597216
3
The linked source has non-congruence in line 2 (which makes more sense).
– Andreas Blass
Nov 21 at 15:12
3
Perhaps replacing line 5 by "do if $gcd(x^{p^{n/r}}-x,f)neq 1$" would suffice ? Just a silly thought...
– user120527
Nov 21 at 15:22
@user120527 I think I don't completely get the reasoning behind your suggestion (completely on me, probably). From my understanding, lines 4-6 work to sort out reducible polynomials, but not necessarily all of them - with your line change, irreducible polynomials still 'reach the end', but I don't quite see how all reducible ones would be sorted out.
– polynomial_donut
Nov 21 at 19:05
This algorithm gives the wrong answer if and only if $f$ is a square-free product of lower degree irreducible polynomials $f(x)=p_1(x)p_2(x)cdots p_k(x)$, $p_i$ irreducible for all $i$, such that $n$ is the least common multiple of the degree os the factors $p_i(x)$.
– Jyrki Lahtonen
Nov 22 at 6:28
1
Anyway, as Eric Wofsey's answer explains, any product of a linear, an irreducible quadratic and an irreducible cubic will pass this test $n=3+2+1=6=lcm{3,2,1}$. Similarly a product of distinct irreducible polynomials of degrees $5,2,2,1$ will pass the test as $5+2+2+1=10=lcm{5,2,2,1}$. I don't see a remedy other than to calculate $gcd(f,x^{p^{n/r}}-x)$ in step 5 rather than simply check non-divisibility.
– Jyrki Lahtonen
Nov 22 at 6:45
|
show 5 more comments
3
The linked source has non-congruence in line 2 (which makes more sense).
– Andreas Blass
Nov 21 at 15:12
3
Perhaps replacing line 5 by "do if $gcd(x^{p^{n/r}}-x,f)neq 1$" would suffice ? Just a silly thought...
– user120527
Nov 21 at 15:22
@user120527 I think I don't completely get the reasoning behind your suggestion (completely on me, probably). From my understanding, lines 4-6 work to sort out reducible polynomials, but not necessarily all of them - with your line change, irreducible polynomials still 'reach the end', but I don't quite see how all reducible ones would be sorted out.
– polynomial_donut
Nov 21 at 19:05
This algorithm gives the wrong answer if and only if $f$ is a square-free product of lower degree irreducible polynomials $f(x)=p_1(x)p_2(x)cdots p_k(x)$, $p_i$ irreducible for all $i$, such that $n$ is the least common multiple of the degree os the factors $p_i(x)$.
– Jyrki Lahtonen
Nov 22 at 6:28
1
Anyway, as Eric Wofsey's answer explains, any product of a linear, an irreducible quadratic and an irreducible cubic will pass this test $n=3+2+1=6=lcm{3,2,1}$. Similarly a product of distinct irreducible polynomials of degrees $5,2,2,1$ will pass the test as $5+2+2+1=10=lcm{5,2,2,1}$. I don't see a remedy other than to calculate $gcd(f,x^{p^{n/r}}-x)$ in step 5 rather than simply check non-divisibility.
– Jyrki Lahtonen
Nov 22 at 6:45
3
3
The linked source has non-congruence in line 2 (which makes more sense).
– Andreas Blass
Nov 21 at 15:12
The linked source has non-congruence in line 2 (which makes more sense).
– Andreas Blass
Nov 21 at 15:12
3
3
Perhaps replacing line 5 by "do if $gcd(x^{p^{n/r}}-x,f)neq 1$" would suffice ? Just a silly thought...
– user120527
Nov 21 at 15:22
Perhaps replacing line 5 by "do if $gcd(x^{p^{n/r}}-x,f)neq 1$" would suffice ? Just a silly thought...
– user120527
Nov 21 at 15:22
@user120527 I think I don't completely get the reasoning behind your suggestion (completely on me, probably). From my understanding, lines 4-6 work to sort out reducible polynomials, but not necessarily all of them - with your line change, irreducible polynomials still 'reach the end', but I don't quite see how all reducible ones would be sorted out.
– polynomial_donut
Nov 21 at 19:05
@user120527 I think I don't completely get the reasoning behind your suggestion (completely on me, probably). From my understanding, lines 4-6 work to sort out reducible polynomials, but not necessarily all of them - with your line change, irreducible polynomials still 'reach the end', but I don't quite see how all reducible ones would be sorted out.
– polynomial_donut
Nov 21 at 19:05
This algorithm gives the wrong answer if and only if $f$ is a square-free product of lower degree irreducible polynomials $f(x)=p_1(x)p_2(x)cdots p_k(x)$, $p_i$ irreducible for all $i$, such that $n$ is the least common multiple of the degree os the factors $p_i(x)$.
– Jyrki Lahtonen
Nov 22 at 6:28
This algorithm gives the wrong answer if and only if $f$ is a square-free product of lower degree irreducible polynomials $f(x)=p_1(x)p_2(x)cdots p_k(x)$, $p_i$ irreducible for all $i$, such that $n$ is the least common multiple of the degree os the factors $p_i(x)$.
– Jyrki Lahtonen
Nov 22 at 6:28
1
1
Anyway, as Eric Wofsey's answer explains, any product of a linear, an irreducible quadratic and an irreducible cubic will pass this test $n=3+2+1=6=lcm{3,2,1}$. Similarly a product of distinct irreducible polynomials of degrees $5,2,2,1$ will pass the test as $5+2+2+1=10=lcm{5,2,2,1}$. I don't see a remedy other than to calculate $gcd(f,x^{p^{n/r}}-x)$ in step 5 rather than simply check non-divisibility.
– Jyrki Lahtonen
Nov 22 at 6:45
Anyway, as Eric Wofsey's answer explains, any product of a linear, an irreducible quadratic and an irreducible cubic will pass this test $n=3+2+1=6=lcm{3,2,1}$. Similarly a product of distinct irreducible polynomials of degrees $5,2,2,1$ will pass the test as $5+2+2+1=10=lcm{5,2,2,1}$. I don't see a remedy other than to calculate $gcd(f,x^{p^{n/r}}-x)$ in step 5 rather than simply check non-divisibility.
– Jyrki Lahtonen
Nov 22 at 6:45
|
show 5 more comments
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
The algorithm should work out with the change that user120527 suggested in a comment on this question.
If $f$ is irreducible, then if we have $f ,mid, P_d:=X^{q^d} - X$ for some $d > 0$, we know that $deg(f) ,mid, d$ since $P_d$ is the squarefree product of all irreducible polynomials of $mathbb{F}_q[X]$ whose degree divides $d$. Hence, $deg (f) leq d$.
This implies that $f ,notmid, P_{n/r}$ for all prime factors $r$ of $n = deg (f)$, because $deg(f) > deg(f)/r = n/r$, meaning that $f$ will pass through to the end in the algorithm above (note that $f ,notmid, P_{n/r} overset{f, text{prime}}iff gcdleft(f, P_{n/r}) neq 1 right)$.
Conversely, if $f$ is reducible, then we have $f = gh$ where $g$ is irreducible and $h$ is nontrivial. Assuming that the algorithm didn't cancel at line 2, we hence know that $g ,mid, f ,mid, P_{deg(f)}$, so that
$$
deg (g) ,mid, deg (f)
$$
Now, since $h$ is nontrivial we know $deg (g) < deg (f)$, so that with the above, there is a prime factor $r$ of $deg(f)$ such that $deg (g) ,mid, deg(f)/r = n/r$ and then,
$$
g ,mid, P_{n/r} iff gcdleft(g, P_{n/r}right) neq 1 implies gcdleft(f, P_{n/r}right) neq 1
$$
and $f$ will fail the test in line 5 of the changed algorithm here:
Irreducibility-Test(f)
1 $n ← deg(f)$
2 if $X^{p^n} notequiv X (mod f)$
3 $quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $quad$ do if $;mathbf{,textbf{gcd}left(f,, X^{p^{n/r}} - X right) neq 1}$
6 $quadquad$ then return "no"
7 return "yes"
answered Nov 22 at 15:34
polynomial_donut
597216
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
The algorithm should work out with the change that user120527 suggested in a comment on this question.
If $f$ is irreducible, then if we have $f ,mid, P_d:=X^{q^d} - X$ for some $d > 0$, we know that $deg(f) ,mid, d$ since $P_d$ is the squarefree product of all irreducible polynomials of $mathbb{F}_q[X]$ whose degree divides $d$. Hence, $deg (f) leq d$.
This implies that $f ,notmid, P_{n/r}$ for all prime factors $r$ of $n = deg (f)$, because $deg(f) > deg(f)/r = n/r$, meaning that $f$ will pass through to the end in the algorithm above (note that $f ,notmid, P_{n/r} overset{f, text{prime}}iff gcdleft(f, P_{n/r}) neq 1 right)$.
Conversely, if $f$ is reducible, then we have $f = gh$ where $g$ is irreducible and $h$ is nontrivial. Assuming that the algorithm didn't cancel at line 2, we hence know that $g ,mid, f ,mid, P_{deg(f)}$, so that
$$
deg (g) ,mid, deg (f)
$$
Now, since $h$ is nontrivial we know $deg (g) < deg (f)$, so that with the above, there is a prime factor $r$ of $deg(f)$ such that $deg (g) ,mid, deg(f)/r = n/r$ and then,
$$
g ,mid, P_{n/r} iff gcdleft(g, P_{n/r}right) neq 1 implies gcdleft(f, P_{n/r}right) neq 1
$$
and $f$ will fail the test in line 5 of the changed algorithm here:
Irreducibility-Test(f)
1 $n ← deg(f)$
2 if $X^{p^n} notequiv X (mod f)$
3 $quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $quad$ do if $;mathbf{,textbf{gcd}left(f,, X^{p^{n/r}} - X right) neq 1}$
6 $quadquad$ then return "no"
7 return "yes"
answered Nov 22 at 15:34
polynomial_donut
597216
add a comment |
up vote
3
down vote
accepted
The algorithm should work out with the change that user120527 suggested in a comment on this question.
If $f$ is irreducible, then if we have $f ,mid, P_d:=X^{q^d} - X$ for some $d > 0$, we know that $deg(f) ,mid, d$ since $P_d$ is the squarefree product of all irreducible polynomials of $mathbb{F}_q[X]$ whose degree divides $d$. Hence, $deg (f) leq d$.
This implies that $f ,notmid, P_{n/r}$ for all prime factors $r$ of $n = deg (f)$, because $deg(f) > deg(f)/r = n/r$, meaning that $f$ will pass through to the end in the algorithm above (note that $f ,notmid, P_{n/r} overset{f, text{prime}}iff gcdleft(f, P_{n/r}) neq 1 right)$.
Conversely, if $f$ is reducible, then we have $f = gh$ where $g$ is irreducible and $h$ is nontrivial. Assuming that the algorithm didn't cancel at line 2, we hence know that $g ,mid, f ,mid, P_{deg(f)}$, so that
$$
deg (g) ,mid, deg (f)
$$
Now, since $h$ is nontrivial we know $deg (g) < deg (f)$, so that with the above, there is a prime factor $r$ of $deg(f)$ such that $deg (g) ,mid, deg(f)/r = n/r$ and then,
$$
g ,mid, P_{n/r} iff gcdleft(g, P_{n/r}right) neq 1 implies gcdleft(f, P_{n/r}right) neq 1
$$
and $f$ will fail the test in line 5 of the changed algorithm here:
Irreducibility-Test(f)
1 $n ← deg(f)$
2 if $X^{p^n} notequiv X (mod f)$
3 $quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $quad$ do if $;mathbf{,textbf{gcd}left(f,, X^{p^{n/r}} - X right) neq 1}$
6 $quadquad$ then return "no"
7 return "yes"
answered Nov 22 at 15:34
polynomial_donut
597216
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
The algorithm should work out with the change that user120527 suggested in a comment on this question.
If $f$ is irreducible, then if we have $f ,mid, P_d:=X^{q^d} - X$ for some $d > 0$, we know that $deg(f) ,mid, d$ since $P_d$ is the squarefree product of all irreducible polynomials of $mathbb{F}_q[X]$ whose degree divides $d$. Hence, $deg (f) leq d$.
This implies that $f ,notmid, P_{n/r}$ for all prime factors $r$ of $n = deg (f)$, because $deg(f) > deg(f)/r = n/r$, meaning that $f$ will pass through to the end in the algorithm above (note that $f ,notmid, P_{n/r} overset{f, text{prime}}iff gcdleft(f, P_{n/r}) neq 1 right)$.
Conversely, if $f$ is reducible, then we have $f = gh$ where $g$ is irreducible and $h$ is nontrivial. Assuming that the algorithm didn't cancel at line 2, we hence know that $g ,mid, f ,mid, P_{deg(f)}$, so that
$$
deg (g) ,mid, deg (f)
$$
Now, since $h$ is nontrivial we know $deg (g) < deg (f)$, so that with the above, there is a prime factor $r$ of $deg(f)$ such that $deg (g) ,mid, deg(f)/r = n/r$ and then,
$$
g ,mid, P_{n/r} iff gcdleft(g, P_{n/r}right) neq 1 implies gcdleft(f, P_{n/r}right) neq 1
$$
and $f$ will fail the test in line 5 of the changed algorithm here:
Irreducibility-Test(f)
1 $n ← deg(f)$
2 if $X^{p^n} notequiv X (mod f)$
3 $quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $quad$ do if $;mathbf{,textbf{gcd}left(f,, X^{p^{n/r}} - X right) neq 1}$
6 $quadquad$ then return "no"
7 return "yes"
answered Nov 22 at 15:34
polynomial_donut
597216
The algorithm should work out with the change that user120527 suggested in a comment on this question.
If $f$ is irreducible, then if we have $f ,mid, P_d:=X^{q^d} - X$ for some $d > 0$, we know that $deg(f) ,mid, d$ since $P_d$ is the squarefree product of all irreducible polynomials of $mathbb{F}_q[X]$ whose degree divides $d$. Hence, $deg (f) leq d$.
This implies that $f ,notmid, P_{n/r}$ for all prime factors $r$ of $n = deg (f)$, because $deg(f) > deg(f)/r = n/r$, meaning that $f$ will pass through to the end in the algorithm above (note that $f ,notmid, P_{n/r} overset{f, text{prime}}iff gcdleft(f, P_{n/r}) neq 1 right)$.
Conversely, if $f$ is reducible, then we have $f = gh$ where $g$ is irreducible and $h$ is nontrivial. Assuming that the algorithm didn't cancel at line 2, we hence know that $g ,mid, f ,mid, P_{deg(f)}$, so that
$$
deg (g) ,mid, deg (f)
$$
Now, since $h$ is nontrivial we know $deg (g) < deg (f)$, so that with the above, there is a prime factor $r$ of $deg(f)$ such that $deg (g) ,mid, deg(f)/r = n/r$ and then,
$$
g ,mid, P_{n/r} iff gcdleft(g, P_{n/r}right) neq 1 implies gcdleft(f, P_{n/r}right) neq 1
$$
and $f$ will fail the test in line 5 of the changed algorithm here:
Irreducibility-Test(f)
1 $n ← deg(f)$
2 if $X^{p^n} notequiv X (mod f)$
3 $quad$ then return "no"
4 for the prime divisors $r$ of $n$
5 $quad$ do if $;mathbf{,textbf{gcd}left(f,, X^{p^{n/r}} - X right) neq 1}$
6 $quadquad$ then return "no"
7 return "yes"
answered Nov 22 at 15:34
polynomial_donut
597216
edited Nov 22 at 15:55
answered Nov 22 at 15:34
polynomial_donut
597216
answered Nov 22 at 15:34
polynomial_donut
597216
answered Nov 22 at 15:34
polynomial_donut
597216
597216
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3007799%2fcan-this-algorithm-be-fixed%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
The linked source has non-congruence in line 2 (which makes more sense).
– Andreas Blass
Nov 21 at 15:12
3
Perhaps replacing line 5 by "do if $gcd(x^{p^{n/r}}-x,f)neq 1$" would suffice ? Just a silly thought...
– user120527
Nov 21 at 15:22
@user120527 I think I don't completely get the reasoning behind your suggestion (completely on me, probably). From my understanding, lines 4-6 work to sort out reducible polynomials, but not necessarily all of them - with your line change, irreducible polynomials still 'reach the end', but I don't quite see how all reducible ones would be sorted out.
– polynomial_donut
Nov 21 at 19:05
This algorithm gives the wrong answer if and only if $f$ is a square-free product of lower degree irreducible polynomials $f(x)=p_1(x)p_2(x)cdots p_k(x)$, $p_i$ irreducible for all $i$, such that $n$ is the least common multiple of the degree os the factors $p_i(x)$.
– Jyrki Lahtonen
Nov 22 at 6:28
1
Anyway, as Eric Wofsey's answer explains, any product of a linear, an irreducible quadratic and an irreducible cubic will pass this test $n=3+2+1=6=lcm{3,2,1}$. Similarly a product of distinct irreducible polynomials of degrees $5,2,2,1$ will pass the test as $5+2+2+1=10=lcm{5,2,2,1}$. I don't see a remedy other than to calculate $gcd(f,x^{p^{n/r}}-x)$ in step 5 rather than simply check non-divisibility.
– Jyrki Lahtonen
Nov 22 at 6:45