How about doing for NFS what you have done for QS? i.e. a fast, reliable, easy to use program.
I'm not knocking other implementations, but many of them require the user to know and understand the NFS algorithm, not an easy task!

Seems like I just caused your 0.87 code to segfault. I tried compiling the code myself in cygwin and also used the precompiled windows .exe you have on your site with the same results.

If I use this number as an input:
[CODE]6948657305861221242055119627832786620828691646469755332126824375475434961384820837143581386953122298202967515764467715654575036306167878847548912232432868054866149086971620199924489[/CODE]

The software returns these results:
[CODE]Msieve v. 0.87
random seeds: 00000d60 41bcc6a3
input to factor: 694865730586122124205511962783278662082869164646975533212682437
54754349613848208371435813869531222982029675157644677156545750363061678788475489
12232432868054866149086971620199924489
factoring 6948657305861221242055119627832786620828691646469755332126824375475434
96138482083714358138695312229820296751576446771565457503630616787884754891223243
2868054866149086971620199924489
Sun Dec 12 17:34:42 2004
prime factor: 2351
prime factor: 4513
prime factor: 8191
Segmentation fault (core dumped)[/CODE]

So far that is the only value that has segfaulted, others seem to work fine.

Jeff.

[QUOTE=jasonp]So it looks like the basics are all there for Msieve, and AFAICT it's loads faster than other QS programs. Where do I go from here?[/QUOTE]

One thing that would be convenient/useful is the ability to use equations for input. So feeding the program something like [b](2^7079-1)/14159[/b] instead of having to expand that out to the full single integer value.

Another C100 factored
 

[code]
Msieve v. 0.86
random seeds: 00000218 41b9ea1d
factoring 8996108210139462978073236775295867026748488312730764496163714592360959433517967920644604084256992347
Fri Dec 10 19:25:33 2004
using multiplier of 7
Fri Dec 10 19:25:36 2004
using sieve block of 65536
using a sieve bound of 1878181 (70333 primes)
using large prime bound of 563454300
using double large prime bound of 5643462481569000


sieving in progress (press Ctrl-C to pause)
found 70529 relations (14124 full + 56405 partial), need 70461
begin with 1558634 relations
reduce to 187642 relations in 14 passes
attempting to read 14124 full and 187642 partial relations
recovered 14124 full and 187642 partial relations
recovered 183703 polynomials
attempting to build 56405 cycles
found 56405 cycles in 7 passes
distribution of cycle lengths:
length 2 : 10864
length 3 : 11030
length 4 : 9806
length 5 : 8016
length 6 : 5923
length 7 : 4059
length 8 : 2690
length 9+: 4017
largest cycle: 22 relations
Sun Dec 12 08:14:57 2004
70333 x 70397 system, weight 5363535 (avg 76.19/col)
reduce to 69900 x 69964 in 3 passes
lanczos halted after 1106 iterations
recovered 61 nontrivial dependencies
Sun Dec 12 08:19:37 2004
probable prime factor: 117313233129506771792305698198589033
probable prime factor: 766845135041866861488895038636348933559984934856636721473
86061859
Sun Dec 12 08:20:52 2004
[/code]

Jason, I found your applet easy to use and really powerful.

Thank you for your effort. If you plan to improve it, I'll be your fan, while if you choose to stop enhancements... I won't complain, and still use msieve for my studies
:wink:

Luigi

[QUOTE=Jeff Gilchrist]Seems like I just caused your 0.87 code to segfault. I tried compiling the code myself in cygwin and also used the precompiled windows .exe you have on your site with the same results.
[/QUOTE]
Msieve can only work on inputs 115 digits or less in size.

That being said, it shouldn't crash either. Will fix.

jasonp

[QUOTE=Joe O]
How about doing for NFS what you have done for QS? i.e. a fast, reliable, easy to use program.
I'm not knocking other implementations, but many of them require the user to know and understand the NFS algorithm, not an easy task![/QUOTE]
I've been teaching myself how NFS works, little by little. I'm not done yet,
and probably never will be, but Crandall/Pomerance and the introductory NFS
papers yield something new on every re-read.

