Factoring of composites with near factors - request for data

[AntonVrba]

I think, I can factor extremely fast, a composite number

Q = Px Cx with restraint (Px-Cx)< 100 Sqrt[Px]

regardless of the size of Px (Px prime, Cx prime or composite)

I would appreciate some test data for
Q = 300, 600 and 1000 decimal digits but please keep restraint (Px-Cx) < 100 Sqrt[Px]

Regards
Anton

[xilman]

Originally Posted by AntonVrba

I think, I can factor extremely fast, a composite number

Q = Px Cx with restraint (Px-Cx)< 100 Sqrt[Px]

regardless of the size of Px (Px prime, Cx prime or composite)

I would appreciate some test data for
Q = 300, 600 and 1000 decimal digits but please keep restraint (Px-Cx) < 100 Sqrt[Px]

Regards
Anton

Three observations:

First, you can easily produce your own test data. There's no need for you to get it from elsewhere.

Second, it sounds very much like you have reinvented Fermat's factoring algorithm.

Third, only an exceedingly small fraction of numbers with 300 digits (and even smaller fractions of larger numbers) meet your criteria.

Post your algorithm and lets take a look at it.


Paul

[John Renze]

Originally Posted by AntonVrba

I think, I can factor extremely fast, a composite number

Q = Px Cx with restraint (Px-Cx)< 100 Sqrt[Px]

regardless of the size of Px (Px prime, Cx prime or composite)

Lenstra's algorithm (C&P Algorithm 4.2.11) can do this with sqrt(Px) replaced by (Px)^2/3.

Edit: Never mind. Lenstra's algorithm is for low bits known, not high bits known. BUT, Coppersmith's LLL techniques work for the case Anton is talking about, all the way up to (Px)^3/4.

[AntonVrba]

After posting I noticed my result is not that spectacular, and I have been asked to share my algorithm, well here goes:

For Q= Px Cx (Px and Cx being near )
using notation [ ] meaning floor function or integerpart

Let
b = [ Sqrt(Q) ]
x0 = Mod(Q , b)
x1 = [Q / b]

k= [Sqrt( i*b - x0) - i/2]+1
then Px = GCD(x0 + k * b , x1-k)
and "i" being an integer quantity!

even more baffeling:

Let p1 be a prime
Let p2 be the nearest prime to p1+[s * sqrt(p1)]
Q= p1 p2
then
b = [ Sqrt(Q) ]
i=[(s^2)/4] or i=[s^2/4]+1
k= [Sqrt( i*b - x0) - i/2]+1
p1= x1-k

Above holds for s < p1^1/6 (sixth root)


Trivial example:
q1= 3 10^12 + 13 = 3000000000013

s=[q1^1/6]=120

q2= q1+[s sqrt(q1)]+40
= 3000207846149 (+40 for next prime)

Q=9000623538486002701999937

b = 3000103921281
x0 = 370057318976
x1 = 3000103921281

i = (120^2)/4=3600
k = [Sqrt( i*b - x0) - i/2]+1 = 103921268

x1-k =...281 - ...268 = 3000000000013 = p1

Now my thinking is:

if k= [Sqrt( i*b - x0) - i/2]+1 is an approximation of a higher order polynomial then it should be possible that the range can be extended and the iterration to find the factors of Q is done over "i"

Any comments?