20201122, 15:48  #1 
Random Account
Aug 2009
U.S.A.
11010011001_{2} Posts 
ECM Factors
Question: Where are the majority of factors found in ECM? Stage 1 or Stage 2?

20201122, 18:20  #2 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10197_{10} Posts 

20201123, 15:31  #3 
Random Account
Aug 2009
U.S.A.
3·563 Posts 

20201123, 16:32  #4 
Jun 2003
11255_{8} Posts 
Something's lost in translation. Rather than explain why you've misunderstood that (oddly phrased) statement, can you explain to us why you think that is not always the case?

20201123, 16:44  #5  
Sep 2009
5×389 Posts 
Quote:
But that's not true. A quick search of recent ECM work I've done reveals: Code:
********** Factor found in step 2: 450447448630040607679056578447 Found composite factor of 30 digits: 450447448630040607679056578447 Prime cofactor 857728978884123546562041187998599433152336542089743038903 has 57 digits 

20201123, 18:00  #6  
Random Account
Aug 2009
U.S.A.
3·563 Posts 
Quote:
Quote:
"Multiple factors can be found below B1, but only one factor above..." Oddly phrased? Perhaps the individual who wrote this statement thought I may not understand a more complex response, so he kept it simple. This was probably three years ago, at least. Who wrote it, I cannot remember. 

20201123, 18:39  #7  
Einyen
Dec 2003
Denmark
11·271 Posts 
Quote:
Besides with ECM it is the group order that has to be smooth and the group order changes with each curves sigma. Last fiddled with by ATH on 20201123 at 18:43 

20201123, 19:18  #8  
"Curtis"
Feb 2005
Riverside, CA
10606_{8} Posts 
Quote:


