The factorization of primorials +/- 1

[Jens K Andersen]

Originally Posted by roger

As for the quotient, I don't know in algebraic terms. I'll have a look through the factor file.

It appears you missed my point. I answered my own question.
You had noted that p(n)#+p(n) is divisible by p(n).
The quotient is (p(n)#+p(n))/p(n) = p(n)#/p(n)+1 = p(n-1)#+1.
This means p(n)#+p(n) = p(n)*(p(n-1)#+1), so you are repeating the work of others who have already factored many numbers of form p(n-1)#+1.

[roger]

I understood your question, I just didn't get to looking into it before reading your answer...

As for repeating other's work, once again the newbie doesn't look at the math. Oh well, it was fun while it lasted.

Regards,

Roger

[Joppe_Bos]

Found a new factor for:
P118# - 1 = 647# - 1 = (c153) = p40 * p113
With p40 = 4460710194647866091044047379244155081819
This completes the factorization of P118# - 1.

Found a new factor for:
P114# + 1 = 619# + 1 = (c222) = p42 * c181
With P42 = 157789955962685027270645602902098758580423

Done 6300 curves on P106# + 1 with B1=43e6
Done 2600 curves on P118# - 1 with B1=11e6

Roger: Too bad you were repeating work, maybe help me on p(n)# +- 1 or work on p(n)# +- p(n+1) see here and here.

[fivemack]

I'm back in England; P109+ is rather over-sieved. I'm running the LA step as I speak and I ought to have an answer this evening.

I'm planning to run P84+ at the 43e6 level on a dual-core at work; one curve takes a bit over six minutes, I've set up for 6000 curves, which ought to be done by the end of the first week in October. That's 700 CPU-hours, a GNFS run would take around 2000, so if I haven't got factors by that point I'll start GNFS and expect a result by the end of the year.

[fivemack]

P109#+1 has largest factor

16637910325093937816348627843064814495390600075720882557526353118578057861799584359

and next-largest factor

1880485480056918062175760642974820848340056891251805332288693

The full factorisation is

P109# + 1 = 154006033 *
74119649873 *
1650289933478587 *
190883459271153022334840970773 *
280818180154859694807701663308663035067 *
1880485480056918062175760642974820848340056891251805332288693 *
16637910325093937816348627843064814495390600075720882557526353118578057861799584359

This took 15 hours on two CPUs for the linear algebra, about two CPU-weeks for polynomial search, and about 1500 CPU-hours for the sieving (started polysearch 14 August, started sieving 20 August, switched to linear algebra 23 September), all on Core2Duo @ 2400MHz. It's the largest GNFS job I've done yet (though I've a C151 on the go which is two-thirds sieved), and thanks to msieve it went very smoothly.

[jasonp]

Originally Posted by fivemack

It's the largest GNFS job I've done yet (though I've a C151 on the go which is two-thirds sieved), and thanks to msieve it went very smoothly.

Awesome. I'll try to get another release out before you finish sieving; I'm working on linear algebra optimizations that slow down the solver by 2-3% but reduce memory use by 15%. As the code gets pushed up to 512 bits that's going to become quite important.

[Joppe_Bos]

Originally Posted by fivemack

This took 15 hours on two CPUs for the linear algebra, about two CPU-weeks for polynomial search, and about 1500 CPU-hours for the sieving (started polysearch 14 August, started sieving 20 August, switched to linear algebra 23 September), all on Core2Duo @ 2400MHz. It's the largest GNFS job I've done yet (though I've a C151 on the go which is two-thirds sieved), and thanks to msieve it went very smoothly.

Wow! Congratulations, certainly a really nice result (and no ECM miss)!

[Joppe_Bos]

Done 6000 curves on P112# - 1 with B1=11e6
Done 7400 curves on P82# + 1 with B1=43e6
No factors found.

[Joppe_Bos]

Done 5200 curves on P76# + 1 with B1=43e6
Done 5100 curves on P86# + 1 with B1=43e6
Done 4700 curves on P114# - 1 with B1=11e6
No factors found.

[fivemack]

Done 5925 curves on P84#+1 with B1=43e6.

No factors found.

I could do this by GNFS, but it'd take about a month and I've got about three weeks of work on Cunningham-project numbers already queued up; unless someone else wants to run GNFS, I'll reserve it now but can't promise factors until mid-December.

[Joppe_Bos]

Originally Posted by fivemack

Done 5925 curves on P84#+1 with B1=43e6.

No factors found.

I could do this by GNFS, but it'd take about a month and I've got about three weeks of work on Cunningham-project numbers already queued up; unless someone else wants to run GNFS, I'll reserve it now but can't promise factors until mid-December.

Thanks, I updated the tables. I am willing to do this number with NFS. It would be fun to learn more about ggnfs, since I have only experience with the CWI suite and just little with ggnfs (only using the factLat script), and how to use it. From what I have read here using msieve for the post-processing seems the way to go (but I will start with searching for a good polynomial for at least a week).