Newbie advice

Belteshazzar · 2011-02-16, 21:25

Wanting to satisfy curiosity about where the state of the art was in factorization and at the same time do something marginally mathematically useful (rather than, say, RSA factors etc), I saw the thread on factorizations needed for OEIS sequences and decided to try factoring 105!+2 on my laptop (1.86 GHz Core2 Duo).

Yafu 1.23 found the factor 193957 pretty quickly and then started doing ECM on the remaining c163- I let it go for a day or so, had to restart the program, found that the deep pretest option didn't start all that deep after all, and decided to try running gmp-ecm directly instead.

So what I ran was ecm -c 14000 -chkpnt fprogress -n -save residues 11e6 (I was confused by what I'd read in the "Which bits of gmp-ecm are now parallel? " thread and thought that doing the -save would allow for doing stage 2 in parallel later- I'd think that I/O isn't slowing things too much tho since I've got a SSD). Right now it's on run 4287 of 14000, taking about 78 seconds for each step1 and 35 seconds for each step2- it's had ~137 hours of CPU time.

What would be a smarter way to attack this? Am I right to guess that this is too big for NFS etc- especially on this machine? Should I be patient with the current run, change options (esp. B1), try to find a way to run in parallel, or just throw up my hands and leave this work to be done by somebody with a faster machine? If the smallest factor is much bigger than the current target of 45 digits then it's going to be semiprime and the smallest factor could be way out of my reach.

bsquared · 2011-02-16, 22:05

The best way to parallelize GMP-ECM would be to run two copies of the program at the same time, each loaded with half as many curves. Nothing fancy.

I don't know how many curves have already been thrown at this number, so I can't give advice on what B1 is appropriate. A C163 is certainly within the range of GNFS (although probably not using just your laptop), but it should be pretested with ECM up to at least t50, I think.

R.D. Silverman · 2011-02-16, 22:22

Quote:

Originally Posted by Belteshazzar

Wanting to satisfy curiosity about where the state of the art was in factorization and at the same time do something marginally mathematically useful (rather than, say, RSA factors etc), I saw the thread on factorizations needed for OEIS sequences and decided to try factoring 105!+2 on my laptop (1.86 GHz Core2 Duo).

I thought that this number had already been done?

These days, a C163 is rather easy with GNFS.

I can't imagine though how it might be mathematically useful
in any way.

R.D. Silverman · 2011-02-16, 22:30

Quote:

Originally Posted by R.D. Silverman

I thought that this number had already been done?

These days, a C163 is rather easy with GNFS.

I can't imagine though how it might be mathematically useful
in any way.

It was done. xilman finished it 10 years ago.

Typical newbie. Compute first, ask questions/look up the answer later.

bsquared · 2011-02-16, 22:38

Quote:

Originally Posted by R.D. Silverman

It was done. xilman finished it 10 years ago.

Typical newbie. Compute first, ask questions/look up the answer later.

You're probably thinking of 105!+1. He's asking about 105!+2. Not that it is any more or less important, but AFAIK, it has not been completed yet.

Belteshazzar · 2011-02-16, 23:07

"Typical newbie." Way to make a friendly introduction. What a great feeling of community there is around here.

If somebody came asking a bunch of questions without trying some things out themselves you'd dismiss them for failing to demonstrate independent thought. Somebody comes having read the docs and the forum, searched for answers, and put a little effort into doing something themselves, and you're on their case for not having asked before. Nice.

As you might have noticed in my post- if you'd bothered to read it- a thread on this forum just a few months ago said the factorization of 105!+2 is wanted for an OEIS sequence (A063684). Sure, it's not super important or anything- I wasn't claiming it was, just that it had some marginal mathematical utility. If it'd already been done I would have anticipated that somebody would have mentioned that fact in the thread.

The ggnfs documentation says explicitly "In its current state, GGNFS will not factor anything extraordinarily large (i.e., it will not do a 160 digit general number)... Please don't send me an email asking what needs to be fixed - you can discover the issues one at a time by yourself by attempting to factor successively larger and larger numbers (say, 140,145,150,...), until you encounter the problems. " A discussion on this forum a few years ago suggested a c140 would take a couple of months on hardware comparable to mine and had some trouble with convergence. Though I knew the docs were a little out of date and the post was a little old, I would think I might be excused for wondering about the viability of trying that on my machine.

Thanks, bsquared, for your helpful response.

axn · 2011-02-17, 00:07

Quote:

Originally Posted by Belteshazzar

The ggnfs documentation says explicitly "In its current state, GGNFS will not factor anything extraordinarily large (i.e., it will not do a 160 digit general number)... Please don't send me an email asking what needs to be fixed - you can discover the issues one at a time by yourself by attempting to factor successively larger and larger numbers (say, 140,145,150,...), until you encounter the problems. "

That advice is pre-msieve. Msieve has tremendously advanced polynomial selection and post processing.

Quote:

Originally Posted by Belteshazzar

A discussion on this forum a few years ago suggested a c140 would take a couple of months on hardware comparable to mine and had some trouble with convergence. Though I knew the docs were a little out of date and the post was a little old, I would think I might be excused for wondering about the viability of trying that on my machine

C140 should be doable in your machine in < 2 weeks (using the linux 64-bit optimized siever). C163 should be about 16 times harder (using the doubling-every-6-digits rule).
If you've a CUDA-enabled graphics card, you could potentially improve the polynomial search also.

jasonp · 2011-02-17, 00:28

