mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-01-12, 03:55   #1
drake2
 
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?

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

1001101000112 Posts
Default

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!

Alex
akruppa is offline   Reply With Quote
Reply

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.