mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2012-07-23, 17:59   #1
david314
 
Jul 2012

13 Posts
Default Can msieve handle c197's with SNFS?

Hi,

trying to run factmsieve with the c197: 3^412 - 2 = 37493582965828985969957724950586364036097201250169303876336045733
55345200761878611110665898978791442414402602377192197115847303615
98835195485031578276026715301962419927445046033052509383510613394
39. Using SNFS with the polynomial:

Code:
n: 37493582965828985969957724950586364036097201250169303876336045733553452007618786111106658989787914424144026023771921971158473036159883519548503157827602671530196241992744504603305250938351061339439
m: 3990838394187339929534246675572349035227
deg: 5
skew: 2.0
type: snfs
c5: 1
c0: -54
I've got about 2.5G of relations saved, and when msieve gets to the first stage of linear algebra it blows up:

Code:
*** buffer overflow detected ***: ./msieve terminated
======= Backtrace: =========
[0x4e1575]
[0x4e113e]
[0x4e0959]
[0x4c22bc]
[0x4b392b]
[0x4e09f6]
[0x4e093d]
[0x40a036]
[0x413881]
[0x40299a]
[0x400a8f]
[0x40140d]
[0x4a591e]
[0x400369]
======= Memory map: ========
00400000-00584000 r-xp 00000000 00:1b 29304262    msieve
00783000-00786000 rw-p 00183000 00:1b 29304262    msieve
00786000-0078d000 rw-p 00000000 00:00 0 
01376000-01399000 rw-p 00000000 00:00 0                                  [heap]
7fe5e75d2000-7fe5e75d3000 rw-p 00000000 00:00 0 
7fff9fab8000-7fff9fada000 rw-p 00000000 00:00 0                          [stack]
7fff9fb37000-7fff9fb38000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
I'm running msieve 1.5.0 compiled for x86_64, and I've tried both with and without GMP-ECM compiled in.

Anyone know what's going on? is it expected that msieve can't handle composites this big, or is there a bug?

thanks...
david314 is offline   Reply With Quote
Old 2012-07-23, 18:25   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Well it's supposed to be able to do it, considering it's doing M1061, a 320-digit SNFS job. Probably a bug. (Perhaps try more sieving, make an easier matrix?)
Dubslow is offline   Reply With Quote
Old 2012-07-23, 19:26   #3
david314
 
Jul 2012

158 Posts
Default

Quote:
Originally Posted by Dubslow View Post
Well it's supposed to be able to do it, considering it's doing M1061, a 320-digit SNFS job. Probably a bug. (Perhaps try more sieving, make an easier matrix?)
Same thing, even with 49071832 relations...

Code:
*** buffer overflow detected ***: ./msieve terminated
======= Backtrace: =========
[0x51ecb5]
[0x51e87e]
[0x51e099]
[0x4ff9dc]
[0x4f0dcb]
[0x51e136]
[0x51e07d]
[0x40a036]
[0x413881]
[0x40299a]
[0x400a8f]
[0x40140d]
[0x4e2dbe]
[0x400369]
Anything wrong with my polynomial? it looks reasonable enough...

Code:
n: 37493582965828985969957724950586364036097201250169303876336045733553452007618786111106658989787914424144026023771921971158473036159883519548503157827602671530196241992744504603305250938351061339439
m: 3990838394187339929534246675572349035227
deg: 5
skew: 2.0
type: snfs
c5: 1
c0: -54
if we let n = 3^412 - 2, then 3^3*n = 3^415 - 54, so f(x) = x^5 - 54, and m = 3^83 = 3990838394187339929534246675572349035227...
david314 is offline   Reply With Quote
Old 2012-07-23, 20:25   #4
david314
 
Jul 2012

13 Posts
Default

Same thing even with 49M relations. Is there perhaps something wrong with the polynomial I'm using?
david314 is offline   Reply With Quote
Old 2012-07-23, 20:49   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59×163 Posts
Default

The poly looks fine. Try ldd on your binary, check if there's anything weird with its library linking. What is the linux flavor?
uname -a
cat /proc/cpuinfo
ldd `where msieve`
Batalov is offline   Reply With Quote
Old 2012-07-23, 21:49   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·2,969 Posts
Default

Should work. SNFS 197 isn't even that hard these days.
henryzz is online now   Reply With Quote
Old 2012-07-23, 23:00   #7
david314
 
Jul 2012

13 Posts
Default

FYI, this happens even with version Msieve v. 1.51 (SVN 722), which I just compiled from SVN at head.

I'm building a statically linked binary because I'm using it on a few machines:

Code:
$ file ./msieve
./msieve: ELF 64-bit LSB executable, x86-64, version 1 (GNU/Linux), statically linked, for GNU/Linux 2.6.15, not stripped

$ ldd ./msieve
	not a dynamic executable
and I've used it to perform several other SNFS factorizations; it's just choking on this c197. System info for one of the machines:

Code:
Linux xena 2.6.18-194.26.1.el5 #1 SMP Wed Nov 17 14:40:07 PST 2010 x86_64 x86_64 x86_64 GNU/Linux
david314 is offline   Reply With Quote
Old 2012-07-23, 23:03   #8
david314
 
Jul 2012

1310 Posts
Default

BTW, here are the first few relations in input.dat; I don't know if factmsieve is doing something funky.

Code:
N 37493582965828985969957724950586364036097201250169303876336045733553452007618786111106658989787914424144026023771921971158473036159883519548503157827602671530196241992744504603305250938351061339439
-1059784,729471:988f9b7,9c33b63,132E6F,8D7669,C70A69,17C9,102B:7ADA49,B99,F7F499
15867698,34712695:5d0f9a9,2383,13F55,2678B,60AE1,151F,1AF3,63D,C25:107a3cd,68ED,9985,33881,63F76F,CF7,F7F499
-308900,13195591:9f12881,f8c04d,42445,1418A7,43DD8B,C85DE9,515:1aa36e5,298F,7957,11FB,143B,F7F499
-4348620,3532793:9469c5b,17b0541,4819,15898F,2DFAED,5187B5,DD3:cd9b3b9,168EF,213005,F7F499
4749573,12683483:f4cb3b,1c0cb11,2185,2AA27,250EEB,DB70ED,1619:9b47069,29f5cd3,2A6CD,66E15,F7F499
25720451,72665733:1b227e1,903a4b1,36AF,5F35,5DEA1,F1B13,36AE29,1C45:f7d465b,62fe8c7,18F55,5355B,F7F499
12599177,49057179:300f1d5,9407fb7,DB6B,E6E3,97C625:135da27,25109,3FD0F7,413191,E7D,120D,F7F499
17970871,66222403:3023,DCCF,1092B,DC73B,23F303,67B211,6D5CAF:4d84b01,13554d3,223A5,2A547D,F7F499
14759095,62858429:1dec975,18FFD,E3E39,168F0D,16F7A7,25AA73,153D:f60e3bf,3161,22163,3E7E9,509,C6D,1AA7,F7F499
david314 is offline   Reply With Quote
Old 2012-07-23, 23:15   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59×163 Posts
Default

Relations are looking fine. You may want to rebuild msieve on the exact machine you are using this time. Some machines will be incompatible to the static binary from others. A project of this size shouldn't give msieve any trouble at all.

While it is adivisable to link zlib and libecm and possibly libgmp statically, you don't want to statically link libc, libm etc.

Last fiddled with by Batalov on 2012-07-23 at 23:18
Batalov is offline   Reply With Quote
Old 2012-07-24, 00:17   #10
david314
 
Jul 2012

13 Posts
Default

Still no luck on this c197 with a dynamically linked msieve binary. But I did get a somewhat more descriptive stack trace...

