mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2014-01-02, 21:54   #1
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

10001010011012 Posts
Default ECM vs P1.

I seem to recall a post about a year ago where someone said doing a P1 is like doing all ECM curves at once for the same B1/B2. Now if I misunderstood then the rest of this post might be gibberish.

If I am on the right track then it would lead me to believe they run a very similar code base and should perform equally.

However, I have a PC (granted old) that can do almost 2 GhzDays per day of P1 and less than 1.5 of ECM. If relevant the P1 was in the 64M range and ECM on Fermat 13 (8192).
petrw1 is offline   Reply With Quote
Old 2014-01-02, 22:58   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by petrw1 View Post
I seem to recall a post about a year ago where someone said doing a P1 is like doing all ECM curves at once for the same B1/B2. Now if I misunderstood then the rest of this post might be gibberish.

If I am on the right track then it would lead me to believe they run a very similar code base and should perform equally.
Rather than rely on some ill-founded belief, why don't you
take the time and effort to learn how these algorithms actually work???
Or are you part of the IGG that is too lazy or unmotivated to be
bothered with something as trite as learning about this subject?

Quote:
However, I have a PC (granted old) that can do almost 2 GhzDays per day of P1 and less than 1.5 of ECM. If relevant the P1 was in the 64M range and ECM on Fermat 13 (8192).
You are severely confused. Let us take this one piece at a time.

I will assume that you mean "P-1" when you write P1.

(1) Where did you get the idea that running P-1 was equivalent to doing all ECM curves at once? Running P-1 is equivalent to running a
single elliptic curve.

(2) Comparing ECM running on a number of 5678 digits versus running
P-1 on a number of 44million digits is meshugah. Furthermore, I suspect
that you were not running an FFT Stage 2 for P-1. Its memory requirements are so vast that the machine would be paging continuously.
A machine running at (say) 2Ghz will yield 2Ghz days of CPU time per day
unless it is busy paging. I expect that ECM was doing some paging
and that you were only running Stage 1 of P-1.

If not, please say what B1/B2 limits you were using. Were you using a
GPU?

How much memory does the machine have?
R.D. Silverman is offline   Reply With Quote
Old 2014-01-02, 23:06   #3
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by petrw1 View Post
I seem to recall a post about a year ago where someone said doing a P1 is like doing all ECM curves at once for the same B1/B2. Now if I misunderstood then the rest of this post might be gibberish.
This is not an accurate summary of P-1.
I'd say instead that:
In P-1 factoring, you are interested in the factorization of the number 1 less than P (P-1).
In ECM you are interested in the factorization of some specific number P+b where b is about the size of P, (something like -sqrt{P} < b < sqrt{P}, which, roughly, means that the first half of the digits are the same as P and the rest are random) and can be calculated by a function where f(sigma, P) = b. Being able to choose different sigmas means that it's something like being able to run P-1 multiple times.
Which means that P-1 is like running a single curve of ECM where b = -1. For Mersenne and Fermat numbers, this happens to nicely coincide with known facts about what their factors can be, making it much more efficient than ECM at similar bounds.
Quote:
Originally Posted by petrw1 View Post
If I am on the right track then it would lead me to believe they run a very similar code base and should perform equally.
However, this is an accurate conclusion: both (in modern implementations) use FFTs, have a stage 1 based on B1 bounds, and a high-memory stage 2 based on B2 bounds.

