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? --
Attachment:
DP-pub.gp
Description: Binary data
_______________________________________________ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/