Schemes for Deterministic Polynomial Factoring

Details Schemes for Deterministic Polynomial Factoring Schemes for Deterministic Polynomial Factoring

2008-04-11

arxiv.org/abs/0804.1974v1

Computer Science

Computational Complexity

14 pages, preliminary version

Scientific paper

In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call m-schemes. We extend the known conditional deterministic subexponential time polynomial factoring algorithm for finite fields to get an underlying m-scheme. We demonstrate how the properties of m-schemes relate to improvements in the deterministic complexity of factoring polynomials over finite fields assuming the generalized Riemann Hypothesis (GRH). In particular, we give the first deterministic polynomial time algorithm (assuming GRH) to find a nontrivial factor of a polynomial of prime degree n where (n-1) is a smooth number.

Affiliated with

Also associated with

No associations

Rating

Schemes for Deterministic Polynomial Factoring does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Schemes for Deterministic Polynomial Factoring, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Schemes for Deterministic Polynomial Factoring will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-473929