Code:
*** buffer overflow detected ***: ./msieve terminated
======= Backtrace: =========
/lib/libc.so.6(__fortify_fail+0x37)[0x7ff2b6d7e7e7]
/lib/libc.so.6(+0xfe6a0)[0x7ff2b6d7d6a0]
/lib/libc.so.6(+0xfdb09)[0x7ff2b6d7cb09]
/lib/libc.so.6(_IO_default_xsputn+0xcc)[0x7ff2b6cf4f6c]
/lib/libc.so.6(_IO_vfprintf+0x395e)[0x7ff2b6cc7cfe]
/lib/libc.so.6(__vsprintf_chk+0x99)[0x7ff2b6d7cba9]
/lib/libc.so.6(__sprintf_chk+0x7f)[0x7ff2b6d7caef]
./msieve[0x439565]
./msieve[0x4233f3]
./msieve[0x41639e]
./msieve[0x40588a]
./msieve[0x40397f]
./msieve[0x4042fd]
/lib/libc.so.6(__libc_start_main+0xfd)[0x7ff2b6c9dc4d]
./msieve[0x403289]
======= Memory map: ========
00400000-0046c000 r-xp 00000000 00:1b 12692227                           ./msieve
0066b000-0066c000 r--p 0006b000 00:1b 12692227                           ./msieve
0066c000-0066d000 rw-p 0006c000 00:1b 12692227                           ./msieve
006c0000-0223b000 rw-p 00000000 00:00 0                                  [heap]
7ff2b6a68000-7ff2b6a7e000 r-xp 00000000 fc:00 800807                     /lib/libgcc_s.so.1
7ff2b6a7e000-7ff2b6c7d000 ---p 00016000 fc:00 800807                     /lib/libgcc_s.so.1
7ff2b6c7d000-7ff2b6c7e000 r--p 00015000 fc:00 800807                     /lib/libgcc_s.so.1
7ff2b6c7e000-7ff2b6c7f000 rw-p 00016000 fc:00 800807                     /lib/libgcc_s.so.1
7ff2b6c7f000-7ff2b6df9000 r-xp 00000000 fc:00 801237                     /lib/libc-2.11.1.so
7ff2b6df9000-7ff2b6ff8000 ---p 0017a000 fc:00 801237                     /lib/libc-2.11.1.so
7ff2b6ff8000-7ff2b6ffc000 r--p 00179000 fc:00 801237                     /lib/libc-2.11.1.so
7ff2b6ffc000-7ff2b6ffd000 rw-p 0017d000 fc:00 801237                     /lib/libc-2.11.1.so
7ff2b6ffd000-7ff2b7002000 rw-p 00000000 00:00 0 
7ff2b7002000-7ff2b701a000 r-xp 00000000 fc:00 801235                     /lib/libpthread-2.11.1.so
7ff2b701a000-7ff2b7219000 ---p 00018000 fc:00 801235                     /lib/libpthread-2.11.1.so
7ff2b7219000-7ff2b721a000 r--p 00017000 fc:00 801235                     /lib/libpthread-2.11.1.so
7ff2b721a000-7ff2b721b000 rw-p 00018000 fc:00 801235                     /lib/libpthread-2.11.1.so
7ff2b721b000-7ff2b721f000 rw-p 00000000 00:00 0 
7ff2b721f000-7ff2b72a1000 r-xp 00000000 fc:00 789061                     /lib/libm-2.11.1.so
7ff2b72a1000-7ff2b74a0000 ---p 00082000 fc:00 789061                     /lib/libm-2.11.1.so
7ff2b74a0000-7ff2b74a1000 r--p 00081000 fc:00 789061                     /lib/libm-2.11.1.so
7ff2b74a1000-7ff2b74a2000 rw-p 00082000 fc:00 789061                     /lib/libm-2.11.1.so
7ff2b74a2000-7ff2b7501000 r-xp 00000000 fc:00 2230619                    /usr/lib/libgmp.so.3.5.2
7ff2b7501000-7ff2b7700000 ---p 0005f000 fc:00 2230619                    /usr/lib/libgmp.so.3.5.2
7ff2b7700000-7ff2b7701000 r--p 0005e000 fc:00 2230619                    /usr/lib/libgmp.so.3.5.2
7ff2b7701000-7ff2b7702000 rw-p 0005f000 fc:00 2230619                    /usr/lib/libgmp.so.3.5.2
7ff2b7702000-7ff2b7748000 r-xp 00000000 fc:00 2264704                    /usr/lib/libecm.so.0.0.0
7ff2b7748000-7ff2b7947000 ---p 00046000 fc:00 2264704                    /usr/lib/libecm.so.0.0.0
7ff2b7947000-7ff2b7948000 r--p 00045000 fc:00 2264704                    /usr/lib/libecm.so.0.0.0
7ff2b7948000-7ff2b7951000 rw-p 00046000 fc:00 2264704                    /usr/lib/libecm.so.0.0.0
7ff2b7951000-7ff2b7971000 r-xp 00000000 fc:00 801222                     /lib/ld-2.11.1.so
7ff2b7b4a000-7ff2b7b4e000 rw-p 00000000 00:00 0 
7ff2b7b6a000-7ff2b7b6b000 rw-p 00000000 00:00 0 
7ff2b7b6d000-7ff2b7b70000 rw-p 00000000 00:00 0 
7ff2b7b70000-7ff2b7b71000 r--p 0001f000 fc:00 801222                     /lib/ld-2.11.1.so
7ff2b7b71000-7ff2b7b72000 rw-p 00020000 fc:00 801222                     /lib/ld-2.11.1.so
7ff2b7b72000-7ff2b7b73000 rw-p 00000000 00:00 0 
7fff70140000-7fff70162000 rw-p 00000000 00:00 0                          [stack]
7fff701ed000-7fff701ee000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Seems like it's dying somewhere inside libc routines?
david314 is offline   Reply With Quote
Old 2012-07-24, 01:14   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59×163 Posts
Default

Well, you may need to build gmp (and so on for the needed libs) on the same machine as well. (You can skip ECM=1 for debugging)
It all looks like the lib incompatibilities. Rest assured that msieve had been run by hundreds of people and it runs fine.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where can I find a arbitrary precision Calculator online that can handle this # ONeil Information & Answers 9 2018-04-17 18:18
How to handle ECM results? dbaugh PrimeNet 6 2012-11-09 19:27
Tweaking polynomial search for C197 fivemack Msieve 38 2011-07-08 08:12
222-digit SNFS completed with msieve frmky Factoring 2 2007-10-01 18:23
New PC can handle two instances of Prime 95 Bundu Software 9 2004-08-21 02:29

All times are UTC. The time now is 16:47.


Fri Dec 3 16:47:05 UTC 2021 up 133 days, 11:16, 2 users, load averages: 0.76, 1.03, 1.06

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.