Quote:
Originally Posted by petrw1 View Post
However, I have a PC (granted old) that can do almost 2 GhzDays per day of P1 and less than 1.5 of ECM. If relevant the P1 was in the 64M range and ECM on Fermat 13 (8192).
Both P-1 and ECM run FFTs, involving some significant amount of memory in stage 2. The biggest variable here is: How much memory was being used? Memory speed differences could be causing the difference between your machine and the reference machine (the machine whose benchmark was used to calculate what constitutes a GHz-day - I believe it's a Core 2 Duo).

Another smaller variable: What FFT size was being used in each test? Different CPUs can scale the speeds at different FFT sizes differently.

At a guess, your assigned memory or memory bandwidth is lower than the reference machine's. You might be able to improve this by upping the memory Prime95 can use, and using the fastest dual-channel memory configuration possible for your setup.

Last fiddled with by Mini-Geek on 2014-01-02 at 23:10
Mini-Geek is offline   Reply With Quote
Old 2014-01-02, 23:10   #4
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

221068 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
How much memory does the machine have?
(In the voice of AGENT SMITH) MR. SILVERMAN...

Sorry, that's all I've got....
chalsall is offline   Reply With Quote
Old 2014-01-02, 23:27   #5
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

43·103 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Rather than rely on some ill-founded belief, why don't you
take the time and effort to learn how these algorithms actually work???
Or are you part of the IGG that is too lazy or unmotivated to be
bothered with something as trite as learning about this subject?

..... A combination of too busy and sufficiently lacking in the fundamentals of any of these topics to learn enough to answer my question.

You are severely confused. Let us take this one piece at a time.

I will assume that you mean "P-1" when you write P1.
......... yes
(1) Where did you get the idea that running P-1 was equivalent to doing all ECM curves at once? Running P-1 is equivalent to running a
single elliptic curve.
.........I stand corrected.
(2) Comparing ECM running on a number of 5678 digits versus running
P-1 on a number of 44million digits is meshugah. Furthermore, I suspect
that you were not running an FFT Stage 2 for P-1. Its memory requirements are so vast that the machine would be paging continuously.
A machine running at (say) 2Ghz will yield 2Ghz days of CPU time per day
unless it is busy paging. I expect that ECM was doing some paging
and that you were only running Stage 1 of P-1.

If not, please say what B1/B2 limits you were using. Were you using a
GPU?
..........B1=260000000, B2=26000000000 for ECM of 8192.
..........B1=570000, B2=9975000 for P-1 of 64M
..........No GPU
How much memory does the machine have?
........1000Meg. 800 allocated to Prime95
See dots above. Thx for answering and questioning.
petrw1 is offline   Reply With Quote
Old 2014-01-02, 23:54   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by petrw1 View Post
See dots above. Thx for answering and questioning.
1G is simply not enough memory for running Step 2 of either P-1
or ECM in an efficient manner.

What code are you using? Are you using GMP-ECM? It allows
one to limit memory usage in Step 2 by partitioning the data
that is generated into pieces.

Of course, one pays a penalty for this partitioning. How much of a penalty
depends on the size of the pieces relative to the amount of total
memory.

Your computer is simply underpowered and undersized by current
standards.

You would be well advised to spend a few bucks and buy more memory.
For (say) $50 you will enhance your performance by a fair bit.
R.D. Silverman is offline   Reply With Quote
Old 2014-01-02, 23:59   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by petrw1 View Post
See dots above. Thx for answering and questioning.
You wrote in response:

Quote:
..... A combination of too busy and sufficiently lacking in the fundamentals of any of these topics to learn enough to answer my question.

Lack of fundamentals is correctable. It just requires motivation and
dedication. We can help guide you.

How much mathematics have you studied? Do you have a STEM degree?
How well did you do in your math classes in high school?
R.D. Silverman is offline   Reply With Quote
Old 2014-01-03, 01:26   #8
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

172710 Posts
Default

Message deleted by TheMawn

Last fiddled with by TheMawn on 2014-01-03 at 01:28 Reason: Duplicate Post somehow
TheMawn is offline   Reply With Quote
Old 2014-01-03, 01:28   #9
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

32778 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Your computer is simply underpowered and undersized by current standards.

You would be well advised to spend a few bucks and buy more memory. For (say) $50 you will enhance your performance by a fair bit.
Note to petrw1: Your older machine will very likely be using DDR2 memory. DDR2 is more expensive as it is an outdated standard. Newegg has a bunch but it's not cheap. Might not be worth your while.


Quote:
Originally Posted by R.D. Silverman View Post
Lack of fundamentals is correctable. It just requires motivation and dedication. We can help guide you.

How much mathematics have you studied? Do you have a STEM degree? How well did you do in your math classes in high school?
I've never fully understood that math either. I visit the P-1 and ECM pages on the mersenne wiki but I never get very far. I'll follow this discussion along out of curiosity.
TheMawn is offline   Reply With Quote
Old 2014-01-03, 03:49   #10
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

43·103 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
You wrote in response:




Lack of fundamentals is correctable. It just requires motivation and
dedication. We can help guide you.

How much mathematics have you studied? Do you have a STEM degree?
How well did you do in your math classes in high school?
High school Math, though done well, was completed 37 year ago.
A University degree in Computer Science minoring in Math was completed 33 years ago.
33 years of IT work devoid of Math pretty much rusted all the math brain cells.
Don't know what STEM is.

And with a full time job still going; a wife and 4 kids and 3 grandkids and a hobby in music....as much as I would love to learn more about this stuff ... can't do it at this time That is why I need to concede that the best I can do is ask questions and hope someone is willing to give a quick and simple answer.

Sorry...and thanks again.

P.S. I agree that I should give this PC a proper burial. Plans are underway; in the meantime I hear CheeseHead "100.01 MPH > 100 MPH"

Last fiddled with by petrw1 on 2014-01-03 at 03:50
petrw1 is offline   Reply With Quote
Old 2014-01-03, 10:46   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by petrw1 View Post
High school Math, though done well, was completed 37 year ago.
A University degree in Computer Science minoring in Math was completed 33 years ago.
33 years of IT work devoid of Math pretty much rusted all the math brain cells.
Don't know what STEM is.

And with a full time job still going; a wife and 4 kids and 3 grandkids and a hobby in music....as much as I would love to learn more about this stuff ... can't do it at this time That is why I need to concede that the best I can do is ask questions and hope someone is willing to give a quick and simple answer.
The problem is that quite often, the answers are neither quick nor
simple. As in this case. Understanding the performance of ECM and
P-1 require fairly deep understanding not only of their underpinnings
but also of computer architecture.



Music? Consider how long it takes to learn to play (say) Chopin on
the piano. People are willing to devote time to things they like.
However, everyone here while claiming to be interested in this subject
always show disdain for taking the time to learn it.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 01:59.

Thu Oct 29 01:59:52 UTC 2020 up 48 days, 23:10, 1 user, load averages: 1.72, 1.66, 1.76

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.