>a factor of 115^19+19^115.

This number could be done with SNFS as well.

Multiply by 115: 115^20+115*19^115
= a^5 + 115*b^5 with a=115^4 and b=19^23

a^5 + 115*b^5 = ((a/b)^5 - 115)*b^5

hence 115^4/19^23 is a root modulo N of the polynomial f(x)=x^5+115.

The polynomial on the rational side is g(x) = 19^23*x - 115^4. Difficulty is 147.

I get an estimated sieving time of about 5 days, plus maybe another day for the matrix.

For numbers of the form x^y+y^x it is often possible to make SNFS polynomials, but not always as easy as in this case.

Alex

PS.: This is a bit too late to be useful for you now. :sad: Sorry, I hadn't noticed before.

I knew about SNFS as well as that GNFS would be even faster :)

But I wanted to test MSieve on a C114.

BTW, with the multiplier of 17 this C114 happens to be of 116-digit difficulty :)

Well, Tom Cage factored a C117 cofactor of 146^72+72^146

1572551858200900899424396151766085993988852438466994070366\
25465464300774264743109319202802467874697255148867036904393

as

Tue Jun 28 04:08:54 2005 prp50 factor:
13526587294381062629138137672122897672944433227141
Tue Jun 28 04:08:54 2005 prp68 factor:
11625636414989449175748590878470408534672440694138510759034560749173

with MSieve 1.0, so I'm stopping my task until the C114 is factored by someone else :)

Msieve 1.01 released
 

Version 1.01 is now available. Highlights include:

- Completely revamped computation of the factor base and multiplier.
The code to do this was pretty old and inefficient; the new version
is better documented and picks a better multiplier quite often.

- Fixed a bug initializing polynomials for very small factorizations

It's not safe to resume your current factorization with v1.01, because the multiplier is not allowed to change in the middle of a factorization.

Happy factoring,
jasonp

A C113 is factored well with Msieve 1.01 in 9 days:
[url]http://groups.yahoo.com/group/xyyxf/message/632[/url]

msieve 1.02 beta
 

I just realized that it's been months since the last release, and I've been sitting on a few new features, so I'm making a beta of msieve 1.02 available:

[url]www.boo.net/~jasonp/msieve102b.tar.gz[/url]
[url]www.boo.net/~jasonp/msieve102b.exe[/url]

Highlights include:

Much more tuning of sieve parameters, especially for very big factorizations. I don't have actual timing data yet, but some tiny experiments have shown that the previous set of parameters was quite suboptimal. I haven't tried factorizations beyond C110 size, so it's possible the new parameters could require hundreds of megabytes of memory

Multiple optimizations that reduce memory use for big factorizations, especially needed since the new parameters can potentially increase memory requirements

New features that allow sieving to stop early (requested by several people). Be sure to check for new command line options

Even more tweaking with multipliers. Once again, this unfortunately means that it's not safe to substitute the beta into a currently running factorization, *unless* you are sure that the multiplier (printed out in the log file) is the same as before.

I want to at least finish my benchmark C105 before considering a full release.

Happy factoring,
jasonp

Does the current version contain support for the 3 large primes?

Could parallel sieving be automated somewhat? Maybe have each siever collect a few relations, lock the msieve.dat file, seek to the end of it, write the relations and unlock. When there are enough relations, the first siever that notices (unless inhibited by a command line switch) writes a flag to the end of msieve.dat to make other sievers terminate and enters post-processing. Does this sound feasible?

Alex

axn1: triple large primes are still a big deal to implement. Building an NFS siever and actually looking at other people's code to factor small integers has convinced me that it's possible to do much better than the tiny MPQS implementation that I used in my first experiments. In practice, everything depends on how fast this code can be made. If I ever do implement triple large primes, it will be in the next release, now that all the other little stuff is out of the way.

Alex: I have docs on locking files for win32 systems, is there a posix-compatible way to do the same thing?

jasonp

[QUOTE=axn1]Does the current version contain support for the 3 large primes?[/QUOTE]

I see no point in implementing such a thing. By the time the composites
become large enough for 3 large primes to be effective, NFS becomes quite
a bit faster.

My advice to the author: DON'T.

[QUOTE=akruppa]Could parallel sieving be automated somewhat? Maybe have each siever collect a few relations, lock the msieve.dat file, seek to the end of it, write the relations and unlock. When there are enough relations, the first siever that notices (unless inhibited by a command line switch) writes a flag to the end of msieve.dat to make other sievers terminate and enters post-processing. Does this sound feasible?

Alex[/QUOTE]
A much cleaner way is to have each siever write their own file and to designate one siever as the master (this choice should be made at the outset). Every time the client has something to say, it opens its output file in append mode (creating it first if necessary), writes the data, and closes it (thereby flushing the file buffer).

Every so often, the master renames the clients' files and then processes them under the new name.

There is still a race condition, but the amount of data lost or corrupted will be very small in practice, and data corruption needs to be detected anyway. You can mess around with file locking if you wish, but it really isn't necessary and virtually impossible to implement in a portable manner.

By an amazing coincidence, this is how Arjen Lenstra's qs.c program works. By an even more bizarre coincidence, I was the person who taught Arjen how perform some of the filesystem manipulations required.


Paul