Aliqueit.exe discussion

[schickel]

Originally Posted by bsquared

FWIW, his paper is available through JSTOR.

Yeah, but unless you have access through an institute of higher learning or library, you have to fork over $24 (US) for the privilege of reading it.....

[bsquared]

Originally Posted by schickel

Yeah, but unless you have access through an institute of higher learning or library, you have to fork over $24 (US) for the privilege of reading it.....

Call me dense, but I never realized that! Now that you mention it, there is a little blurb at the corner of the page saying "Your access to JSTOR provided by...". I guess I've taken for granted that access over the years (unlike my access to here, which I really do need to do my day job and which occasionally is useful for personal projects as well).

[smh]

Originally Posted by axn

EDIT:- A test scenario would be, time aliqueit on a aliquot sequence till 90-digits. Then collect all the LHS from that and feed it to msieve as a batch. IF the time difference is +/- 2%, call it a tie.

I did this for two sequences (with prefer_yafu = false in aliqueit.ini). I ran 840 to completion and 251970 to 80 digits.

Sequence    aliqueit  msieve
840          1:19      1:11
251970      25:45     29:45

[mklasson]

Originally Posted by smh

I did this for two sequences (with prefer_yafu = false in aliqueit.ini). I ran 840 to completion and 251970 to 80 digits.

Sequence    aliqueit  msieve
840          1:19      1:11
251970      25:45     29:45

I for one would still like to see another run and see how the times change. Seems like just one lucky curve more or less on one of the bigger composites would sub/add a couple of minutes. Oh well, maybe I'm overly scared of the big bad variance wolf.

[...] Well, I ran a test myself too using the same 251970 to 80 digits. I probably should've chosen another sequence as the distribution of factor sizes in the sequence should favor more or less ecm. If all composites split into two big factors that we have very slim chances of cracking with ecm then less ecm is preferable, whereas if all composites only have small factors then lots of ecm seems preferable... Maybe the effect of that is negligible in practice though.

aliqueit 16m 39s
msieve 24m 9s

Oh... I just realised I ran msieve without -e... Well, at least that appears to be suboptimal. I'll give it another run.

[mklasson]

Alright, msieve -e vs aliqueit on seq 251970 to 80 digits:

aliqueit 18m 27s
msieve -e 18m 35s

There's a 10% diff between the first and second aliqueit runs... I'm going for a third one!

[mklasson]

And the third run on 251970:

aliqueit 18m 5s
msieve -e 20m 39s

So aliqueit's range here over three tests is 16:39 to 18:27 and msieve's range over two tests is 18:35 to 20:39. Both programs' worst times are 10% higher than their best. That's all the testing I'm prepared to do right now. Seems like aliqueit just might have a little edge in this scenario.

[10metreh]

I reckon taking a sequence to 96 digits is going to produce particularly bad results from msieve -e, and it will start to improve afterwards.

[Greebley]

I was curious what ecm aliqueit would try on the 150 digit cofactor for 4788. It didn't seem to check over the 11e6 when I was expecting a 43e6 type check as recommended in the thread. Unfortunately, I don't really understand how it chooses the ecm levels to know if this is an issue with my ini file (or lack of it - it is possible I tested in a directory that the ini wasn't in), or just the fact you need to run ecm outside aliqueit for very large numbers.

[Mini-Geek]

Originally Posted by Greebley

I was curious what ecm aliqueit would try on the 150 digit cofactor for 4788.

It's pretty simple, actually. Here's all the info you need. From aliqueit.ini: (default settings)

//Formulae used to determine the maximum factor size we will do ecm to.
//For QS: <qs_k> * input_digits + <qs_m>
qs_k = 0.448
qs_m = -11.26

//For GNFS: <gnfs_k> * input_digits + <gnfs_m>
gnfs_k = 0.235
gnfs_m = 9.4

And from aliqueit.cc (code, default):

//run ecm on big input_numbers using ~ gmp-ecm recommended settings and trying to make the ecm time take a constant fraction of the qs/gnfs time.
int run_ecm_big( string input_number, vector<mpz_class> & new_factors ) {
    int ecm_settings[][3] = {
        { 20, 11000, 74 },
        { 25, 50000, 214 },
        { 30, 250000, 430 },
        { 35, 1000000, 904 },
        { 40, 3000000, 2350 },
        { 45, 11000000, 4480 },
        { 50, 43000000, 7553 },
        { 55, 110000000, 17769 },
        { 60, 260000000, 42017 },
        { 65, 850000000, 69408 },    //quick, someone find a way for this to be useful!
    };
    float max_factor_size = get_ecm_level( (unsigned int)input_number.size() );

    int prev_level_digits = 0;
    bool done = false;
    for( int level = 0; !done && level < sizeof( ecm_settings ) / ( 3 * sizeof( int ) ); ++level ) {
        int b1 = ecm_settings[level][1];
        int curves = ecm_settings[level][2];
        if( max_factor_size < ecm_settings[level][0] ) {
            curves = (int)( curves * ( max_factor_size - prev_level_digits ) / ( ecm_settings[level][0] - prev_level_digits ) );
            if( !curves ) break;    //if curves is 0 we'll ecm forever (or until we find a factor, whichever comes first)
            done = true;
        }
//run P-1, P+1, and ECM for the given size, removed from this snippet for size
    }

So with default aliqueit.ini settings, (i.e. those NFS ECM settings and an NFS cutoff of at most 150) it will run ECM to a bit level of 0.235*150+9.4=44.650, which means it runs 74@11e3, 214@5e4, 430@25e4, 904@1e6, 2350@3e6, and floor(4.65/5*4480)@11e6 = 4166@11e6.

I think that the settings don't run enough ECM for large numbers, like the c150, and an NFS seems likely to be necessary, so we skipped the 11e6 step and are instead running several thousand at 43e6.

[Greebley]

Ok, so if I thought 150 should have a value of 47 (40% of the 7553 at 43e6)
and solve to keep 100 the same, I get:

gnfs_k = 0.282
gnfs_m = 4.7

so .282*100+4.7 = 32.9 = .235*100+9.4 and
.282*150+4.7 = 47

125 digits would be 39.95 instead of 38.775 and
90 digits would be 30.08 instead of 30.55.

What do you think?

[axn]

Originally Posted by Greebley

What do you think?

Not very scientific, IMO. If you're going to pull numbers out of thin air, might as well go with aliqueit's numbers. Otherwise, do a systematic calulation: Calculate a table of ECM effort (in CPU hours or equivalent unit) Vs probability of success. Then figure out the optimal point of ECM/NFS cutover based on estimated effort for NFS.

THAT... would be scientific.

EDIT:- There is a 1/3 heuristic that says that you should do full 50-digit ECM pre-testing before doing a GNFS on c150. So in aliquieit parlance, that'd translate to g_k = 0.333, g_m = 0