Browse Groups

• 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
Message 1 of 1 , Jul 1, 2004
View Source
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.
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.