Getting Msieve to where it is now took about eight months. GGNFS has been
underway for ~3 years, and apparently the CWI implementation of NFS has
been under development for a decade. The conventional wisdom is that NFS
is inherently hard to use, because it can go places no other factoring
algorithm can go. Is the hard-to-use part inevitable? I just don't know.
QS is very forgiving of suboptimal parameter choices but NFS is not.

I keep thinking it would be enormously easier to get an existing NFS
implementation to be easier to use than to start another one from scratch.
And while there's no doubt that I would learn a heck of a lot of really arcane
stuff building an NFS program, there's also no doubt that it would be a
massive effort. It's likely that I won't be willing to make such an effort
at this time.

jasonp

[QUOTE=jasonp]it'll definitely cause a new version. What I'm not sure of is whether
it's worth everyone's time to continue hardcore development of the
core code.

According to Paul's 3-large-prime QS paper, the speedup to expect
from going to 3 large primes is a factor of ~1.7 when the input is
large enough. Problem is, 'large enough' may well be past the point
where Msieve will always be slower than using GGNFS.[/QUOTE]That figure of 1.7 was for factoring a 135-digit number and so much larger than anything people use MPQS for these days (or ever, for that matter!) Out there, we estimated, GNFS would be several times faster than 3LP MPQS.

My experiments suggested that TMPQS (as I called it) was cost-effective with PPMPQS at around 95-100 digits and better at around 100-105 digits. The precise crossover point is hard to determine as it depends on parameter choices and each data point takes a long time to produce.
[QUOTE=jasonp] I estimate
that point to be ~103 digits right now, since for numbers that size
Msieve takes ~3 days and GGNFS takes maybe 2-3 days. Adding
3LP support can maybe move the crossover point to 105-106 digits.
And GGNFS is under constant development; it already eats numbers
this small for breakfast.

Is it worth the effort? [/QUOTE]Personally I think not, if your metric is purely one of computational efficiency. 3LP-MPQS is unlikely to be better than GNFS in the range where GNFS is better than 2LP-MPQS. If you have another metric, such as ease of use, then it may well be better.

My advice is to bask in the glory of what you've created, and it is an impressive creation, and move on to something else. I can think of several tools in the NFS chain, for instance, that could be improved greatly over what is presently available.

:bow:

Paul

Hi Jason!

I think you've done a great job so far. As Paul said, there isn't much idea to try and tweak an extra 1% speed performance out of the code for +100 digit numbers, when GGNFS is clearly faster.

However, I think that if you had to put the finger on something that could be improved it would be the parallelization. But then again, a number requirering massive parallel effort wouldn't be done by MPQS anyway. :rolleyes:

Thanks for a greal tool!

-----
Cheers,
Jes

[QUOTE=xilman]
My advice is to bask in the glory of what you've created, and it is an impressive creation, and move on to something else. I can think of several tools in the NFS chain, for instance, that could be improved greatly over what is presently available.

:bow:

Paul[/QUOTE]
Yes, msieve is truly an impressive creation!

How about a wrapper for GGNFS? I don't want to BASH scripts, and I love TACOS (Korn Shells) but having to use a script or do it manually is very offputting. I noticed that there is now a PERL script, but how many Windoze programmers even know that PERL is available for Windoze?

By the way I love PERL, and yes I do run it under Windoze!

Once the wrapper is done, perhaps checking/improving the Lanczos matrix solviing or the sieving would be the next best place to improve the package?

[QUOTE=Joe O]Once the wrapper is done, perhaps checking/improving the Lanczos matrix solviing or the sieving would be the next best place to improve the package?[/QUOTE]

Or, continuing on Paul's suggestion, take a look at the Lanczos code for NFS.

One thing that has bothered me some time now, is that none of the major NFS implementations (GGNFS,CWI and Franke et. al.) have support for running the linear algebra on more then one CPU. I've recently completed a matrix, and that took me 24 days. I'm sure this figure could be brought down a lot if I had been able to use all four CPU's on the computer.

I know NFSNET has a parallel version of the lanczos code from CWI, but is that is heavily licenced, and not availlable to us mere mortals. :rolleyes:

-----
Cheers,
Jes

Dear Jason,

would you like to add an API so your code can be included in other packages? I've compared msieve to the MPQS included in Pari/GP on a c60, yours took 113s while gp took 502s, almost four times as long. Perhaps the Pari group would like to include your code in gp?

Alex