Can msieve handle c197's with SNFS?

david314 · 2012-07-23, 17:59

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...

Dubslow · 2012-07-23, 18:25

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?)

david314 · 2012-07-23, 19:26

Quote:

Originally Posted by Dubslow

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 · 2012-07-23, 20:25

Same thing even with 49M relations. Is there perhaps something wrong with the polynomial I'm using?

Batalov · 2012-07-23, 20:49

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`

henryzz · 2012-07-23, 21:49

Should work. SNFS 197 isn't even that hard these days.

david314 · 2012-07-23, 23:00

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 · 2012-07-23, 23:03

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

Batalov · 2012-07-23, 23:15

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.

david314 · 2012-07-24, 00:17

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?

Batalov · 2012-07-24, 01:14

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.

2012-07-23, 23:15	#9
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·47·101 Posts	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

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

2012-07-23, 18:25	#2
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3×29×83 Posts	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?)

2012-07-23, 20:25	#4
david314 Jul 2012 13 Posts	Same thing even with 49M relations. Is there perhaps something wrong with the polynomial I'm using?

2012-07-23, 20:49	#5
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9494₁₀ Posts	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`

2012-07-23, 21:49	#6
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 16FE₁₆ Posts	Should work. SNFS 197 isn't even that hard these days.

2012-07-23, 23:00	#7
david314 Jul 2012 15₈ Posts	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

2012-07-24, 01:14	#11
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9494₁₀ Posts	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.