- 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)

In Factor. z = 100000000000063

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

[[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'] - On Sat, 2012-04-21 at 19:21 -0400, Kermit Rose wrote:
>

Without any information on how you propose to find the t_i it's next to

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

impossible to give any meaningful analysis of your algorithm.

Paul