SNFS Program?

[antiroach]

Is there an executable program or applet that can do factoring using the SNFS method without me having to learn a lot of the background information required to get it to work ?

[smh]

NFSX for Ubasic is the only one i know of.
It can be found at ftp://rkmath.rikkyo.ac.jp./pub/ubtest/

[smh]

Originally Posted by antiroach

Is there an executable program or applet that can do factoring using the SNFS method without me having to learn a lot of the background information required to get it to work ?

Did you manage to get it work?

[antiroach]

nope. i gave up after reading the instructions for how to run the program. also there are so many zip files, i dont know which ones to use or whatnot. I havent even gotten ubasic 'installed'. maybe you could provide a quick step by step procedure on how to get it working? thanks.

[Wacky]

I really question why you want to do this. Any sieving program written in UBasic is probably very slow. The production grade sievers have all had many years spent tweeking, use custom assembly code, etc.

If you are trying to understand the algorithm, you could very well look at the CODE for a simplified siever in order to better understand what is happening, but you wouldn't learn much just trying to run it.

Additionally, just running the siever is only a part of solving a factorization. There are not very many people who have access to enough computing power to solve anything of interest. If you don't have at least tens, and preferably hundreds, of reasonably fast computers and access to a very large machine/cluster for the LA, the biggest problem that you could solve is so small that ECM is much more efficient.

[aaronl]

What about relatively small numbers? How difficult is it to factor a 384 bit number with GNFS?

[xilman]

Originally Posted by Wacky

I really question why you want to do this. Any sieving program written in UBasic is probably very slow. The production grade sievers have all had many years spent tweeking, use custom assembly code, etc.

If you are trying to understand the algorithm, you could very well look at the CODE for a simplified siever in order to better understand what is happening, but you wouldn't learn much just trying to run it.

Additionally, just running the siever is only a part of solving a factorization. There are not very many people who have access to enough computing power to solve anything of interest. If you don't have at least tens, and preferably hundreds, of reasonably fast computers and access to a very large machine/cluster for the LA, the biggest problem that you could solve is so small that ECM is much more efficient.

Actually, this implementation of SNFS isn't so bad. Large chunks of it are wrotten in assembler and the package is entirely useable for factorizations with SNFS-difficulty up to 110 or 120 digits. I've used it myself to factor several generalized Cullen & Woodall numbers where its extreme ease of use more than made up for its relative slowness compared with, say, the CWI suite.

The main limitations, as I understand them, are that the sieving effort can not be split over several machines (at least, I never found out how to do so) and it's limited to odd-degree poynomials by the choice of the Couveignes square root. Occasionally, it would choose bad sieving parameters which had either to be tweaked by hand (not easy if you don't know what you're doing) or let the program run for a ridiculously long time.

Finally, I dispute that ECM is invariably better than SNFS for numbers so small. A C100 which happens to be the product of a P48 and a P52 will be *much* harder to factor with ECM than with SNFS, assuming the SNFS difficulty isn't too much greater than 100 digits.

On the other hand, you should definitely run ECM for a while before turning to SNFS.

Paul

[smh]

Originally Posted by Wacky

I really question why you want to do this. Any sieving program written in UBasic is probably very slow. The production grade sievers have all had many years spent tweeking, use custom assembly code, etc.

Because it's the only SNFS program i know of that is freely available.

Although other implementations might be significantely faster and do not have limitations NFSX has, it's a much better alternative to ppsiqs for some type of numbers.

Originally Posted by Wacky

If you are trying to understand the algorithm, you could very well look at the CODE for a simplified siever in order to better understand what is happening, but you wouldn't learn much just trying to run it.

I'm not trying to understand the algorithm at all. Just like i don't understand how ecm or the nfsnet client works.

Originally Posted by Wacky

Additionally, just running the siever is only a part of solving a factorization. There are not very many people who have access to enough computing power to solve anything of interest. If you don't have at least tens, and preferably hundreds, of reasonably fast computers and access to a very large machine/cluster for the LA, the biggest problem that you could solve is so small that ECM is much more efficient.

Recentely i factored 11*2^423+1 in a P64 and P65, which would be very hard to do by ecm.

7*2^456+1 took about 49 hours on my P4 and the largest i've done is 5*2^475-1 (c143) in less then 14 days on a P3 800!!

And i know of even larger factorizations done with this program, all on a single pc!

[xilman]

Originally Posted by aaronl

What about relatively small numbers? How difficult is it to factor a 384 bit number with GNFS?

Easy, if you have a good implementation of GNFS. Extremely hard if you have to write your implementation first.

Paul

[aaronl]

Originally Posted by xilman

Easy, if you have a good implementation of GNFS. Extremely hard if you have to write your implementation first.

Paul

That seems like the hard part. I've been looking at the GNFS implementation at ftp://ftp.math.uni-bonn.de/people/franke/mpqs4linux/. It doesn't seem great but it could probably suffice for small factorizations. CWI's NFS code isn't generally available AFAICT, which is a pity since I can't see how they could profit from it.

[JHansen]

Originally Posted by aaronl

NFS code isn't generally available AFAICT, which is a pity since I can't see how they could profit from it.

Well, that depends. I got my CWI NFS suite relatively easy. All I did as a private person, was to write to Herman te Riele at CWI, that I would like to try the NFS suite, and he sent me a licence. After that had been printed, signed and sent back to him he mailed me the source code, and the binaries too. Now, wasn't that nice of him?