full-disclosure - Polynomials and factoring

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <1c143520704280316i16366e93se0da61302380ac48@mail.gmail.com>
Date: Sat, 28 Apr 2007 13:16:28 +0300
From: "r ahead" <aheadr@...glemail.com>
To: full-disclosure@...ts.grok.org.uk
Subject: Polynomials and factoring

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?

--

Content of type "text/html" skipped

Download attachment "DP-pub.gp" of type "application/octet-stream" (3469 bytes)

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/