"lanczos error: only trivial dependencies found" with massive oversieving

[bsquared]

Originally Posted by R.D. Silverman

Morons. Morons. Morons. I am surrounded by morons.

Did anyone happen to notice that the number trying to be factored is even? That it is 2 mod 4?
That there are no squares that are 2 mod 4?

Why let two seconds of thought get in the way of massive blind computing?

Nobody cares about the OP number, including the OP.

[chris2be8]

As a rough guess QS on a C150 would take about 500.000 CPU hours (give or take an order of magnitude).

The last C150 I did with GNFS took about 360 CPU hours in total (not all on the same system).

So don't even think about factoring one with QS.

After reading the beginners guide I would recommend factoring RSA100, RSA110, RSA120, RSA130 and RSA140 to work your way up to C150.

Chris

[VBCurtis]

Originally Posted by debrouxl

For factoring 512-bit RSA keys, 85M raw relations represents significant oversieving. IME, 70M raw relations do the job.

Note I specified 31-bit large prime bounds. Are you sure 70M is enough, or are you thinking of 30-bit bounds? I failed to build a matrix on a C155 with 78M relations while 80M worked, for example.

[debrouxl]

Originally Posted by VBCurtis

Note I specified 31-bit large prime bounds. Are you sure 70M is enough, or are you thinking of 30-bit bounds? I failed to build a matrix on a C155 with 78M relations while 80M worked, for example.

Oh, right. I'm thinking of 29-bit LPs bound, which is what RSALS and a couple solo 512-bit RSA key factoring jobs of mine used.

[R.D. Silverman]

Originally Posted by bsquared

Nobody cares about the OP number, including the OP.

Missing the point yet again.

The OP complained that he could not get a successful dependency even after massive
oversieving. Two seconds of thought, plus a little knowledge about how the algorithm
worked would have told why.

Instead, people just throw CPU time at the problem. They can't be bothered reading how the algorithm works.

[bsquared]

Originally Posted by R.D. Silverman

Missing the point yet again.

The OP complained that he could not get a successful dependency even after massive
oversieving. Two seconds of thought, plus a little knowledge about how the algorithm
worked would have told why.

Instead, people just throw CPU time at the problem. They can't be bothered reading how the algorithm works.

Did you READ his post? Can you be bothered to understand how msieve works? Taking the time to do either would have revealed to you that the factor of 2 and several other small factors were REMOVED prior to starting QS.

But, as I said, it is all moot. Noone cares about that particular number. The OP was just getting a process in place to work on larger numbers. The comically large oversieving did indeed cause a problem in the QS filtering and matrix building, but I hope Jason doesn't spend a millisecond figuring it out.

[VBCurtis]

Originally Posted by debrouxl

Oh, right. I'm thinking of 29-bit LPs bound, which is what RSALS and a couple solo 512-bit RSA key factoring jobs of mine used.

whoops! I meant 30-bit in all places this thread I used "31". Mea culpa.

[VBCurtis]

Originally Posted by R.D. Silverman

Missing the point yet again.

The OP complained that he could not get a successful dependency even after massive
oversieving. Two seconds of thought, plus a little knowledge about how the algorithm
worked would have told why.

Instead, people just throw CPU time at the problem. They can't be bothered reading how the algorithm works.

I spent more than two seconds, and fail to see the reason you find obvious. The small factors were taken out, as shown in the OP, and QS was used for the 74-digit cofactor. Can you explain your two seconds of thought for what is obvious?

[eigma]

Thanks bsquared, this is exactly the context of my OP (just setting up a process for a larger project).

I have started experimenting with GNFS. I'd like to check my understanding of a few things.

First, it seems that unlike QS, GNFS does not use randomness. Does this mean that for a particular *.job input file, gnfs-lasieve4e will always produce the same spairs.out?

factmsieve.py determines qstep from the number of digits in n alone, correct? It does not depend on any other parameters, the polynomial selected, etc.?

Sieving overlapping Q ranges will presumably duplicate work. Is it *harmful* to the postprocessing though? If it is convenient for me to do a little overlapping work (perhaps it helps with parallelization), are there considerations other than efficiency why I should avoid it?

As long as I avoid or minimize duplicate coverage of the Q range [Q0, +inf), and cover most of it "densely", can I change qstep in the middle of a job? In other words, can I merge spairs.out from two sieves with different qsteps?

In general, what is the Q parameter? I scanned the wikipedia page for GNFS but couldn't find a corresponding concept.

[jasonp]

Originally Posted by bsquared

The comically large oversieving did indeed cause a problem in the QS filtering and matrix building, but I hope Jason doesn't spend a millisecond figuring it out.

I already know why it happens; the QS linear algebra begins by chopping the matrix after filtering into the correct proportions, then the LA removes any singletons and cliques. In the face of very large oversieving, the chopping process is likely to destroy the nullspace of the matrix so there is no linearly dependent part to hold a solution.

[VBCurtis]

Originally Posted by eigma

First, it seems that unlike QS, GNFS does not use randomness. Does this mean that for a particular *.job input file, gnfs-lasieve4e will always produce the same spairs.out?

factmsieve.py determines qstep from the number of digits in n alone, correct? It does not depend on any other parameters, the polynomial selected, etc.?

1. Correct, the output is deterministic.

2. Yes. See code nearish line 500 for where qstep is set. I edited my copy of the script to use qstep 400000 for jobs this size and a quad-core desktop. Each 100k block on each core takes a few hours.

You can concatenate any relations files you wish from a single polynomial/parameter choice, and the filtering stage (or the utility remdups) will remove duplicate relations so overlapping q-ranges is merely a waste of time. remdups has the advantage that it saves a file with the duplicate relations removed, so all future filtering attempts don't have to waste CPU time finding and removing the duplicates.

I've found good efficiency starting my sieving at q = alim/rlim divided by 4, and sieving until q is roughly equal or slightly higher than alim/rlim. I've also found (with no theory to support the observation) that for smaller jobs alim/3 is better (measured by hours needed for the sieving step) to start at, and for large jobs alim/6 or lower is fine. For your C154s, you might choose alim=rlim=30M, and sieve a range of something like 8M to the low 30's. factmsieve will choose these parameters if you let it, but it defaults to start at q = alim/2. The time-per-relation starts to fall off around q = alim/rlim, and by q = 2* alim it's pretty bad. So, we choose parameters that complete the job before getting near that range, so that even a below-avg poly will still complete a factorization.

The previous paragraph is an example of the tweaking of parameters that might produce efficiency gains of 0-15% vs the default script settings. The script was developed and tested when GNFS-140 was a time-consuming endeavor, and the script assumes anyone who tackles GNFS-150+ is willing to tinker a little in order to save a day or two of CPU time in part because few people had both the resources to do a bunch of tasks that size and the interest in improving the script (the big guns are, mostly, so experienced that they set the parameters by hand and runs the steps without the script).