20201124, 08:47  #9  
Romulan Interpreter
Jun 2011
Thailand
2^{2}·7·11·29 Posts 
Quote:
Taking as example P1, because that is easy to explain, assume there is a prime factor q that divides m=2^p1, then we know that q is prime (yeah...) and it has the form q=2kp+1. Because it is prime, from Fermat's theorem, for any base b smaller than q, we have b^(q1)=1 (mod q). Which, when implemented for mersenne numbers, due to the fact that q=2kp+1, we have b^(2kp)1=0 (mod q). Which means that (b^(2p))^k1 is a multiple of q. If we can calculate this, or some multiple of it, then the gcd between m and the result of that calculation, will reveal the factor q. What P1 factoring does, it computes a very large number E, as the product of a lot of small numbers (i.e. LCM(all numbers below a "boundary" B1), which means all numbers below B1 are included in this E), then it picks a small random b (usually 3 or 5), it computes first c=b^(2p), then it computes H=c^E. If k is smooth (i.e. it has nothing but very small factors) then H1 will be a multiple of q, and we will find the factor q. Now, E contains lots and lots of prime factors, millions (depending how high B1 is). There is a possibility that more factors of m, i.e q1, q2, etc., "fit the pattern". Example: Assume you try to find a factor of m=M29=2^291=536870911=233*1103*2089, using B1=10, B2=23. You calculate first E=2^3*3^2*5*7=72*35=2520 (product of all primes smaller than B1=10, with their largest power not exceeding B1=10). E is a very smooth number, and it is the least common multiple of all numbers from 2 to 10, i.e. all such numbers 2, 3, 4, 5, 6, 7, 8, 9, 10, are "inside E". Then, you pick b=3, and compute c=b^(2*29)=3^58 (mod m), then H=c^E (mod m). You do the calculation mod m=M29, to avoid the numbers getting ridiculously big. Without the modular step, c would be a (about) 30 digits number, and H would be a number with over 70 thousands digits! (only for this shitty small example). So, (al calculation is (mod m)): c=3^58=194980136, H=194980136^2520=214651018. H'=H1=2146510181=214651017. If now you take gcd(H',m)=gcd(214651017,536870911) you get 486737, which is the products of 233 and 2089. So, you found the first and the third factor, but didn't find the second. Why? Because the "k" of the first and the third factor is 10smooth, while the k of the second is not. We have (the "k" is in parenthesis, in q=2kp+1 form): 233 = 2^3*29+1 = 2*(2^2)*29+1 = 2*(4)*29+1 1103 = 2*(19)*29+1 2089 = 2^3*3^2*29+1 = 2*(2^2*3^2)*29+1 = 2*(36)*29+1 All factors of "k" in the first and third case are twos and threes, i.e. smaller than 10. The second "k" is 19, which is not 10smooth. So, P1 can't find this factor, with this B1. (here you may think about why P1 does not find the factors "in order", larger factors can be found, and smaller can be missed). Therefore, in stage 1 of the P1, we found a multiple (composite) factor, q1*q3. Assuming we want to continue with the P1 stage 2 (if we didn't find any factor in stage 1, or if we just want to continue) then stage 2 works like that: we keep the result H that we computed in stage 1, we need it. Then, for any prime r between B1 and B2 (in our example, 13, 17, 19, 23) we calculate X=H^r and take the gcd(X1,m). Therefore, in stage 2, you can find a factor q ONLY if its particular "k" has that particular "r" in its factors. In our case, taking gcd(H^131,m), and gcd(H^171,m), will NOT reveal any new factors. Only when we move to gcd(H^191, m), we will find the factor 1103. (well, this is a stupid example, because in this case the GCD is m itself, so no factor is found, I should have picked a mersenne number with 4 factors for that, but I am lazy to go back and remake all the calculus, which I did in my head, except for the large exponentiation, for which I used pari). For mersenne numbers, probability of two factors q1 and q2 of the same m, to have respective k1 and k2 which share the same r is very VERY small, especially for large r. You can count such cases on your fingers on one hand. In practice, things are a bit different, the algorithm makes a lot of optimizations in stage 2, it doesn't take the primes one by one, but in "groups", and it precomputes "things" that transform the exponentiation into multiplication, that is why it is very fast, and that is why we do stage 2, otherwise, taking the prime one by one and doing exponentiations, it would be much too slow, and it would make no sense to do it. Yet, to find a multiple factor in stage 2, you will need that the factors that you find in stage 2 share some "r" in the same gcd group. Assuming q_{1}=2k_{1}p+1, q_{2}=2k_{2}p+1, where k_{1,2}=z_{1,2}*r_{1,2}, where z_{1,2} are some integers, and r_{1,2} are some primes. You will need to have q_{1}=2z_{1}r_{1}p+1, q_{2}=2z_{2}r_{2}p+1 with all factors of z_{1} and z_{2} being smaller than B1, and r_{1} and r_{2} being two LARGE primes, larger than B1, not necessary equal, but they must be in the same "gcd group", i.e. very close to eachother, to be found at the next gcd. This is extremely restrictive. So, yes, your probability to find more than one factors in stage 1 is muchMUCH higher than the probability to find more than one factor in stage 2. But about finding factors, in general, multiple or not, more factors are found in stage 2, because probabilistic, if you pick a random number, there is a higher probability that such number has one big factor and many small factors, than it is to have only small factors. Smooth numbers are "rare" and they become rarer as you go up on the numbers axis. See for example why in RSA cryptography, when a key is "weak", or easy to factor (the used primes were not "safe primes" or so), there is a higher probability it was intentionally chosen so, than that is was random picked. Additional, we work here with B2 being 30 or 50 or 100 times larger than B1. Think about that: picking a random number, in a reasonable range (we talk here about the number "q1") what's its probability to have all factors under B1, and what's its probability to have allbutone factors under B1 and one factor only between B1 and 30 or 50 or 100*B1? What's its probability to have all factors but few (2, 3, etc) under B1, and the rest (2, 3, etc) between B1 and B2, but in the same "group" to be gulped at once in the gcd? Mind that we are talking about factors that we find in stage 2, and not "factors that fulfill the condition to be found in stage 2" (stage 2 will stop at the first gcd that finds a factor, even if there are more factors there, while the stage 1 will always find ALL "factors that fulfill the stage 1 condition to be found", i.e. have k's which are B1 smmoth). ECM works somehow similar, but it would be more complicated to explain with an example. You also have to consider the fact that stage 2 is usually done only if stage 1 doesn't return any factor. Last fiddled with by LaurV on 20201124 at 09:22 

20201124, 15:56  #10  
Random Account
Aug 2009
U.S.A.
699_{16} Posts 
Quote:
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
No factors below 2^76. What does this mean? Thanks  king  Information & Answers  2  20180210 15:34 
Known factors  ATH  PrimeNet  2  20140904 19:45 
Missing factors at the 'Known Factors' page  MatWurS530113  PrimeNet  11  20090121 19:08 
factors  ATH  Prime Cullen Prime  16  20070707 13:02 
I need some factors  MatWurS530113  Math  21  20070512 19:36 