0
$\begingroup$

There are many analogies between the objects $\mathbb F_q[x]$ and $\mathbb Z$.

Supposing there is a fixed (say $10^9$) dimension linear integer program (describable without any objective function) in fixed number of constraints which assists in a deterministic polynomial time algorithm for factoring integers would it say anything about derandomization of $\mathbb F_q[x]$ factoring (the most important step is the case of equal degree factoring https://www.csa.iisc.ac.in/~chandan/courses/CNT/notes/lec8.pdf)?

Fixed dimension integer programming is known to be in $P$ by a result of Lenstra (https://www.jstor.org/stable/3689168).

To be clear assume that the integer program is a simple $\exists x\in\mathbb Z^n:Ax\leq b$ program which has no objective function and produces the factors in one of its variables. We have to set the program, run Lenstra's algorithm and determine the value of a particular variable for a non-trivial possibly composite factor by computing $GCD$ of this variable with the given integer externally to the program after the program is completed. We can reuse the program to completely factor the given integer with the help of $AKS$ algorithm (https://en.wikipedia.org/wiki/AKS_primality_test) for primality.

Essentially would such a set up help over $\mathbb Fq[x]$?

Update A question was raised below on why not just assume $P=BPP$. Since the reply was long for a comment I post the reply as an update. $P=BPP$ relies on still (I believe $100\%$ true but) unproven lower bound on the complexity class $E$ and there is no way known around this. As far as we know the only way to prove $P=BPP$ could be to prove $P=NP$ and no one has dismantled this possibility (and proving deterministic factoring of integers in polynomial time is much easier than $P=NP$ even if both were possible and arguably looking for deterministic factoring of integers in polynomial time (as a way to derandomize $\mathbb F_q[x]$) is much easier than proving the general purpose derandomization statement $P= BPP$ by proving lower bounds against $E$ even if both were possible). This problem is about derandomizing the specific problem of derandomizing equal degree factoring. I do not see any possibility to use such an integer linear program for derandomizing equal degree factoring. Since we believe derandomizing equal degree factoring should be possible and since we believe this to be all the more likely than the more difficult problem of deterministic general purpose integer factoring, I am wondering whether non-transferability of such a deterministic integer program result is barrier to existence of such programs. It is a motivation for the question.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Could you clarify what you mean by "without any objective function"? Isn't that usually part of the definition of an integer program? $\endgroup$
    – Bill Bradley
    Commented Jan 5, 2023 at 12:51
  • $\begingroup$ @BillBradley Just a statement of form $\exists x\in\mathbb Z^n: Ax\leq b$ is an integer program in $n$ dimensions. We take a particular variable, say $x_1$, and after the program is tested for solutions by Lenstra's algorithm compute $GCD(x_1,N)$ to get a possibly composite factor which is non-trivial. $\endgroup$
    – Turbo
    Commented Jan 5, 2023 at 12:58
  • 1
    $\begingroup$ I don't quite understand the point of this question. If, in your quest for derandomization, you allow yourself to assume unproven hypotheses such as "integer factorization is in $\mathsf{P}$," then why not just assume the unproven hypothesis that $\mathsf{P} = \mathsf{BPP}$? Probably more people believe the latter than the former. $\endgroup$
    – Timothy Chow
    Commented Jan 6, 2023 at 3:59
  • $\begingroup$ @TimothyChow Since my comment was going to be long I posted reply as an update to the MO post. $\endgroup$
    – Turbo
    Commented Jan 6, 2023 at 4:18
  • 1
    $\begingroup$ Okay, so you think that proving that integer factorization is in $\mathsf{P}$ may be easier than proving that $\mathsf{P} = \mathsf{BPP}$. Fair enough. But your final comment still puzzles me. Did you mean to say that the transferability (rather than the non-transferability) would be a barrier? If problem $X$ seems hard and problem $Y$ seems easy, then a barrier to a proposed approach $A$ to solving $X$ might be that $A$ would allow $X$ to be reduced to $Y$, which we don't think can be done. $\endgroup$
    – Timothy Chow
    Commented Jan 6, 2023 at 13:15

0

Reset to default

You must log in to answer this question.