On Sunday, December 15, 2013 2:48:21 PM UTC-8, Volker Braun wrote: > > This is from http://trac.sagemath.org/15517, ecm doesn't find a factor. > But there is one with 17 digits, so should be just fine? Does anybody have > a suggestion on what to do if ecm quits without finding a factor? When is > it safe enough to assume that there is no factor? >
??? It's a probabilistic method. With any reasonable choice of parameters, there is always a non-zero chance that ECM will not find a factor. A priori it may just be the case that for an integer N=p*q you choose an elliptic curve and a point such that the order of the point modulo p as well as q is a prime (of size about p and q). Trying to use ECM to detect a prime factor with such a curve is probably worse than trial division. ECM has a better expected runtime because the probability of running into such a curve should be low (and ECM amortizes by trying several curves). The proper thing to do after ECM has failed to find a factor is to try to PROVE no factor exists by running a primality prover. In fact, you should probably have already run a probilistic primality test such as Miller-Rabin to establish that N is not prime itself (it is much easier to get astronomic probabilistic certainty out of that than by running ECM to get evidence that a factor of at most 17 digits probably doesn't exist). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/groups/opt_out.
