The Experts below are selected from a list of 102 Experts worldwide ranked by ideXlab platform
Saxena Nitin - One of the best experts on this subject based on the ideXlab platform.
-
Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications
LIPIcs - Leibniz International Proceedings in Informatics. 34th Computational Complexity Conference (CCC 2019), 2019Co-Authors: Dwivedi Ashish, Mittal Rajat, Saxena NitinAbstract:Finding an Irreducible Factor, of a polynomial f(x) modulo a prime p, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that counts the number of Irreducible Factors of f mod p. We can ask the same question modulo prime-powers p^k. The Irreducible Factors of f mod p^k blow up exponentially in number; making it hard to describe them. Can we count those Irreducible Factors mod p^k that remain Irreducible mod p? These are called basic-Irreducible. A simple example is in f=x^2+px mod p^2; it has p many basic-Irreducible Factors. Also note that, x^2+p mod p^2 is Irreducible but not basic-Irreducible! We give an algorithm to count the number of basic-Irreducible Factors of f mod p^k in deterministic poly(deg(f),k log p)-time. This solves the open questions posed in (Cheng et al, ANTS\u2718 & Kopp et al, Math.Comp.\u2719). In particular, we are counting roots mod p^k; which gives the first deterministic poly-time algorithm to compute Igusa zeta function of f. Also, our algorithm efficiently partitions the set of all basic-Irreducible Factors (possibly exponential) into merely deg(f)-many disjoint sets, using a compact tree data structure and split ideals
Nitin Saxena - One of the best experts on this subject based on the ideXlab platform.
-
Counting basic-Irreducible Factors mod $p^k$ in deterministic poly-time and $p$-adic applications
arXiv: Symbolic Computation, 2019Co-Authors: Ashish Dwivedi, Rajat Mittal, Nitin SaxenaAbstract:Finding an Irreducible Factor, of a polynomial $f(x)$ modulo a prime $p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of Irreducible Factors of $f\bmod p$. We can ask the same question modulo prime-powers $p^k$. The Irreducible Factors of $f\bmod p^k$ blow up exponentially in number; making it hard to describe them. Can we count those Irreducible Factors $\bmod~p^k$ that remain Irreducible mod $p$? These are called {\em basic-Irreducible}. A simple example is in $f=x^2+px \bmod p^2$; it has $p$ many basic-Irreducible Factors. Also note that, $x^2+p \bmod p^2$ is Irreducible but not basic-Irreducible! We give an algorithm to count the number of basic-Irreducible Factors of $f\bmod p^k$ in deterministic poly(deg$(f),k\log p$)-time. This solves the open questions posed in (Cheng et al, ANTS'18 \& Kopp et al, Math.Comp.'19). In particular, we are counting roots $\bmod\ p^k$; which gives the first deterministic poly-time algorithm to compute Igusa zeta function of $f$. Also, our algorithm efficiently partitions the set of all basic-Irreducible Factors (possibly exponential) into merely deg$(f)$-many disjoint sets, using a compact tree data structure and {\em split} ideals.
Dwivedi Ashish - One of the best experts on this subject based on the ideXlab platform.
-
Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications
LIPIcs - Leibniz International Proceedings in Informatics. 34th Computational Complexity Conference (CCC 2019), 2019Co-Authors: Dwivedi Ashish, Mittal Rajat, Saxena NitinAbstract:Finding an Irreducible Factor, of a polynomial f(x) modulo a prime p, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that counts the number of Irreducible Factors of f mod p. We can ask the same question modulo prime-powers p^k. The Irreducible Factors of f mod p^k blow up exponentially in number; making it hard to describe them. Can we count those Irreducible Factors mod p^k that remain Irreducible mod p? These are called basic-Irreducible. A simple example is in f=x^2+px mod p^2; it has p many basic-Irreducible Factors. Also note that, x^2+p mod p^2 is Irreducible but not basic-Irreducible! We give an algorithm to count the number of basic-Irreducible Factors of f mod p^k in deterministic poly(deg(f),k log p)-time. This solves the open questions posed in (Cheng et al, ANTS\u2718 & Kopp et al, Math.Comp.\u2719). In particular, we are counting roots mod p^k; which gives the first deterministic poly-time algorithm to compute Igusa zeta function of f. Also, our algorithm efficiently partitions the set of all basic-Irreducible Factors (possibly exponential) into merely deg(f)-many disjoint sets, using a compact tree data structure and split ideals
Ashish Dwivedi - One of the best experts on this subject based on the ideXlab platform.
-
Counting basic-Irreducible Factors mod $p^k$ in deterministic poly-time and $p$-adic applications
arXiv: Symbolic Computation, 2019Co-Authors: Ashish Dwivedi, Rajat Mittal, Nitin SaxenaAbstract:Finding an Irreducible Factor, of a polynomial $f(x)$ modulo a prime $p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of Irreducible Factors of $f\bmod p$. We can ask the same question modulo prime-powers $p^k$. The Irreducible Factors of $f\bmod p^k$ blow up exponentially in number; making it hard to describe them. Can we count those Irreducible Factors $\bmod~p^k$ that remain Irreducible mod $p$? These are called {\em basic-Irreducible}. A simple example is in $f=x^2+px \bmod p^2$; it has $p$ many basic-Irreducible Factors. Also note that, $x^2+p \bmod p^2$ is Irreducible but not basic-Irreducible! We give an algorithm to count the number of basic-Irreducible Factors of $f\bmod p^k$ in deterministic poly(deg$(f),k\log p$)-time. This solves the open questions posed in (Cheng et al, ANTS'18 \& Kopp et al, Math.Comp.'19). In particular, we are counting roots $\bmod\ p^k$; which gives the first deterministic poly-time algorithm to compute Igusa zeta function of $f$. Also, our algorithm efficiently partitions the set of all basic-Irreducible Factors (possibly exponential) into merely deg$(f)$-many disjoint sets, using a compact tree data structure and {\em split} ideals.
Sabina B. Pannek - One of the best experts on this subject based on the ideXlab platform.
-
Number of Irreducible polynomials whose compositions with monic monomials have large Irreducible Factors
arXiv: Group Theory, 2019Co-Authors: Sabina B. PannekAbstract:Given a prime power $q$ and positive integers $m,t,e$ with $e > mt/2$, we determine the number of all monic Irreducible polynomials $f(x)$ of degree $m$ with coefficients in $\mathbb{F}_q$ such that $f(x^t)$ contains an Irreducible Factor of degree $e$. Polynomials with these properties are important for justifying randomised algorithms for computing with matrix groups.
-
Irreducible linear subgroups generated by pairs of matrices with large Irreducible submodules
Archiv der Mathematik, 2012Co-Authors: Alice C. Niemeyer, Sabina B. Pannek, Cheryl E. PraegerAbstract:We call an element of a finite general linear group GL(d, q) fat if it leaves invariant and acts irreducibly on a subspace of dimension greater than d/2. Fatness of an element can be decided efficiently in practice by testing whether its characteristic polynomial has an Irreducible Factor of degree greater than d/2. We show that for groups G with SL(d, q) ≤ G ≤ GL(d, q) most pairs of fat elements from G generate Irreducible subgroups, namely we prove that the proportion of pairs of fat elements generating a reducible subgroup, in the set of all pairs in G × G, is less than q −d+1. We also prove that the conditional probability to obtain a pair (g 1, g 2) in G × G which generates a reducible subgroup, given that g 1, g 2 are fat elements, is less than 2q −d+1. Further, we show that any reducible subgroup generated by a pair of fat elements acts irreducibly on a subspace of dimension greater than d/2, and in the induced action the generating pair corresponds to a pair of fat elements.