I gave an example earlier of attempting to find the factors of a number

known to have two and only two prime factors.

In this example I shall show how recursive use of the algorithm brings even

better results.

I shall use 9913 as my example, ((10*43) + 1) * ((2*11) + 1).

Feeding 9913 into the 'reverse method' algorithm shows that 9913 divides a

Mersenne of 2^473 -1.

At this stage we know the two factors divide Mersennes 2^x -1 and 2^y -1

where x*y = 473.

As 473 is an odd number we can feed it back into the algorithm, giving a

result of 70.

What the 70 represents is also interesting. It shows, amongst other things

that 2^70 - 1 divides by both x and y. Further it shows that the shortest

Mersenne lengths for x and y both divide into 70. (Trivially, 2^x and 2^y

both divide 2^70).

Looking at the factors of 70 we note that it divides as follows:

70 / 2 = 35

70 / 5 = 14

70 / 7 = 10

Looking into the table of shortest Mersenne lengths for a given number we

note that 11 divides 2^10 - 1 and that 43 divides 2^14 - 1. So both 10 and

14 divide 70 and 11 * 43 divides 473 (above). So now we know, for sure,

that x and y are 11 and 43 respectively.

Now we can make up an equation.

((11a)+1) * ((43b)+1) = 9913

In this instance we know, without trial factoring, that a is 2 and b is

10. Strangely enough, both numbers appear in the factors of 70. I think

that this is co-incidental, but it seems to happen with quite a few number

combinations that I have tried.

I'll just summarize the same process for 245969 ((6*37)+1) * ((38*29)+1).

245969 gives 1073 or x * y.

1073 gives 252

Factors of 252 are:

252 / 2 = 126

252 / 3 = 84

252 / 4 = 63

252 / 6 = 42

252 / 7 = 36

252 / 9 = 28

252 / 12 = 21

252 / 14 = 18

Looking through the Mersenne table we find that 37 divides 2^36 - 1 and 29

divides 2^28 - 1.

Now we know that:

((29a)+1) * ((37b)+1) = 245969.

Trial factoring finally gives us a = 38 and b = 6.

In conclusion, I think that I have shown a method to break down the problem

of factorizing a composite number into chunks that are easier to deal

with. First by deriving the Mersenne numbers from where the factors come

and then by trial factoring in the appropriate ranges.

Now if I can only derive the multiples (a & b) as well as the powers (x &

y) then I will be laughing :-)

Kevin.