Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2006-01-12, 03:55   #1
Aug 2005

24 Posts
Default Basic Question about ECM factoring?

If there were no practical time limits when trying to factor a number using ECM and you pick a B1 such as 11,000,000 or 44,000,000 so that you could run as many curves as desired is it guaranteed that you will eventually find the factor? Also if you just kept raising B1 to much larger numbers, would that guarantee success, again assuming no practical time limit?

For example, the C140 of C(566) Cullen number in Mr. Leyland's tables. From my understanding of what I have read you could run ECM curves forever and never find the factor if there are not small factors of p-1 less than B1 or one of the factors of p-1 between B1 and B2 and the rest less than B1, but I am not sure my understanding is correct.

Since in reality we do have time limits, I am assuming the better approach to attempting to factor this number is to learn how gnfs works. What sort of practical timeframe would be required when trying to factor this C140 using gnfs not counting any practice or learning time?

drake2 is offline   Reply With Quote
Old 2006-01-12, 07:40   #2
akruppa's Avatar
Aug 2002

1001101000112 Posts

ECM finds the factor p if the group order of the elliptic curve (mod p) has only small prime factors. By Hasse's theorem, the order is in the interval [p-2sqrt(p)+1, p+2sqrt(p)+1]. If p is large and your B1,B2 very small, it is quite possible that no smooth enough number exists in that interval. Another problem for this analysis is that Montgomery parameterisation does not allow as many distinct curves to be selected as, say, WeierstraƟ form does, so the lucky smooth integer(s) in the Hasse interval may not be accessible. A far greater problem is that most ECM implementations choose the sigma value for the curve parameters from a fairly small set of integers ([7, 2^32] in the case of GMP-ECM), so only a tiny fraction of distinct group order from the Hasse interval is accessible. So there are several reasons that for very large p and given B1,B2, it may actually be impossible for ECM to find p. However, p would have to be quite large.
Keep in mind, though, that choosing B1,B2 way off has a severe impact on performance of ECM. Especially when choosing them way too low, the expected time to find p grows faster than p, making ECM worse than trial factoring!

akruppa is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Question regarding basic routines being used in Yafu. storflyt32 YAFU 2 2015-06-29 23:25
basic question for assignment wong8888 Information & Answers 5 2015-03-22 12:15
A basic math question iconized Prime Sierpinski Project 2 2012-02-03 00:01
Yet another basic-factoring-questions thread davar55 Factoring 24 2011-01-23 23:57
Basic optimisation question fivemack Puzzles 6 2008-04-08 13:50

All times are UTC. The time now is 06:24.

Wed May 12 06:24:21 UTC 2021 up 34 days, 1:05, 0 users, load averages: 1.80, 1.66, 1.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.