mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-06-05, 10:02   #12
wsgtrsys
 
Jan 2009

616 Posts
Default

i have problem .
log is:
Quote:
$ ./factMsieve.pl ros
-> ___________________________________________________________
-> | This is the factMsieve.pl script for GGNFS. |
-> | This program is copyright 2004, Chris Monico, and subject|
-> | to the terms of the GNU General Public License version 2.|
-> |__________________________________________________________|
-> This is client 1 of 1
-> Using 4 threads
-> Working with NAME=ros...
-> Selected default factorization parameters for 140 digit level.
-> Selected lattice siever: .//gnfs-lasieve4I14e
-> No parameter change detected. Resuming.
-> Doing matrix solving step...
=> ".//msieve" -s ros.dat -l ggnfs.log -i ros.ini -v -nf ros.fb -t 4 -nc2

Msieve v. 1.41
Fri Jun 05 06:56:40 2009
random seeds: 57eaf218 9d541200
factoring 1219901374107509269727705827206869949617579394785535062013138456055113
29899985543648271570479476424990192640998571418571175836687323684147561430666970
37831 (155 digits)
searching for 15-digit factors
commencing number field sieve (155-digit input)
R0: -305246705185119988393049615458
R1: 512796205383113353
A0: -1654136390110887053567413679248552485
A1: 6896128775024703671131698569170
A2: 7591355774065335794017922
A3: -23229658654233831899
A4: -8643354678366
A5: 4603320
skew 1045136.28, size 6.029243e-015, alpha -6.933451, combined = 3.225493e-012
commencing linear algebra
read 3803991 cycles
cycles contain 12352322 unique relations
read 12352322 relations
using 20 quadratic characters above 536870820
building initial matrix
memory use: 1495.6 MB
read 3803991 cycles
matrix is 4513569 x 3803991 (1217.6 MB) with weight 397180641 (104.41/col)
sparse part has weight 288748960 (75.91/col)
filtering completed in 1 passes
matrix is 4513569 x 3803991 (1217.6 MB) with weight 397180641 (104.41/col)
sparse part has weight 288748960 (75.91/col)
read 3803991 cycles
matrix is 4513569 x 3803991 (1217.6 MB) with weight 397180641 (104.41/col)
sparse part has weight 288748960 (75.91/col)
matrix must have more columns than rows
Return value 65280. Terminating...
who can help me?
how to do?
wsgtrsys is offline   Reply With Quote
Old 2009-06-05, 11:46   #13
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by wsgtrsys View Post
i have problem .
log is:


who can help me?
how to do?
You don't have enough relations (or you have loads too many). Sieve a bit more and retry.
10metreh is offline   Reply With Quote
Old 2009-06-05, 17:05   #14
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3×1,979 Posts
Default

well done for getting this far
most dont
try sieving a bit more and hopefully it will work
henryzz is offline   Reply With Quote
Old 2009-06-15, 00:32   #15
wsgtrsys
 
Jan 2009

68 Posts
Default

i have new problem:
Quote:
-> This is client 1 of 1
-> Using 4 threads
-> Working with NAME=ros...
-> Selected default factorization parameters for 140 digit level.
-> Selected lattice siever: .//gnfs-lasieve4I14e
-> No parameter change detected. Resuming.
-> Doing matrix solving step...
=> ".//msieve" -s ros.dat -l ggnfs.log -i ros.ini -v -nf ros.fb -t 4 -nc2

Msieve v. 1.41
Mon Jun 15 07:51:54 2009
random seeds: 2940d804 e849c7ec
factoring 12199013741075092697277058272068699496175793947855350620131384560551
298999855436482715704794764249901926409985714185711758366873236841475614306669
37831 (155 digits)
searching for 15-digit factors
commencing number field sieve (155-digit input)
R0: -305246705185119988393049615458
R1: 512796205383113353
A0: -1654136390110887053567413679248552485
A1: 6896128775024703671131698569170
A2: 7591355774065335794017922
A3: -23229658654233831899
A4: -8643354678366
A5: 4603320
skew 1045136.28, size 6.029243e-015, alpha -6.933451, combined = 3.225493e-012
commencing linear algebra
read 4395416 cycles
cycles contain 12003363 unique relations
read 12003363 relations
using 20 quadratic characters above 536870820
building initial matrix
memory use: 1473.1 MB
read 4395416 cycles
matrix is 4395216 x 4395416 (1251.6 MB) with weight 414426005 (94.29/col)
sparse part has weight 292941502 (66.65/col)
filtering completed in 1 passes
matrix is 4395216 x 4395416 (1251.6 MB) with weight 414426005 (94.29/col)
sparse part has weight 292941502 (66.65/col)
read 4395416 cycles
matrix is 4395216 x 4395416 (1251.6 MB) with weight 414426005 (94.29/col)
sparse part has weight 292941502 (66.65/col)
saving the first 48 matrix rows for later
matrix is 4395168 x 4395416 (1199.1 MB) with weight 328830104 (74.81/col)
sparse part has weight 287964967 (65.51/col)
matrix includes 64 packed rows
using block size 65536 for processor cache size 6144 kB
failed to allocate 943920 bytes
Return value 65280. Terminating...
wsgtrsys is offline   Reply With Quote
Old 2009-06-15, 03:13   #16
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,181 Posts
Default

