mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-02-04, 14:18   #1
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

2×72 Posts
Default Factoring of composites with near factors - request for data

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
AntonVrba is offline   Reply With Quote
Old 2006-02-04, 17:53   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

11·919 Posts
Default

Quote:
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
xilman is offline   Reply With Quote
Old 2006-02-05, 00:43   #3
John Renze
 
John Renze's Avatar
 
Nov 2005

24·3 Posts
Default

Quote:
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.

Last fiddled with by John Renze on 2006-02-05 at 00:45
John Renze is offline   Reply With Quote
Old 2006-02-05, 06:30   #4
AntonVrba
 
AntonVrba's Avatar
 
Jun 2005

6216 Posts
Default The Algorithm

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?
AntonVrba is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring n via factors of n-1 or n+1 a1call Miscellaneous Math 63 2018-03-06 09:39
P-1 factoring attempts at smallest-remaining Mersenne numbers with no known factors UberNumberGeek Factoring 51 2017-02-13 20:30
option for finding multiple factors during trial factoring tha Software 24 2014-06-10 23:31
What's the point of factoring known composites? ixfd64 PrimeNet 4 2011-02-21 11:51
Types of work to request from server : Add P-1 Factoring MoZ Software 2 2004-02-06 20:24

All times are UTC. The time now is 09:17.

Tue Oct 20 09:17:25 UTC 2020 up 40 days, 6:28, 0 users, load averages: 1.57, 1.76, 1.71

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.