Mixing
Test of irreducibility of a binary polynomial
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
What criteria do we have to efficiently test if a binary polynomial $P(x)$ is irreducible?
Assume $P$ is given as a vector of $n+1$ bits $c_i$, with $c_0=c_n=1$, as $P(x)=displaystylesum_j=0^nc_j,x^j$ .
If $P(x)$ is irreducible, then $x^2^n-1bmod P=1$ (proof: the order of $x$ in the multiplicative group modulo $x$ divides the group order). This can give a quick and certain indication that a polynomial is not irreducible (the test runs in $O(n^3)$ binary operations using $O(n)$ bits of memory with classical algorithms).
Unfortunately, much like the Fermat pseudo-prime test to base 2 has pseudoprimes (OEIS A001567), there are pseudo-primitives to this test. The list to degree 9 inclusive is (not yet at OEIS but soon to become A316970):
$$beginarrayl
1+x+x^4+x^6\
1+x^2+x^5+x^6\
1+x+x^2+x^3+x^4+x^5+x^6\
1+x+x^2+x^4+x^8\
1+x+x^3+x^4+x^5+x^7+x^8\
1+x^4+x^6+x^7+x^8\
dotsendarray$$
How can we make a more selective test? Is there an analog to the strong pseudoprime test?
Update: found the related Rabin's test for polynomial irreducibility over $Bbb F_2$
galois-theory finite-fields irreducible-polynomials
asked Jul 18 at 12:43
fgrieu
534319
add a comment |Â
up vote
1
down vote
favorite
What criteria do we have to efficiently test if a binary polynomial $P(x)$ is irreducible?
Assume $P$ is given as a vector of $n+1$ bits $c_i$, with $c_0=c_n=1$, as $P(x)=displaystylesum_j=0^nc_j,x^j$ .
If $P(x)$ is irreducible, then $x^2^n-1bmod P=1$ (proof: the order of $x$ in the multiplicative group modulo $x$ divides the group order). This can give a quick and certain indication that a polynomial is not irreducible (the test runs in $O(n^3)$ binary operations using $O(n)$ bits of memory with classical algorithms).
Unfortunately, much like the Fermat pseudo-prime test to base 2 has pseudoprimes (OEIS A001567), there are pseudo-primitives to this test. The list to degree 9 inclusive is (not yet at OEIS but soon to become A316970):
$$beginarrayl
1+x+x^4+x^6\
1+x^2+x^5+x^6\
1+x+x^2+x^3+x^4+x^5+x^6\
1+x+x^2+x^4+x^8\
1+x+x^3+x^4+x^5+x^7+x^8\
1+x^4+x^6+x^7+x^8\
dotsendarray$$
How can we make a more selective test? Is there an analog to the strong pseudoprime test?
Update: found the related Rabin's test for polynomial irreducibility over $Bbb F_2$
galois-theory finite-fields irreducible-polynomials
asked Jul 18 at 12:43
fgrieu
534319
1
Isn't testing for non-trivial common divisors, $gcd(P(x),x^2^m-x)$, $m<deg P(x)$, a viable option? The first step in the Euclidean algorithm calls for the remainder of $x^2^m-x$ modulo $P(x)$. This can be done efficiently with square-and-multiply (and the result can be reused when you increment $m$). From that point on you only have "low" degree polynomials, so Euclid runs fast.
– Jyrki Lahtonen
Jul 19 at 7:43
1
Maybe this article has something helpful? On the number of irreducible polynomials with 0,1 coefficients
– Sil
Jul 22 at 15:54
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
What criteria do we have to efficiently test if a binary polynomial $P(x)$ is irreducible?
Assume $P$ is given as a vector of $n+1$ bits $c_i$, with $c_0=c_n=1$, as $P(x)=displaystylesum_j=0^nc_j,x^j$ .
If $P(x)$ is irreducible, then $x^2^n-1bmod P=1$ (proof: the order of $x$ in the multiplicative group modulo $x$ divides the group order). This can give a quick and certain indication that a polynomial is not irreducible (the test runs in $O(n^3)$ binary operations using $O(n)$ bits of memory with classical algorithms).
Unfortunately, much like the Fermat pseudo-prime test to base 2 has pseudoprimes (OEIS A001567), there are pseudo-primitives to this test. The list to degree 9 inclusive is (not yet at OEIS but soon to become A316970):
$$beginarrayl
1+x+x^4+x^6\
1+x^2+x^5+x^6\
1+x+x^2+x^3+x^4+x^5+x^6\
1+x+x^2+x^4+x^8\
1+x+x^3+x^4+x^5+x^7+x^8\
1+x^4+x^6+x^7+x^8\
dotsendarray$$
How can we make a more selective test? Is there an analog to the strong pseudoprime test?
Update: found the related Rabin's test for polynomial irreducibility over $Bbb F_2$
galois-theory finite-fields irreducible-polynomials
asked Jul 18 at 12:43
fgrieu
534319
What criteria do we have to efficiently test if a binary polynomial $P(x)$ is irreducible?
Assume $P$ is given as a vector of $n+1$ bits $c_i$, with $c_0=c_n=1$, as $P(x)=displaystylesum_j=0^nc_j,x^j$ .
If $P(x)$ is irreducible, then $x^2^n-1bmod P=1$ (proof: the order of $x$ in the multiplicative group modulo $x$ divides the group order). This can give a quick and certain indication that a polynomial is not irreducible (the test runs in $O(n^3)$ binary operations using $O(n)$ bits of memory with classical algorithms).
Unfortunately, much like the Fermat pseudo-prime test to base 2 has pseudoprimes (OEIS A001567), there are pseudo-primitives to this test. The list to degree 9 inclusive is (not yet at OEIS but soon to become A316970):
$$beginarrayl
1+x+x^4+x^6\
1+x^2+x^5+x^6\
1+x+x^2+x^3+x^4+x^5+x^6\
1+x+x^2+x^4+x^8\
1+x+x^3+x^4+x^5+x^7+x^8\
1+x^4+x^6+x^7+x^8\
dotsendarray$$
How can we make a more selective test? Is there an analog to the strong pseudoprime test?
Update: found the related Rabin's test for polynomial irreducibility over $Bbb F_2$
galois-theory finite-fields irreducible-polynomials
asked Jul 18 at 12:43
fgrieu
534319
edited Jul 19 at 6:46
asked Jul 18 at 12:43
fgrieu
534319
asked Jul 18 at 12:43
fgrieu
534319
asked Jul 18 at 12:43
fgrieu
534319
534319
1
Isn't testing for non-trivial common divisors, $gcd(P(x),x^2^m-x)$, $m<deg P(x)$, a viable option? The first step in the Euclidean algorithm calls for the remainder of $x^2^m-x$ modulo $P(x)$. This can be done efficiently with square-and-multiply (and the result can be reused when you increment $m$). From that point on you only have "low" degree polynomials, so Euclid runs fast.
– Jyrki Lahtonen
Jul 19 at 7:43
1
Maybe this article has something helpful? On the number of irreducible polynomials with 0,1 coefficients
– Sil
Jul 22 at 15:54
add a comment |Â
1
Isn't testing for non-trivial common divisors, $gcd(P(x),x^2^m-x)$, $m<deg P(x)$, a viable option? The first step in the Euclidean algorithm calls for the remainder of $x^2^m-x$ modulo $P(x)$. This can be done efficiently with square-and-multiply (and the result can be reused when you increment $m$). From that point on you only have "low" degree polynomials, so Euclid runs fast.
– Jyrki Lahtonen
Jul 19 at 7:43
1
Maybe this article has something helpful? On the number of irreducible polynomials with 0,1 coefficients
– Sil
Jul 22 at 15:54
1
1
Isn't testing for non-trivial common divisors, $gcd(P(x),x^2^m-x)$, $m<deg P(x)$, a viable option? The first step in the Euclidean algorithm calls for the remainder of $x^2^m-x$ modulo $P(x)$. This can be done efficiently with square-and-multiply (and the result can be reused when you increment $m$). From that point on you only have "low" degree polynomials, so Euclid runs fast.
– Jyrki Lahtonen
Jul 19 at 7:43
Isn't testing for non-trivial common divisors, $gcd(P(x),x^2^m-x)$, $m<deg P(x)$, a viable option? The first step in the Euclidean algorithm calls for the remainder of $x^2^m-x$ modulo $P(x)$. This can be done efficiently with square-and-multiply (and the result can be reused when you increment $m$). From that point on you only have "low" degree polynomials, so Euclid runs fast.
– Jyrki Lahtonen
Jul 19 at 7:43
1
1
Maybe this article has something helpful? On the number of irreducible polynomials with 0,1 coefficients
– Sil
Jul 22 at 15:54
Maybe this article has something helpful? On the number of irreducible polynomials with 0,1 coefficients
– Sil
Jul 22 at 15:54
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855547%2ftest-of-irreducibility-of-a-binary-polynomial%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
Isn't testing for non-trivial common divisors, $gcd(P(x),x^2^m-x)$, $m<deg P(x)$, a viable option? The first step in the Euclidean algorithm calls for the remainder of $x^2^m-x$ modulo $P(x)$. This can be done efficiently with square-and-multiply (and the result can be reused when you increment $m$). From that point on you only have "low" degree polynomials, so Euclid runs fast.
– Jyrki Lahtonen
Jul 19 at 7:43
1
Maybe this article has something helpful? On the number of irreducible polynomials with 0,1 coefficients
– Sil
Jul 22 at 15:54