A matrix with 4.4 million columns is going to need 2-2.5GB of memory. If you are running this on a 32-bit OS then I doubt such a large linear algebra job will fit. You need to move the relations to a 64-bit machine (plus possibly rerun the filtering, if you are moving to a big-endian system), then retry the linear algebra.

Last fiddled with by jasonp on 2009-06-15 at 03:18
jasonp is offline   Reply With Quote
Old 2009-06-15, 12:39   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by jasonp View Post
A matrix with 4.4 million columns is going to need 2-2.5GB of memory. If you are running this on a 32-bit OS then I doubt such a large linear algebra job will fit. You need to move the relations to a 64-bit machine (plus possibly rerun the filtering, if you are moving to a big-endian system), then retry the linear algebra.
Huh? I can get such matrices to fit in well under 2Gbytes.
R.D. Silverman is offline   Reply With Quote
Old 2009-06-15, 16:10   #18
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

Well, the only way to get the error reported by the OP is either because his process memory is too fragmented to support a big allocation, or the VM usage of the msieve process exceeds (2GB - epsilon). Originally I thought it had to be the latter, but the log of reported memory use seems to be well short of 2GB, so it could be the former. Not sure what he could do about that though; if in windows, perhaps reboot into /3GB mode so that maybe there would be enough VM for the linear algebra to initialize. Or maybe running in safe mode removes enough globally resident libraries that msieve would work.

I actually don't run many big matrices, so the 2.5GB figure was from memory based on tests made a long time ago.

Last fiddled with by jasonp on 2009-06-15 at 16:11
jasonp is offline   Reply With Quote
Old 2010-07-15, 03:58   #19
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

2×7×13×19 Posts
Default

Found this page, less than 1.5 years ago.

Excerpt includes:
FEBRUARY 2009 A Study on Parallel RSA Factorization ... So far, the Quadratic Sieve (QS) is the fastest and general-purpose method for factoring composite numbers having less than about 110 digits. In this paper ... a variant of the QS ... (MPQS) ... The experimental result shows that it only takes 6.6 days for factoring larger numbers of 100 digits using the enhanced MPQS by 32 workstations. ...

I give up, where's the typo??
RichD is offline   Reply With Quote
Old 2010-07-15, 04:48   #20
axn
 
axn's Avatar
 
Jun 2003

3·11·157 Posts
Default

The full paper can be found here:
http://www.academypublisher.com/ojs/...iew/0402112118
axn is offline   Reply With Quote
Old 2010-07-15, 05:18   #21
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

242210 Posts
Default

This thread (from another forum) shows how a 512-bit RSA signing key was factored by one person: http://unitedti.org/forum/index.php?showtopic=8888 https://cemetech.net/projects/uti/viewtopic.php?t=8888

Last fiddled with by ixfd64 on 2019-05-17 at 22:30 Reason: fixed dead link
ixfd64 is online now   Reply With Quote
Old 2010-07-15, 08:16   #22
debrouxl
 
debrouxl's Avatar
 
Sep 2009

2·3·163 Posts
Default

The OP in in the topic mentioned by ixfd64 estimated that his aging dual-core computer spent 73 days on it. Nowadays, more or less one month with a modern quad-core computer.

Factoring more 512-bit RSA keys very quickly (because we knew that the manufacturer would be very unhappy and would send DMCA threats, no matter how bogus - they did, the news was picked by various sites all over the Web and they got publicly slapped by the EFF) was the starting point of the RSALS BOINC grid - hence the name

Last fiddled with by debrouxl on 2010-07-15 at 08:19
debrouxl is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
newb needs help - factoring RSA512 error barthmaul Msieve 22 2014-12-04 08:25
today ,i factoring rsa512 is ok,only 3 day jackchina Factoring 7 2012-04-13 17:57
NFS Factoring Time Stargate38 Factoring 6 2011-12-08 21:42
LLT, double-checking and factoring at the same time T.Rex Math 12 2006-02-08 20:35
per iteration time for Trial Factoring? MavsFan Software 3 2003-12-12 03:42

All times are UTC. The time now is 19:02.


Wed Dec 1 19:02:13 UTC 2021 up 131 days, 13:31, 1 user, load averages: 1.09, 1.22, 1.25

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.