mersenneforum.org Msieve with GNFS support
 Register FAQ Search Today's Posts Mark Forums Read

2006-01-31, 13:04   #1
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts
Msieve with GNFS support

Quote:
 Originally Posted by jasonp I should also mention that there is a new Yahoo! group, nfs-hacks, that has recently started. We hope that people interested in number field sieve implementations will join in. Happy factoring, jasonp
I have joined nfs-hacks. Allow me to repeat what I said there:

I will send my lattice source to anyone who asks by private email
(robert_silverman@raytheon.com) Please acknowledge receipt of same.
I don't expect thanks, but too many times I never get an acknowledgement.

The code is for the Pentium/Athlon. I have a more generic version, but
it needs some porting work to Unix (replacement of timing routines,
replacement of MPP code [I provide generic MPP code]) etc. Any
volunteers?

 2006-08-19, 21:43 #2 XYYXF     Jan 2005 Minsk, Belarus 6208 Posts Nice to see the ball is rolling! :up:
2006-08-21, 03:58   #3
jasonp
Tribal Bullet

Oct 2004

DE316 Posts

Quote:
 Originally Posted by XYYXF Nice to see the ball is rolling! :up:
Indeed. The next version will be out real soon now, and will contain many cleanups and a few small QS and NFS improvements. End-to-end GNFS will be sooo nice when it happens.

In the meantime, Daniel Lerch has put together a package that implements distributed MPQS using the msieve library. dfact 0.1 is available at http://factorizacion.blogspot.com. He tells me that his time is limited right now, but hopefully his current effort will benefit some of the people here.

Apparently software crackers have discovered msieve too. It seems that some programs use RSA keys to verify registration information, but the key sizes don't exceed 256 bits.

jasonp

2006-08-21, 08:09   #4
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

101101100001102 Posts

Quote:
 Originally Posted by jasonp Apparently software crackers have discovered msieve too. It seems that some programs use RSA keys to verify registration information, but the key sizes don't exceed 256 bits.
More fool them.

About 10 years ago PGP allowed public moduli to be as small as 384-bit numbers, though recommendations were made not to use them.

Jim Gillogly, Alec Muffett, Arjen Lenstra and I factored a notorious PGP key's public modulus back in 96 or so. A search with the term "blacknet" and our names will find the story.

The next release enforced a minimum keys size of 512 bits.

Breaking 512-bit keys now is no harder, maybe slightly easier, than 384-bits was a decade ago. Verb. Sap.

Paul

2006-08-24, 06:23   #5
smh

"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts

Quote:
 Originally Posted by jasonp I'll PM the instructions on running the line siever as part of your GGNFS run.
I'm also interested in these instructions. Can you PM them to me too?

2006-08-24, 08:21   #6
Mystwalker

Jul 2004
Potsdam, Germany

3×277 Posts

Quote:
 Originally Posted by smh I'm also interested in these instructions. Can you PM them to me too?
Maybe a special command line switch would be a solution?
That way, unexperienced users still won't be able to try to factor too large composites, but experienced users could easily circumvent the limit when they feel it is sensible.

 2006-08-25, 22:19 #7 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 2×4,079 Posts Just out of curiosity -- have you looked at R.D.Silverman's lattice siever? Any plans on upgrading from a line siever to a lattice siever? P.S. Kudos to you for undertaking this mammoth task - great program!
 2006-10-15, 15:21 #8 Mystwalker     Jul 2004 Potsdam, Germany 3×277 Posts Hi Jason, I've just started Msieve 1.12 to factor 151026*5^110-1 (83 digits), and it took 34 minutes and 34 seconds on a Pentium4 2.4 GHz. I don't exactly recall my previous timings (with versions 0.88 to 1.0x) for composites in that digit range, but I have the impression that is was faster then (and took only a couple of minutes). Can you confirm that my memory is flawed and the time is adequate?
2006-10-16, 03:24   #9
jasonp
Tribal Bullet

Oct 2004

32·5·79 Posts

Quote:
 Originally Posted by Mystwalker Hi Jason, I've just started Msieve 1.12 to factor 151026*5^110-1 (83 digits), and it took 34 minutes and 34 seconds on a Pentium4 2.4 GHz. I don't exactly recall my previous timings (with versions 0.88 to 1.0x) for composites in that digit range, but I have the impression that is was faster then (and took only a couple of minutes). Can you confirm that my memory is flawed and the time is adequate?
On my 1GHz system, this factorization takes 57:30, so your Pentium4 time is in the right neighborhood. You can also use the backup binary from my web page just to make sure, but my rule of thumb is that the fastest I've ever seen an 80-digit factorization take is around 20 minutes.

jasonp

Last fiddled with by jasonp on 2006-10-16 at 03:24 Reason: typo

 2006-11-03, 21:23 #10 trhent   16C616 Posts Here is a basic gui that doesn't offer any frills for msieve. If ya have trouble using cmd-line, might check it out: Code: http://rapidshare.com/files/1862929/Msieve.GUI.1.1.rar.html
 2006-12-24, 05:02 #11 jasonp Tribal Bullet     Oct 2004 67438 Posts Christmas came early this year I just got the NFS square root within msieve to work. The current code computes the algebraic square root by brute force, and once various bugs were resolved it hasn't failed yet. For a 100-digit factorization each dependency takes 8 minutes. This means that all the pieces for GNFS are now written, though the sophistication is mediocre throughout :) I'll try to get v1.13 out in the next week. I'll also try to make the GNFS code kick butt in the next year. Happy holidays to everyone, jasonp

 Similar Threads Thread Thread Starter Forum Replies Last Post EdH EdH 9 2022-01-07 16:31 LegionMammal978 Msieve 6 2017-02-09 04:28 jasonp Msieve 223 2011-03-11 19:30 bsquared YAFU 20 2011-01-21 16:38 fivemack Factoring 3 2007-12-25 08:53

All times are UTC. The time now is 09:59.

Tue Jan 31 09:59:09 UTC 2023 up 166 days, 7:27, 0 users, load averages: 0.97, 0.83, 0.84