mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-03-15, 03:19   #1
antiroach
 
antiroach's Avatar
 
Jun 2003

22×61 Posts
Default SNFS Program?

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 ?
antiroach is offline   Reply With Quote
Old 2004-03-15, 08:04   #2
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

4A516 Posts
Default

NFSX for Ubasic is the only one i know of.
It can be found at ftp://rkmath.rikkyo.ac.jp./pub/ubtest/
smh is offline   Reply With Quote
Old 2004-03-30, 18:43   #3
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

118910 Posts
Default

Quote:
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?
smh is offline   Reply With Quote
Old 2004-03-30, 19:23   #4
antiroach
 
antiroach's Avatar
 
Jun 2003

22·61 Posts
Default

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.
antiroach is offline   Reply With Quote
Old 2004-03-30, 21:44   #5
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

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.

Last fiddled with by Wacky on 2004-03-30 at 21:45
Wacky is offline   Reply With Quote
Old 2004-03-31, 01:22   #6
aaronl
 
aaronl's Avatar
 
Aug 2003

4810 Posts
Default

What about relatively small numbers? How difficult is it to factor a 384 bit number with GNFS?
aaronl is offline   Reply With Quote
Old 2004-03-31, 09:07   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3·3,529 Posts
Default

Quote:
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
xilman is online now   Reply With Quote
Old 2004-03-31, 11:29   #8
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

Quote:
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.

Quote:
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.

Quote:
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!

Last fiddled with by smh on 2004-03-31 at 11:31
smh is offline   Reply With Quote
Old 2004-03-31, 13:51   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

295B16 Posts
Default

Quote:
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
xilman is online now   Reply With Quote
Old 2004-03-31, 20:26   #10
aaronl
 
aaronl's Avatar
 
Aug 2003

24·3 Posts
Default

Quote:
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.
aaronl is offline   Reply With Quote
Old 2004-04-23, 07:48   #11
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

22×29 Posts
Default

Quote:
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?
JHansen is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SNFS Polynomial for 919^87-1 wblipp Factoring 6 2011-08-23 04:59
SNFS 200 parameters JoeCrump Factoring 3 2009-12-06 14:50
fun with snfs masser Sierpinski/Riesel Base 5 36 2008-04-18 02:39
SNFS Sample(10^4+1) nuggetprime Factoring 1 2007-06-11 16:31
Offline SNFS R.D. Silverman NFSNET Discussion 18 2004-12-31 11:45

All times are UTC. The time now is 11:20.

Mon Mar 1 11:20:20 UTC 2021 up 88 days, 7:31, 0 users, load averages: 1.24, 1.29, 1.29

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.