Re: Analysing the Collatz tree!


Danny wrote:
Mensanator wrote:

A lot of Collatz stuff is like that: I have a way to use
Collatz to factor large numbers, but to be practical, >you
need to know one of the factors. :-(

In your factoring quest have you looked for the GCD
of the target composite(seed) in its own seed path?

Yeah, that's how it works. If your seed happens to be
on one of the Non-Trivial factor trees of 3n+C, where
C is, say, an RSA challenge number, then the GCD
of consecutive odd numbers in the seed path will
be a factor of C.

It is easy to find those Non-Trivial trees when you
know the factors (I've proved the concept using one
of the RSA challenge numbers that's already been
solved).

The tricky part (which I'm still pondering) is being able
to identify a factor tree without knowing the factor.


Probably very inefficient for very large composites
because of the huge number of terms in its' seed path.

Yes, the loop cycle at the root of a factor tree can have
a length that's within an order of magnitude of the factor
making loop cycle detection intractable for RSA sized
factors. But the GCD=factor trick seems to work anywhere
on the factor tree, not just the loop cycle, so I'm not
giving up yet.


I have the same problem with triangle number factoring,
you need to know a larger or smaller triangle number to
give you the 1 factor you need to find both factors of
a composite with just 2 factors. Ironically you need both
factors to find the right target triangle number.
If the composite is on the same triangle number line then
it is trivial and very easy to find one of its factors.

For 3n+C, the GCDs will always be a divisor of C (including
many distinct trees with the same GCD). But in my limited
testing, if C has exactly 2 factors, it seems I get 4 trees with
GCDs: C, 1, factor1 and factor2. And I only need to find one
of the factor trees to solve the challenge.

When you see the announcement that the RSA Challenge
is closed (because all the challenges have been solved),
you'll know I figured out the tricky part. :-)


Dan

.