mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2006-01-31, 13:04   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts
Default 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?
R.D. Silverman is offline   Reply With Quote
Old 2006-08-19, 21:43   #2
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

6208 Posts
Default

Nice to see the ball is rolling! :up:
XYYXF is offline   Reply With Quote
Old 2006-08-21, 03:58   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DE316 Posts
Default

Quote:
Originally Posted by XYYXF View Post
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
jasonp is offline   Reply With Quote
Old 2006-08-21, 08:09   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

101101100001102 Posts
Default

Quote:
Originally Posted by jasonp View Post
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
xilman is offline   Reply With Quote
Old 2006-08-24, 06:23   #5
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

Quote:
Originally Posted by jasonp View Post
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?
smh is offline   Reply With Quote
Old 2006-08-24, 08:21   #6
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Default

Quote:
Originally Posted by smh View Post
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.
Mystwalker is offline   Reply With Quote
Old 2006-08-25, 22:19   #7
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2×4,079 Posts
Default

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!
Prime95 is offline   Reply With Quote
Old 2006-10-15, 15:21   #8
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Default

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?
Mystwalker is offline   Reply With Quote
Old 2006-10-16, 03:24   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32·5·79 Posts
Default

Quote:
Originally Posted by Mystwalker View Post
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
jasonp is offline   Reply With Quote
Old 2006-11-03, 21:23   #10
trhent
 

16C616 Posts
Default

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
  Reply With Quote
Old 2006-12-24, 05:02   #11
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67438 Posts
Default 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
jasonp is offline   Reply With Quote
Reply

Thread Tools


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 9 2022-01-07 16:31
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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”