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?
--
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/
