Python Driver for GGNFS and MSIEVE

[yoyoyogi]

The OS is Windows Server 2008 Standard SP2. I'm not familiar with this OS, but it was already installed on the system I'm using. All components for factoring were installed and executed as Administrator. I'm familiar with permission based issues in Linux, but not in Windows. Perhaps it has to do with executing Python on Windows Server? I'll look into this.
Thank you,
-Yogesh

[Brian Gladman]

I doubt that it has anything to do with Python since the missing file is one that should be written by msieve before it returns to the Python code. Moreover, msieve is signalling an error of some kind when it finishes, which is consistent with an msieve issue of some kind. I am not familiar with the details of what msieve does when it terminates but Jason may be able to suggest some possible failures that could have occurred.

Brian

[jasonp]

I think the problem is just that the polynomial selection didn't find any polynomials. How large is the input number?

Edit: of course you're factoring an RSA key. Inputs like this are too large for msieve's polynomial selection unless you have the graphics card version, or have many machines. Even then finding even one polynomial will take several days. With limited resources you're better off using pol51

[Brian Gladman]

Jason, would it be possible to have some meaningful error return codes from msieve? I could then improve feedback to users when things seem to go wrong.

Brian

[yoyoyogi]

Originally Posted by jasonp

I think the problem is just that the polynomial selection didn't find any polynomials. How large is the input number?

Edit: of course you're factoring an RSA key. Inputs like this are too large for msieve's polynomial selection unless you have the graphics card version, or have many machines. Even then finding even one polynomial will take several days. With limited resources you're better off using pol51

The input number is 154 digits. This would explain why I had success with the 100 digit example number from this beginner's guide (http://gilchrist.ca/jeff/factoring/n...ers_guide.html), but not this number on the same system. What kind of resources would it take to factor this number within 1-2 months?

Thanks for your help,
-Yogesh

[Andi47]

Originally Posted by yoyoyogi

The input number is 154 digits. This would explain why I had success with the 100 digit example number from this beginner's guide (http://gilchrist.ca/jeff/factoring/n...ers_guide.html), but not this number on the same system. What kind of resources would it take to factor this number within 1-2 months?

Thanks for your help,
-Yogesh

A Core 2 Duo (which is running 24/7) should be able to do it in ~2 months (or maybe 1-2 weeks longer).

You will need 2 GB RAM for the matrix.

[jasonp]

Originally Posted by Brian Gladman

Jason, would it be possible to have some meaningful error return codes from msieve? I could then improve feedback to users when things seem to go wrong.

I think now would be a good time to finally correct the error reporting in the library; will get to it as time allows.

[debrouxl]

Agreed, for 512-bit RSA keys (well, that's what many GNFS tasks of difficulty 154-155 are ) in a 2 months, you need at least a dual-core CPU and 2 GB of RAM.
As a complement to Andi's post: 3 GB of RAM would buy you more comfort (in case you end up with a 5M x 5M or larger matrix, or you simply need to use the computer for other tasks).

[Mini-Geek]

Tired of seeing something like "Found 1952010 relations, 99.5% of the estimated minimum (1961927)." and it sieving a whole extra portion, I decided to make this little patch to make it do post-proc it if it's 95% or more, instead of 100% or more: (bold means new code)

# Set global flags to control operation

...
VERBOSE = True
FRACTION_OF_ESTIMATED = 0.95
...
      cs = ('Found {0:d} relations, {1:2.1f}% of the estimated minimum ({2:d}).'
                            .format(curr_rels, pc, lats_p['minrels']))      
      write_string_to_log(cs)
      print(cs)
      if curr_rels > FRACTION_OF_ESTIMATED*lats_p['minrels']:

(lines 89 and 1709)
I think it'd be a good idea to implement this (though maybe with a different variable name, I just picked something so I could change it a bit more easily than re-finding that code) into the main releases of factmsieve.py.
This change has had only minimal testing, (i.e. I resumed a test and it got 99.5% of the estimated relations, and it went straight to post-proc as expected) but it's so simple I don't foresee anything going wrong because of it.

[Brian Gladman]

But this change is the same as reducing the minrels estimate. So I assume that you are, in effect, saying that the minrels estimate is 5% too high for the sort of numbers you are tackling. What are the lpbr/a values to which this 5% applies?

Brian

[Mini-Geek]

Originally Posted by Brian Gladman

But this change is the same as reducing the minrels estimate.

Huh, I hadn't thought of it that way...I just wanted to give it a little wiggle room so it'd try to post-proc before it was quite at 100%. But still, I guess you're right about what I was implying (though I didn't realize it at the time).

Or, to look at the issue from another point of view, maybe the script could be modified to see this information:
"Each section of work gets about x% of the estimate." and
"I'm now much closer to the estimate than x%."
And, instead of taking this action:
"So I'll sieve another full section of work and overshoot 100% by a lot."
Take this one:
"So I'll sieve what I can expect will put me a little over 100% and then see if I'm there."
e.g. if it goes from 84.5% to 99.5%, (15%) then it decides to only sieve 1/20th of the normal length, finishes at about 100.25%, (99.5%+15/20=100.25%) and continues to post-proc (or, in the event that it hasn't gone over 100%, the process repeats).

Originally Posted by Brian Gladman

So I assume that you are, in effect, saying that the minrels estimate is 5% too high for the sort of numbers you are tackling. What are the lpbr/a values to which this 5% applies?

Brian

The numbers I've ran since my modification were in the 92-95 digit range. They all have this line in their g9x-test.txt file:

Large prime bits: 25/25

I'm assuming that means the lpbr/a values are 25. (there are no other references to it in the files left behind after the cleanup)
I'd have to run more tests to see just how few relations it can have at different sizes for it to still finish, but on a c92 I got to 95.7% and it still finished. ("Found 1677546 relations, 95.7% of the estimated minimum (1753486).")
If you want me to run some trials to find the minimum relations for some size(s), let me know what size(s) and any other info I need.