The following thread is on the challenging problem of how to quickly factor a composite integer using polynomials.

I wish for other users to answer the question I make in each post, however if it goes unanswered, I'll post it myself eventually (assuming I have it) and then move on to the next part. Furthermore, I'll point out those problems which I feel are ''research questions'' that have currently gone unanswered in the literature.

Consider a degree $\displaystyle d$ polynomial $\displaystyle P(x;a) = (a^dx - 1).....(a^2x - 1)(ax - 1)$ and suppose $\displaystyle n$ is a composite integer we wish to factor.

Let $\displaystyle k = [\frac{\sqrt{n}}{d}]$ and $\displaystyle i = a^{d} mod(n)$.

Argue that if $\displaystyle gcd(a,n) = 1$ then the product

$\displaystyle P = P(i;a)P(i^2;a)P(i^3;a)....P(i^k;a)mod(n)$, is such that $\displaystyle gcd(P,n) ! = 1$