squre root step problem

[loong]

Dear all,
I use factmsieve.py to factoring a big N, and it runs very well till the squre root step.
The output is as following:

xxx@xxx64:/data/corefile/xxx/factortool/test2> /usr/local/bin/python3 factmsieve2.py test2.n
-> ________________________________________________________________
-> | Running factmsieve.py, a Python driver for MSIEVE with GGNFS |
-> | sieving support. It is Copyright, 2010, Brian Gladman and is |
-> | a conversion of factmsieve.pl that is Copyright, 2004, Chris |
-> | Monico.    Version 0.76 (Python 2.6 or later) 10th Nov 2010. |
-> |______________________________________________________________|
test2
-> This is client 1 of 1
-> Running on 4 Cores with 1 hyper-thread per Core
-> Working with NAME = test2
-> Selected default factorization parameters for 163 digit level.
-> Selected lattice siever: gnfs-lasieve4I15e
-> No parameter change detected, resuming...
-> Running lattice siever ...
-> entering sieving loop
-> File 'deps' already exists. Proceeding to sqrt step.
-> Running square root step ...
/data/corefile/xxx/factortool
./msieve
-> ./msieve -s test2/test2.dat -l test2/test2.log -i test2/test2.ini -nf test2/test2.fb -t 4 -nc3
-> Computing 1.30423e+09 scale for this machine...
-> procrels -speedtest> PIPE
 __________________________________________________________
|        This is the procrels program for GGNFS.           |
| Version: 0.77.1-20060722-nocona                          |
| This program is copyright 2004, Chris Monico, and subject|
| to the terms of the GNU General Public License version 2.|
|__________________________________________________________|
b[a%1024] = 00000000
timeunit: 2.063
Traceback (most recent call last):
  File "factmsieve2.py", line 2124, in <module>
    output_summary(NAME, fact_p, pols_p, poly_p, lats_p)
  File "factmsieve2.py", line 1807, in output_summary
    tmp = grep_l('timeunit:', res)
  File "factmsieve2.py", line 190, in grep_l
    for l in lines:
TypeError: 'NoneType' object is not iterable

and test2.log shows:

...
Sun May 1 14:15:58 2011 commencing square root phase
Sun May 1 14:15:58 2011 reading relations for dependency 1
Sun May 1 14:16:01 2011 read 2845889 cycles
Sun May 1 14:16:08 2011 cycles contain 7925904 unique relations
Sun May 1 14:25:03 2011 read 7925904 relations
Sun May 1 14:26:03 2011 multiplying 7925904 relations
Sun May 01 14:35:20 2011 -> Computing 1.30423e+09 scale for this machine...
Sun May 01 14:35:20 2011 -> procrels -speedtest> PIPE


Is there any error with my whole step?

[jasonp]

It looks like you got a reasonable dependency that crashed when you tried to use it. This would sometimes happen if you compiled Msieve or GMP with gcc 4.1.x, for reasons I've never been able to understand. gcc 4.2.x is reported to be safe. The other possibility is that you ran out of memory. If you're running on a 32-bit widows system that could be the problem, give that size of dataset.

[WraithX]

Originally Posted by loong

-> Running square root step ...
/data/corefile/xxx/factortool
./msieve
-> ./msieve -s test2/test2.dat -l test2/test2.log -i test2/test2.ini -nf test2/test2.fb -t 4 -nc3
-> Computing 1.30423e+09 scale for this machine...
-> procrels -speedtest> PIPE
 __________________________________________________________
|        This is the procrels program for GGNFS.           |
| Version: 0.77.1-20060722-nocona                          |
| This program is copyright 2004, Chris Monico, and subject|
| to the terms of the GNU General Public License version 2.|
|__________________________________________________________|
b[a%1024] = 00000000
timeunit: 2.063
Traceback (most recent call last):
  File "factmsieve2.py", line 2124, in <module>
    output_summary(NAME, fact_p, pols_p, poly_p, lats_p)
  File "factmsieve2.py", line 1807, in output_summary
    tmp = grep_l('timeunit:', res)
  File "factmsieve2.py", line 190, in grep_l
    for l in lines:
TypeError: 'NoneType' object is not iterable

Also, this error was thrown by Python itself, and is not an error returned by one of the sub-programs called by the python script. This error seems to be due to the fact that the output from "procrels -speedtest> PIPE" was printed to stdout and not captured by factmsieve.py for later grep-ing. Since it wasn't saved internally, there was no info to grep, hence the error. It was looking for the line "timeunit: 2.063" that was printed to stdout.

One way to see if this will complete successfully for you is to modify the script like so:

Find the following two lines (the first is at line 1807 of your factmsieve2.py):

  tmp = grep_l('timeunit:', res)
  timescale = float(re.sub('timeunit:\s*', '', tmp[0]))

