## Performance of factoring algorithms

Expand Messages
• Hello friends. I ve constructed a factoring algorithm that I call ProportionateFactor because, to factor positive integer z, it seeks to find four integers
Message 1 of 2 , Apr 21, 2012
• 0 Attachment
Hello friends.

I've constructed a factoring algorithm that I call ProportionateFactor
because, to factor positive integer z, it seeks to find four integers
t0,t1,t2,t3 such that

t0 + t1 + t2 + t3 = z
and
t0 t3 = t1 t2.

Then it checks to see if GCD(t0+t1,z) is strictly between 1 and z.
It often happens that GCD(t0+t1,z) is exactly equal to z.

In the following I have tested my new factoring algorithm against
several other algorithms.

The third number in the output vector is the number of cycles within the
algorithm that found the factors.

ProportionateFactor appears to be in close competition with (p-1)
factoring algorithm.

I had had hopes that ProportionateFactor would be much faster, but I did
not anticipate that most of the time
GCD(z,t0+t1) would be exactly equal to z.

>>> Factor(10**14+13)

In Factor. z = 100000000000013
[[173L, 578034682081L, 27], 'ProportionateFactor: Level A2']

>>> Factor(10**14+27)

In Factor. z = 100000000000027
[[751L, 133155792277L, 3], 'ProportionateFactor: Level A2']

>>> Factor(10**14+37)

In Factor. z = 100000000000037
Found factor by p-1.
[[53799857L, 1858741L], 1452]

>>> Factor(10**14+39)

In Factor. z = 100000000000039
Found factor by p-1.
[[2596823L, 38508593L], 49]

>>> Factor(10**14+49)

In Factor. z = 100000000000049
[[109L, 917431192661L, 16], 'ProportionateFactor: Level A3']

>>> Factor(10**14+51)

In Factor. z = 100000000000051
[[6653L, 15030813167L, 2795], 'ProportionateFactor: Level A3']

In Factor. z = 100000000000057
[[23L, 4347826086959L, 1], 'ProportionateFactor: Level A4']
>>> Factor(10**14+61)

>>> Factor(10**14+63)

In Factor. z = 100000000000063
[[572587L, 174645949L, 11175], 'ProportionateFactor: Level A4']
>>> Factor(10**14+67)

In Factor. z = 100000000000073
Found factor by Pollard Rho.
[[13371821L, 7478413L], 961]
>>> Factor(10**14+79)

In Factor. z = 100000000000079
Found factor by trial division.
[[19, 5263157894741L], 3]
>>> Factor(10**14+81)

In Factor. z = 100000000000081
[[47309L, 2113762709L, 11545], 'ProportionateFactor: Level A3']
• ... Without any information on how you propose to find the t_i it s next to impossible to give any meaningful analysis of your algorithm. Paul
Message 2 of 2 , Apr 23, 2012
• 0 Attachment
On Sat, 2012-04-21 at 19:21 -0400, Kermit Rose wrote:
>
> Hello friends.
>
> I've constructed a factoring algorithm that I call ProportionateFactor
> because, to factor positive integer z, it seeks to find four integers
> t0,t1,t2,t3 such that
>
> t0 + t1 + t2 + t3 = z
> and
> t0 t3 = t1 t2.
>
> Then it checks to see if GCD(t0+t1,z) is strictly between 1 and z.
> It often happens that GCD(t0+t1,z) is exactly equal to z.
>
> In the following I have tested my new factoring algorithm against
> several other algorithms.
>
> The third number in the output vector is the number of cycles within
> the
> algorithm that found the factors.
>
> ProportionateFactor appears to be in close competition with (p-1)
> factoring algorithm.
>
> I had had hopes that ProportionateFactor would be much faster, but I
> did
> not anticipate that most of the time
> GCD(z,t0+t1) would be exactly equal to z.

Without any information on how you propose to find the t_i it's next to
impossible to give any meaningful analysis of your algorithm.

Paul
Your message has been successfully submitted and would be delivered to recipients shortly.