mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2018-12-01, 14:06   #1
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

2×7×112 Posts
Default ECM B1 vs B2

I have been studying the ECM Progress page on mersenne.org off and on for several days. As it goes across, the B1 values get really large, rapidly. Running some of these high values could be really time consuming, considering B2 = B1 * 100.

I do not understand why B1 must be so large in these cases. Here is my question: What happens in B1 that does not happen in B2, and vice-versa?

Thank you.
storm5510 is offline   Reply With Quote
Old 2018-12-01, 15:26   #2
wpolly
 
wpolly's Avatar
 
Sep 2002
Vienna, Austria

DB16 Posts
Default

The main difference is that the ECM group order can have many prime factors below B1, and only one between B1 and B2.
wpolly is offline   Reply With Quote
Old 2018-12-01, 15:30   #3
VictordeHolland
 
VictordeHolland's Avatar
 
"Victor de Hollander"
Aug 2011
the Netherlands

23·3·72 Posts
Default

Short answer:
You need larger B1&B2 values to find larger factors.
VictordeHolland is offline   Reply With Quote
Old 2018-12-01, 15:49   #4
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

2×7×112 Posts
Default

Quote:
Originally Posted by wpolly View Post
The main difference is that the ECM group order can have many prime factors below B1, and only one between B1 and B2.

Only one between B1 and B2. I find that amazing. Is there a specific reason for only one?
storm5510 is offline   Reply With Quote
Old 2018-12-01, 19:41   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1039310 Posts
Default

Quote:
Originally Posted by storm5510 View Post
Only one between B1 and B2. I find that amazing. Is there a specific reason for only one?
Yes.

The complete answer is left as an exercise. You should learn at least a little about the ECM (and the P-1 method from which it was developed) before asking questions like these, not afterwards.

xilman is online now   Reply With Quote
Old 2018-12-01, 23:50   #6
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

69E16 Posts
Default

Quote:
Originally Posted by xilman View Post
Yes.

The complete answer is left as an exercise. You should learn at least a little about the ECM (and the P-1 method from which it was developed) before asking questions like these, not afterwards.
I should have known better than to ask. I am not a mathematician. I looked at Wiki results before asking. All the formulas shown there, I do not understand. At my age, it is too late to start. End of story.
storm5510 is offline   Reply With Quote
Old 2018-12-02, 00:59   #7
VictordeHolland
 
VictordeHolland's Avatar
 
"Victor de Hollander"
Aug 2011
the Netherlands

23·3·72 Posts
Default

Quote:
Originally Posted by storm5510 View Post
At my age, it is too late to start.
It' never too late to learn
VictordeHolland is offline   Reply With Quote
Old 2018-12-02, 02:00   #8
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

169410 Posts
Default

Quote:
Originally Posted by VictordeHolland View Post
It' never too late to learn.

I agree. However, one must be able to comprehend the material which they are studying. I cannot.
storm5510 is offline   Reply With Quote
Old 2018-12-02, 02:56   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,939 Posts
Default

Quote:
Originally Posted by storm5510 View Post
Only one between B1 and B2. I find that amazing. Is there a specific reason for only one?
You're looking at it the wrong way. It's not about the number being special in any way; it's about us choosing parameters that are convenient for us in our search.

You could easily set up a method with just a B1 that looked for numbers with all its prime (power) divisors smaller than B1. But then you might have to make B1 large, and that's hard. As a compromise, you can design the method in a different way: instead of all the primes needing to be smaller than B1, you can have one exception which is bigger than B1. But it still has to be smaller than B2. So running B1 = x, B2 = y is a way to avoid running the first method with just B1 = y.

Does that make sense?

Last fiddled with by CRGreathouse on 2018-12-02 at 02:57
CRGreathouse is offline   Reply With Quote
Old 2018-12-02, 04:47   #10
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

11×409 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
You could easily set up a method with just a B1 that looked for numbers with all its prime (power) divisors smaller than B1. But then you might have to make B1 large, and that's hard. As a compromise, you can design the method in a different way: instead of all the primes needing to be smaller than B1, you can have one exception which is bigger than B1. But it still has to be smaller than B2. So running B1 = x, B2 = y is a way to avoid running the first method with just B1 = y.

Does that make sense?
I wanted to say something like this, but couldn't find such an eloquent way. The key to this description is that the method that allows one factor between B1 and B2 is over 100 times faster than simply making B1 the size of B2; Note the time taken in stage 2 is less than stage 1, for a range 100x larger.

Roughly speaking, we could search with B1 = 2M, allowing any number of factors less than 2M; or, for a similar amount of time, we can search to B1 = 1M and B2 = 100M, which allows any number of factors below 1M *and* one between 1M and 100M. The latter case covers more situations than the former, so we use Stage 2 and a B2.
VBCurtis is offline   Reply With Quote
Old 2018-12-05, 15:20   #11
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

2×7×112 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
You're looking at it the wrong way. It's not about the number being special in any way; it's about us choosing parameters that are convenient for us in our search.

You could easily set up a method with just a B1 that looked for numbers with all its prime (power) divisors smaller than B1. But then you might have to make B1 large, and that's hard. As a compromise, you can design the method in a different way: instead of all the primes needing to be smaller than B1, you can have one exception which is bigger than B1. But it still has to be smaller than B2. So running B1 = x, B2 = y is a way to avoid running the first method with just B1 = y.

Does that make sense?
Yes it does, and thank you for your response!

During my studying, I matched B1 and B2. This became cumbersome rapidly. I also experimented with B2 = B1 * 10. This didn't really cover the ground it needed to.

Quote:
Originally Posted by VBCurtis
I wanted to say something like this, but couldn't find such an eloquent way. The key to this description is that the method that allows one factor between B1 and B2 is over 100 times faster than simply making B1 the size of B2; Note the time taken in stage 2 is less than stage 1, for a range 100x larger.

Roughly speaking, we could search with B1 = 2M, allowing any number of factors less than 2M; or, for a similar amount of time, we can search to B1 = 1M and B2 = 100M, which allows any number of factors below 1M *and* one between 1M and 100M. The latter case covers more situations than the former, so we use Stage 2 and a B2.
If I get this correctly, Stage 1 will complete the value of its setting, regardless of whether it finds a factor, or not. B2 will stop after one factor is found.

I want to emphasize that all of this was for a leaning experience, only. What the server gives me, I run as is.

Thank you all for your time. Most kind.
storm5510 is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 10:14.

Wed Dec 2 10:14:54 UTC 2020 up 83 days, 7:25, 1 user, load averages: 1.92, 1.88, 1.86

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.