And change them to:

  # tmp = grep_l('timeunit:', res)
  # timescale = float(re.sub('timeunit:\s*', '', tmp[0]))
  timescale = 2.063

This might be a problem with the version of Python that you are running. Could you run '/usr/local/bin/python3 -V' from the command line and let us know which version of python you are running. And also, which operating system are you on?

[loong]

Originally Posted by jasonp

It looks like you got a reasonable dependency that crashed when you tried to use it. This would sometimes happen if you compiled Msieve or GMP with gcc 4.1.x, for reasons I've never been able to understand. gcc 4.2.x is reported to be safe. The other possibility is that you ran out of memory. If you're running on a 32-bit widows system that could be the problem, give that size of dataset.

Thanks for your reply jasonp.
I've executed msieve with the following command alone:
./msieve -v -s test2/test2.dat -l test2/test2.log -i test2/test2.ini -nf test2/test2.fb -t 4 -nc3

and get the output:

commencing square root phase
reading relations for dependency 1
read 2845889 cycles
cycles contain 7925904 unique relations
read 7925904 relations
multiplying 7925904 relations
Segmentation fault

Note the "Segmentation fault".
I've checked the gcc version, and it is exactly 4.1.x :
gcc version 4.1.2 20070115 (prerelease) (SUSE Linux)

and I compiled msieve under linux x86_64, the memory is 8GB, so it might not the problem of that run out of memory.

I'll update gcc to 4.2.x to see if it will happen again.

Thanks again.

[loong]

Originally Posted by WraithX

Also, this error was thrown by Python itself, and is not an error returned by one of the sub-programs called by the python script. This error seems to be due to the fact that the output from "procrels -speedtest> PIPE" was printed to stdout and not captured by factmsieve.py for later grep-ing. Since it wasn't saved internally, there was no info to grep, hence the error. It was looking for the line "timeunit: 2.063" that was printed to stdout.

One way to see if this will complete successfully for you is to modify the script like so:

Find the following two lines (the first is at line 1807 of your factmsieve2.py):

  tmp = grep_l('timeunit:', res)
  timescale = float(re.sub('timeunit:\s*', '', tmp[0]))

And change them to:

  # tmp = grep_l('timeunit:', res)
  # timescale = float(re.sub('timeunit:\s*', '', tmp[0]))
  timescale = 2.063

This might be a problem with the version of Python that you are running. Could you run '/usr/local/bin/python3 -V' from the command line and let us know which version of python you are running. And also, which operating system are you on?

WraithX, thanks for your help.
I'm running python 3.2, and the operating system is SuSe Linux SP2 x86_64.

Thanks for your help again.

[loong]

I've updated gcc to 4.6.0, and have compiled msieve again, but the problem still exists, am I must change gcc to 4.2.x?

[fivemack]

I would suggest

a) build msieve against the newest version of gmp
b) run 'ulimit -s unlimited' before trying the square-root step

I have had this problem in the past and it came from gmp running out of stack space in the very-bignum arithmetic.

[loong]

Originally Posted by fivemack

I would suggest

a) build msieve against the newest version of gmp
b) run 'ulimit -s unlimited' before trying the square-root step

I have had this problem in the past and it came from gmp running out of stack space in the very-bignum arithmetic.

Thanks for your suggestion.
I've run 'ulimit -s unlimited' before trying the square root step, and msieve successfully passed the 1st dependency.
It looks like follows:

Tue May 3 10:49:46 2011 commencing square root phase
Tue May 3 10:49:46 2011 reading relations for dependency 1
Tue May 3 10:49:49 2011 read 2845889 cycles
Tue May 3 10:49:55 2011 cycles contain 7925904 unique relations
Tue May 3 10:58:42 2011 read 7925904 relations
Tue May 3 10:59:40 2011 multiplying 7925904 relations
Tue May 3 11:58:43 2011 multiply complete, coefficients have about 420.10 million bits
Tue May 3 11:58:50 2011 initial square root is modulo 34510537

till now, 5 hours has been passed, but the output is still shows as above,
I don't know whether such a long time is normal or an exception has occured which caused msieve stop to running?

[loong]

Thanks for all.
After 8 hours of square root phase, msieve successfully got the factors.

[xilman]

Originally Posted by loong

Thanks for all.
After 8 hours of square root phase, msieve successfully got the factors.

Good!

As a matter of interest, what N were you factoring and what is its factors?

Paul

[jasonp]

Redacted logfile, matrix of size 5.6M, I'd say somebody's RSA key :)

(8 hours is a little bit long for a dependency of this size, but not unusually so if the leading algebraic polynomial coefficient is at all large)