#15443: Random time outs in ecm.py
-------------------------------------+-------------------------------------
Reporter: vbraun | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.1
Component: number theory | Resolution:
Keywords: | Merged in:
Authors: Volker Braun | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vbraun/ecm_cleanup | 998126dbd22d30eb34b46a0f122f9d62a9f861c9
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by nbruin):
Ah, OK. I see what happens. The case you are running into really has very
low probability and it is surprising you're triggering it at all. You're
basically finding BOTH factors together. The idea of ECM is to choose a
group E over Z together with a group element G, such that for the integer
N=p*q (it works for products of more primes too) such that the order of G
mod p is B-smooth (allowing some non-smoothness with "second stage" large
prime variation). However, if G mod q is ''also'' B-smooth then you're
detecting both factors together.
In the analysis of ECM, it turns out the optimal parameter choice is such
that the probability of hitting an (E,G) pair with B-smooth order of G mod
p is pretty low. The probability of G mod q also being B-smooth should be
pretty much independent. If p,q are roughly of the same size and you need
on average N trials to find G mod p of B-smooth order, then you expect
that in 1/N of ''those'' cases, G mod q also has B-smooth order. If q is
much larger than p then this probability should be ''much'' lower. I'm
surprised that for N=45949729863572179*13109994191499930367061460439 you
guys are encountering this at all. It suggests that the B1 value used is a
little on the large side if this happens with discernable frequency (what
may happen is that you're simply unlucky the first few times and then you
have increased B1 to such a point that finding both G mod p and G mod q to
be B-smooth isn't such an unlikely event anymore. So perhaps you're
increasing B1 a little too aggressively)
Anyway, as you can see, certainly for p,q of roughly the same size (not
ECM's forte, but if p,q are not big, ECM can still be useful for those),
finding p*q as a factor is really something that has to be counted on.
You should REALLY NOT run ECM on a number that might be prime. You should
FIRST prove the number is composite for certain. In that case, you can
treat finding the input as factor as finding no factor at all and simply
try another time (perhaps NOT increasing B1)
--
Ticket URL: <http://trac.sagemath.org/ticket/15443#comment:25>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
