Msieve with GNFS support

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

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?

XYYXF · 2006-08-19, 21:43

Nice to see the ball is rolling! :up:

jasonp · 2006-08-21, 03:58

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

xilman · 2006-08-21, 08:09

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

smh · 2006-08-24, 06:23

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?

Mystwalker · 2006-08-24, 08:21

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.

Prime95 · 2006-08-25, 22:19

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!

Mystwalker · 2006-10-15, 15:21

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?

jasonp · 2006-10-16, 03:24

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

2006-11-03, 21:23

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

jasonp · 2006-12-24, 05:02

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

2006-11-03, 21:23	#10
trhent 7,103 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 3,541 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
How I Run a Larger Factorization Using Msieve, gnfs and factmsieve.py on Several Ubuntu Machines	EdH	EdH	7	2019-08-21 02:26
Compiling Msieve with GPU support	LegionMammal978	Msieve	6	2017-02-09 04:28
Msieve with GPU support	jasonp	Msieve	223	2011-03-11 19:30
YAFU with GNFS support	bsquared	YAFU	20	2011-01-21 16:38
518-bit GNFS with msieve	fivemack	Factoring	3	2007-12-25 08:53

2006-08-19, 21:43	#2
XYYXF Jan 2005 Minsk, Belarus 2⁴·5² Posts	Nice to see the ball is rolling! :up:

2006-08-25, 22:19	#7
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 7526₁₀ 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 33F₁₆ 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?