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.

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.

[QUOTE=Belteshazzar;252709]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).
[/QUOTE]

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.

[QUOTE=R.D. Silverman;252715]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.[/QUOTE]

It was done. xilman finished it 10 years ago.

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

[QUOTE=R.D. Silverman;252718]It was done. xilman finished it 10 years ago.

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

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

"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- [I]if you'd bothered to read it[/I]- a [URL="http://www.mersenneforum.org/showthread.php?t=14265"]thread on this forum[/URL] just a few months ago said the factorization of 105!+2 is wanted for an OEIS sequence ([URL="http://oeis.org/A063684"]A063684[/URL]). 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 [URL="http://www.mersenneforum.org/showthread.php?t=7105"]discussion on this forum [/URL]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.

[QUOTE=Belteshazzar;252722]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. "[/quote]
That advice is pre-msieve. Msieve has tremendously advanced polynomial selection and post processing.
[QUOTE=Belteshazzar;252722]A [URL="http://www.mersenneforum.org/showthread.php?t=7105"]discussion on this forum [/URL]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[/QUOTE]
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.

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.

[QUOTE=Belteshazzar;252722]"Typical newbie." Way to make a friendly introduction. What a great feeling of community there is around here.[/QUOTE]

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.

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

[QUOTE=wblipp;252739]Getting dissed by Bob Silverman is a rite of passage here.[/QUOTE]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

[QUOTE=xilman;252757]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[/QUOTE]

[i]My[/i] advice to newbies:

(1) Do your background reading/research FIRST.
(2) Engage brain before putting computer into gear. --> Compute first,
think later is a bad way to go.
(3) Ask questions.

[QUOTE=R.D. Silverman;252774][i]My[/i] advice to newbies:

(1) Do your background reading/research FIRST.
(2) Engage brain before putting computer into gear. --> Compute first,
think later is a bad way to go.
(3) Ask questions.[/QUOTE]

This is exactly what he did, IMO. Did you *read* his post? Or skim it and dismiss it?

[QUOTE=bsquared;252776]This is exactly what he did, IMO. Did you *read* his post? Or skim it and dismiss it?[/QUOTE]

Really? The content of his post strongly suggested that he thought
that a number near C160-170 was state-of-the-art.

Nor did he [i]ask[/i] whether anyone else thought that doing that
number would be mathematically interesting.

Before [b][i]I[/i][/b] start doing work in an area new to me, I ask
those already working in that area:

(1) What problems are interesting?
(2) What do I need to learn? What do I need to read? What is the level
of effort needed to learn the basic background?
(3) What a newbie (such as I would be) might contribute?

[QUOTE=R.D. Silverman;252781]

Nor did he [i]ask[/i] whether anyone else thought that doing that
number would be mathematically interesting.
[/QUOTE]

It was clear (at least to me) that he was doing this for the benefit of people who had already expressed interest in the result (OEIS). Leave alone for the moment whether it is *mathematically* interesting - the result itself is interesting to people for reasons of their own. He was doing the best he could to help, and was looking for advice as to how to be of more help. Perfectly fine, in my book.

A factorization of 105!+2 (which I do not believe is complete) would help with extending the sequence [URL="http://http://oeis.org/search?q=A063684&language=english&go=Search"]A063684[/URL] in the OEIS.

I have previously run 4590 ECM curves with b1=11e6.

[QUOTE=Belteshazzar;252709]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).

... 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.[/QUOTE]
For 105!+2 cofactor, you'd rather want it to be semiprime and 105 will be the next term of that sequence. But your laptop will take more than a year to finish this number with GNFS. You could warm up by factoring the c136 cofactor of 108!+2 (which is the next candidate). Btw, 127 is the term of [URL="http://oeis.org/A063684"]A063684[/URL] (out of order).

[QUOTE=R.D. Silverman;252774][I]My[/I] advice to newbies:

(1) Do your background reading/research FIRST.
(2) Engage brain before putting computer into gear. --> Compute first,
think later is a bad way to go.
(3) Ask questions.[/QUOTE]That, IMO, is some of Bob's advice which you [i]should[/i] follow to the letter.

Paul

[QUOTE]Really? The content of his post strongly suggested that he thought
that a number near C160-170 was state-of-the-art.[/QUOTE]My "curiosity about where the state of the art was in factorization" had little to do with what the current records are- that has almost as much to do with where the state of the art is in computer hardware, clustering, etc as it does with the state of the art in factorization algorithms. GNFS and ECM are state-of-the-art, and I don't have to be factoring 240-digit numbers to get a better idea of how they perform and how one should use them.

[QUOTE]
Nor did he [I]ask[/I] whether anyone else thought that doing that
number would be mathematically interesting.

Before [B][I]I[/I][/B] start doing work in an area new to me, I ask
those already working in that area:

