If a prime Q | M_C
then Order(2,Q) | C ;but not 1
Order(2,Q) | Q-1
F:=GCD(C,Q-1) != 1
F will either be C or one of it's divisors.
If Order(2,Q)==C then it has almost zero information
to tell us anything about the factors of C.
If C has 2 factors P0 & P1 then the product of factors
with Order == C is M_C/(M_P0.M_P1)
with Order == P1 is M_P1
Order == P0 is M_P0
(For more than 2 factors of C, Pofwo(C) is recursively
defined as M_C / all the pofwos of the divisors of C).
I would expect the probability that a factor of M_C
has these orders to be a non-decreasing function of these
products.
An approximation for the probabilities could be just the
ratio of these products.
Sadly for composites such as M727 which guesses have as
having a small number of factors and it is known that the
smallest factor is bigger than a decent bound, F will
equal M727 nearly all the time, and rarely will a factor
be found. There is also the rare case where the order of
Q <= M_C but F=M_C
The distribution of Mersenne Divisors is such that small
Q will tend to have a smaller order, and any Q<=2M_C
will not have order M_C.
If you are only searching for factors of M_C of the form
KC+1 then these will always have F=M_C and tell us nothing
about the factors of C. The only factors of M_C that help
with factoring C are those not of the form KC+1.
Stating the obvious, M_C is exponentially bigger than
C and even a trial divison of M_C using exponentiation
will take longer than meaningful operations on C.
For example a division of M_M727 is not practical, but if
a factor of M_C is found it is worth doing one GCD.
So an approximate heuristic that anyone can better by not
using a geometric mean or using knowledge of the distribution
of Mersenne Divisors, is that for C having 2 factors, the
probability of Q | M_C helping with factoring C is approx:-
M_P0 + M_P1
-----------------------
M_C + M_P0 + M_P1
---------
M_P0.M_P1 or not a lot!
Cheers,
Paul Landon
ps. Every train driver knows that Scottish sheep have
a maximum of 7 colours :-)
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