You actually should not believe anything the GGNFS documentation (or Chris Monico's web page) says, it was last updated around 2005. The msieve documentation is also very out of date (2007 :), I don't have the time to overhaul it, especially for NFS.

wblipp · 2011-02-17, 04:14

Quote:

Originally Posted by Belteshazzar

"Typical newbie." Way to make a friendly introduction. What a great feeling of community there is around here.

Getting dissed by Bob Silverman is a rite of passage here. It's happened to most of us. Think of him as our village curmudgeon, tolerated in spite of his abyssmal social skills because he happens to be a talented mathematician who occasionally drops nuggets among his gripes. Congratulations on achieving this milestone so early in you MersenneForum career.

bsquared · 2011-02-17, 04:26

Ah yes, I still have memories of my rite of passage... it's somewhere in the homogeneous cunninghams thread, I think.

xilman · 2011-02-17, 10:22

Quote:

Originally Posted by wblipp

Getting dissed by Bob Silverman is a rite of passage here.

And if not here, likely somewhere else on the interweb thingy.

My advice to newbies is two-fold. Pay attention to Bob's advice (but don't necessarily follow it to the letter) and grow a thick skin,

Paul

2011-02-16, 21:25	#1
Belteshazzar Feb 2011 2⁵ Posts	Newbie advice Wanting to satisfy curiosity about where the state of the art was in factorization and at the same time do something marginally mathematically useful (rather than, say, RSA factors etc), I saw the thread on factorizations needed for OEIS sequences and decided to try factoring 105!+2 on my laptop (1.86 GHz Core2 Duo). Yafu 1.23 found the factor 193957 pretty quickly and then started doing ECM on the remaining c163- I let it go for a day or so, had to restart the program, found that the deep pretest option didn't start all that deep after all, and decided to try running gmp-ecm directly instead. So what I ran was ecm -c 14000 -chkpnt fprogress -n -save residues 11e6 (I was confused by what I'd read in the "Which bits of gmp-ecm are now parallel? " thread and thought that doing the -save would allow for doing stage 2 in parallel later- I'd think that I/O isn't slowing things too much tho since I've got a SSD). Right now it's on run 4287 of 14000, taking about 78 seconds for each step1 and 35 seconds for each step2- it's had ~137 hours of CPU time. What would be a smarter way to attack this? Am I right to guess that this is too big for NFS etc- especially on this machine? Should I be patient with the current run, change options (esp. B1), try to find a way to run in parallel, or just throw up my hands and leave this work to be done by somebody with a faster machine? If the smallest factor is much bigger than the current target of 45 digits then it's going to be semiprime and the smallest factor could be way out of my reach.

2011-02-17, 04:26	#10
bsquared "Ben" Feb 2007 110110111100₂ Posts	Ah yes, I still have memories of my rite of passage... it's somewhere in the homogeneous cunninghams thread, I think. Last fiddled with by wblipp on 2011-02-17 at 05:07 Reason: typo rite

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
need tablet pc advice for newbie mom	jasong	jasong	10	2010-12-25 05:27
Advice for PSU	em99010pepe	Hardware	1	2010-01-31 23:48
Looking for advice for a new PC....	petrw1	Hardware	39	2009-07-11 13:38
P95 newbie looking for advice	francais	Hardware	2	2008-04-23 01:01
New LMH needs advice.	M0CZY	Lone Mersenne Hunters	2	2005-05-24 20:05

2011-02-16, 22:05	#2
bsquared "Ben" Feb 2007 2²×3×293 Posts	The best way to parallelize GMP-ECM would be to run two copies of the program at the same time, each loaded with half as many curves. Nothing fancy. I don't know how many curves have already been thrown at this number, so I can't give advice on what B1 is appropriate. A C163 is certainly within the range of GNFS (although probably not using just your laptop), but it should be pretested with ECM up to at least t50, I think.

2011-02-16, 23:07	#6
Belteshazzar Feb 2011 2⁵ Posts	"Typical newbie." Way to make a friendly introduction. What a great feeling of community there is around here. If somebody came asking a bunch of questions without trying some things out themselves you'd dismiss them for failing to demonstrate independent thought. Somebody comes having read the docs and the forum, searched for answers, and put a little effort into doing something themselves, and you're on their case for not having asked before. Nice. As you might have noticed in my post- if you'd bothered to read it- a thread on this forum just a few months ago said the factorization of 105!+2 is wanted for an OEIS sequence (A063684). Sure, it's not super important or anything- I wasn't claiming it was, just that it had some marginal mathematical utility. If it'd already been done I would have anticipated that somebody would have mentioned that fact in the thread. The ggnfs documentation says explicitly "In its current state, GGNFS will not factor anything extraordinarily large (i.e., it will not do a 160 digit general number)... Please don't send me an email asking what needs to be fixed - you can discover the issues one at a time by yourself by attempting to factor successively larger and larger numbers (say, 140,145,150,...), until you encounter the problems. " A discussion on this forum a few years ago suggested a c140 would take a couple of months on hardware comparable to mine and had some trouble with convergence. Though I knew the docs were a little out of date and the post was a little old, I would think I might be excused for wondering about the viability of trying that on my machine. Thanks, bsquared, for your helpful response.

2011-02-17, 00:28	#8
jasonp Tribal Bullet Oct 2004 3×1,181 Posts	You actually should not believe anything the GGNFS documentation (or Chris Monico's web page) says, it was last updated around 2005. The msieve documentation is also very out of date (2007 :), I don't have the time to overhaul it, especially for NFS.