[Full-disclosure] Polynomials and factoring

[aheadr at googlemail.com (r ahead)]

Abstract: Finding a nonzero multiple of coefficients or
exponent of polynomial may be equivalent to factoring

Let N be composite.
Let f(x) be a polynomial with coefficients reduced modulo N.
All examples are in gp/pari.

1. f(x) = (1+x)^N
p=13;q=17;n=p*q;po1=(1+Mod(1,n)*x)^n
2. f(x)= N-th Chebyshev polynomial of the first kind
p=13;q=17;n=p*q;po1=cheby1f(n,Mod(1,n)*x)
3. Let E: y^2=x^3+a*x+b be elliptic curve over Q
3.a f(x) = N-th division polynomial, variable is x. Of special
interest are a = 0 or b = 0
p=13;q=7;n=p*q;po1=SLPDivisionPolynomial(Mod(1,n),0,Mod(1,n)*x,n);
3.b f(x) = N-th division polynomial, variable is either a or
b, x is fixed
p=13;q=7;n=p*q;po1=SLPDivisionPolynomial(Mod(1,n)*x,0,Mod(1,n),n);

f(x) may be computed efficiently for numerical x and the
result is bounded modulo N.

When working symbolically the number of terms is large and
640KB are not enough.

Finding a nonzero multiple of any coefficient of f(x) or
exponent (except for the trivial highest or free coefficient
and 3.b) reveals the factorization of N.

The k-th derivative may be computed via pascal matrix in time
k and it is zero except for 3.b.

f(x) evaluated at the companion matrix of y^k-1 gives the sum
of coefficients of exponents divisible by k.

Let f(x)=sum(a_k*x^k)

sum(a_m*m*x^m, m = 0 mod m0) may be computed using about m0^4
memory.
m0=4;ma7=matcompanion(x^m0-1)*x;ma7=x*subst(ma7,x,matpascal(1));pol=x^5+15*x^4+3*x^2+2;po1=subst(pol,x,ma7);po1[1,1][2,1]

It would be nice if nilpotent elements were efficiently
computable - Mod(y,y^k) may find the degree of the lowest
monomial, but k is large.

Any ideas?

--
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.grok.org.uk/pipermail/full-disclosure/attachments/20070428/20fd7b5c/attachment.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DP-pub.gp
Type: application/octet-stream
Size: 3468 bytes
Desc: not available
Url : http://lists.grok.org.uk/pipermail/full-disclosure/attachments/20070428/20fd7b5c/attachment.obj