(1) What problems are interesting?
(2) What do I need to learn? What do I need to read? What is the level
of effort needed to learn the basic background?
(3) What a newbie (such as I would be) might contribute? [/QUOTE]I wanted to try these algorithms out, and the post about OEIS was sufficiently interesting to convince me to try them out on this rather than on random input. If there were numbers whose factorization would have extremely strong mathematical interest and whose factorization was within the reach of my laptop, I would anticipate they'd have already been done well before now.

I read enough to find the best known algorithms, download a couple of open-source implementations, and go through their documentation. Seemed like enough initial reading to me. Choosing to leave my laptop in one location to run these for a while isn't a career change.

As far as learning the background, I'm a math grad student but haven't ever taken a number theory course and don't really have time to go through a proof of ECM or GNFS. I've had plenty of algebra and a little algebraic geometry so I have a faint inkling of what's involved; though I'm sure there's lots of interesting math there, there are only so many hours in the day.
[QUOTE]
I have previously run 4590 ECM curves with b1=11e6. [/QUOTE]Thanks for piping up. With my 6698 curves with the same b1, looks like it's time to move on.

Got 105!+2- yes, the c163 was semiprime. It was a stroke of luck to get it so quickly after bumping b1 up- expected # of curves for a 49-digit factor using b1=43e6 is probably >5000, I got it after roughly 200.

Batalov, what kind of ECM pretesting has already gone into the c136 cofactor of 108!+2?

Report it to [URL]http://factordb.com/index.php?query=105%21%2B2[/URL]
and OEIS.

The c136 should be ready for GNFS by now.

I figured it would be, so I got GNFS started, but since polynomial selection seems to only be using one core, I'd left the other core continuing with YAFU's factoring routine (which I'd started in order to find the c136 cofactor- I didn't know about factordb- and which was doing ECM w/b1=10M). So I'll just free up that core now.

Got it- sieving took ~9 days. p59*p78, factors reported to factordb.

Well, having read up some more about the algorithms in the meantime, my curiosity is satisfied for now, and I'll be glad to have my laptop freed up. I may visit again in the future if I end up doing more number theory or get hardware more fit for the task (say, a Bulldozer desktop and a CUDA-capable card).

Thanks!

Now, 109!+2 [URL="http://mersenneforum.org/showthread.php?p=254317#post254317"]is factored[/URL] and 109 is not a member of the sequence, then 110!+2 is factored and 110 is a member. Next candidates are 112 and 114.

[FONT=Arial Narrow]Input number is (2+110!)/446 (176 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=664425596
Step 1 took 33854ms
Step 2 took 13759ms
********** Factor found in step 2: 144476918413758184246036836336545025029
Found probable prime factor of 39 digits: 144476918413758184246036836336545025029
Probable prime cofactor ((2+110!)/446)/144476918413758184246036836336545025029 has 138 digits
[/FONT]

I have run 17900 curves with b1=110e6 and 4000 curves with b1=300e6 on 114!+1 without finding a factor.
114!+2 is easily factored and has an even number of factors.

Yes, both 114!+1 and 115!+1 are tough nuts on this road.
(This was only 'easy' until the +2 side caught up with the +1 bleeding edge.) After them, there are 118, 119, 120, etc etc...

It has been brought to my attention that 101 has not been definitively ruled out of this sequence. I do not appear to have a complete factorization for 101!+2 (and likely never had one). The remaining C145 almost certainly splits into two primes which would eliminate 101.

Anyone want to have a crack at it?

If you post or PM the C145 I'll have a go. It'll take me about 3 weeks though.

Chris K

[QUOTE=chris2be8;254728]If you post or PM the C145 I'll have a go. It'll take me about 3 weeks though.[/QUOTE]

[CODE]101!+2 = 2.76651.42727279519.C145

C145=1439037017974459737209176591173154490623757641646671713778278703958022205299519888479141257083536507005774582500092299135064595968911493780619229
[/CODE]

I've run over 5000 curves with b1=11e6, and a few with b1=110e6 without breaking it, so it should yield a good size factor.

I'll run ecm at 43e6 for a few days. T50 is about the right amount of ecm to to run before starting gnfs. If anyone wants to help just post how many you've run and I'll post when we have enough.

Chris K

167!+2 = 2.p13.p14.3693165342354759209.p256

[QUOTE=sean;254731]I've run over 5000 curves with b1=11e6, and a few with b1=110e6 without breaking it, so it should yield a good size factor.[/QUOTE]

How many curves did you run with b1=110e6?

Chris K

[QUOTE=chris2be8;254913]How many curves did you run with b1=110e6?[/QUOTE]

Only 60.

101!+2 has had about 2/3 of t50, which should be enough. I'm starting GNFS now.

Chris K

prp60 factor: 587729207511810516885232785200956763621863606981651963932241
prp85 factor: 2448469464477894009131719983156935384410413013804660295414240456460532653836441950669

Chris K

Thanks for that, I'll update the corresponding OEIS entry.