FPRD LabShare an approach

← Claims

Proposition · complexity upper bound

FPRD-LRS-T03

Randomized polynomial-time zero test

Exact statement

Indexed LRS zeroness belongs to coRP\mathsf{coRP}: repeated squaring builds a polynomial-size division-free integer circuit for the queried matrix entry, and random-prime modular evaluation has one-sided error.

StatusDerived from the standard EquSLP upper bound; externally used
External reviewBacik, Ouaknine, and Worrell use the same iterated-powering and arithmetic-circuit zero-test subroutine; no external review of this FPRD exposition is recorded.

Context

A zero integer remains zero modulo every prime. The standard EquSLP algorithm chooses its prime-sampling range from a circuit-growth bound, so a nonzero output is missed with probability at most one half.

Hypotheses and scope

  • The standard one-sided randomized upper bound for integer straight-line-program zeroness is available.

Proof or evidence

Repeated squaring uses polynomially many matrix operations in log n and produces a polynomial-size circuit. Modular evaluation avoids expanding the potentially enormous integer.

Reduction to arithmetic-circuit zeroness →

Verification notes

The direction of the reduction and one-sided error were checked against Schönhage's straight-line-program bound and Bacik--Ouaknine--Worrell's explicit use of EquSLP in the bounded-Skolem setting. No reverse reduction from arbitrary EquSLP is asserted.

Limitations

  • coRP is not deterministic polynomial time.
  • The result does not establish EquSLP hardness.

Open work

Investigate deterministic hitting sets for the structured repeated-power circuits.