Loading ...
Sorry, an error occurred while loading the content.

Recursion brings better results

Expand Messages
  • Kevin Acres
    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
    • 0 Attachment
      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.