Small inconsistencies between mersenne.org and mersenne.ca factor databases

[LaurV]

Originally Posted by James Heinrich

Or I can generate a simpler list of exponent,factor if that suffices for your purpose, just let me know what you want.

Or you just can generate a list of factors, and pack it. It will save a lot of transfer time.

I know this is only tangent connected, but I already complained to you few times, mersenne.ca will tell me every time I search for a factor which is not in the data base, that the factor is not in the data base. It would be very easy and fast to check if that is a valid factor, and in case it is, add it to the data base together with the exponent that results from that calculus.

Usually I don't add factors to mersenne.ca, i.e. I report them to PrimeNet and let mersenne.ca deal with it. However I look to mersenne.ca quite often to see properties of the factors (like their smoothness of k, size in bits, etc) - those reports look much better there than I could see using pari (like "#binary(factor)", etc).

Therefore it would be very useful if, when somebody search for a factor and you can not find it in the db, you then run something like

getpfp(n)=
{
    if(!isprime(n),return(0));
    my(c);
    c=divisors(n-1);
    for(i=1,#c,
        if(c[i]<1000000000 && Mod(2,n)^c[i]==1, return(c[i]))
    );
    return(0);
}

and if that returns a prime, then add the pair to the database.

[James Heinrich]

Originally Posted by LaurV

Or you just can generate a list of factors, and pack it.

There is now an export option available for those who need it. PM me if you want access.

Originally Posted by LaurV

I already complained to you few times

I don't recall you ever mentioning this before...

Originally Posted by LaurV

Usually I don't add factors to mersenne.ca, i.e. I report them to PrimeNet and let mersenne.ca deal with it

Mostly because you can't add factors to mersenne.ca (except above 1000M)

Originally Posted by LaurV

mersenne.ca will tell me every time I search for a factor which is not in the data base, that the factor is not in the data base. It would be very easy and fast to check if that is a valid factor, and in case it is, add it to the data base together with the exponent that results from that calculus.

Perhaps not a bad idea, but I'm also cautious about adding a web interface to abuse my server CPU (imagine an evil spider crawling sequential numbers from 1 to infinity looking for factors, for example).
Validating a factor to a known exponent is easy and fast. Validating a known factor to (maybe) one of ~200-million potential exponents I don't think can be described as "fast". As a one-off issue when LaurV queries an unknown factor that's fine, but I'm not quite sure how to safeguard it. Suggestions?

[axn]

Originally Posted by LaurV

getpfp(n)=
{
    if(!isprime(n),return(0));
    my(c);
    c=divisors(n-1);
    for(i=1,#c,
        if(c[i]<1000000000 && Mod(2,n)^c[i]==1, return(c[i]))
    );
    return(0);
}

Is this faster than just invoking znorder( Mod(2,f) )?

[James Heinrich]

Originally Posted by axn

Is this faster than just invoking znorder( Mod(2,f) )?

I haven't a clue what the math is doing, but that actually does seem fast, at least tested locally. If that's how fast it is then I can look into adding it as requested.

[science_man_88]

Originally Posted by axn

Is this faster than just invoking znorder( Mod(2,f) )?

I wouldn't think faster except LaurV's code allows the testing of all possible p values that the factor could be a divisor of. if factors q-1 and gets the factorization of 2*k*p into primes back for all p values it could possibly be a candidate factor of. I could think of other optimizations of the code like eliminating p if the remaining factorization isn't of the proper modular class etc.

[LaurV]

Originally Posted by axn

Is this faster than just invoking znorder( Mod(2,f) )?

If you ignore the two primality tests (one for factor, one for result) and the limit check (which would be 2^32 for James, not 1G as in my example) and consider the argument always prime, then yes, my routine is faster. The limit will also avoid testing for larger divisors, gaining more time either. They are done about the same internally; znorder needs to know the divisors list (it gets slower for a non-prime, where my routine without isprime() will fail, returning a wrong result). Otherwise we would have a very fast way to factor numbers by invoking znorder so.

However, faster or not, my piece of code give James an insight if he wants a perl or php implementation (to which I know he is very good), versus znorder which he may not know what is it or how to php it.

The isprime() test is not included in my initial routine (but the <1G test is) and I added it "on spot" when I did the paste, because I assumed someone can try reporting factors which are not prime. The name itself says "get the p from a prime q" where q is a (known) factor of (an unknown) m=2^p-1. (you may recall that I keep this notation in all my posts). This as opposite of the general "getp()" which will accept a non-prime argument too, but is slower (same speed as znorder).

edit: re SM's post: that is bull

edit 2: re "I don't recall you ever mentioning this before...", it is on the posts where I was talking about "factoring by k". This is what is doing, take a k, compute 2kp+1, get its order, if prime, we found a factor. There I mentioned about searching for previously unknown factors on mersenne.ca (by searching I mean I press the search button and type my new-found factor, the site should do an evaluation and give me the p, instead of telling me "factor not found")

[science_man_88]

Originally Posted by LaurV

edit: re SM's post: that is bull

well that's what your code allows if you tested n to see if it's not 3 or 5 mod 8 or some other modular classes you could speed it up even more potentially, factoring n-1 is going to give you 2*k*p 's factorization extract a new p from the possibility list and it allows you to test divisibility for all of them. I'm wondering what you think it bull ?

[LaurV]

First because "LaurV's code allows the testing of all possible p values that the factor could be a divisor of" is not needed, two mersenne with prime exponents can't share a factor, so you stop at the first p. Second, that is what znorder does too, it factors q-1. About optimizations, we were not discussing finding factors, this piece of code and other even more optimized I posted in the past here:

/* trial factoring by k, specify a starting point and the outfput file */
ratf(q=2,fis="mf_by_k.out")=
{
    while(1,
        until(q%8==1 || q%8==7,q=nextprime(q+1));
        c=factorint(q-1)[,1]~;
        for(i=1,#c,
            if(c[i]<1000000000 && Mod(2,q)^c[i]==1, print(q" divides M"c[i]); write(fis,q","c[i]))
        )
    );
}

edit: this doesn't need the full list of divisors, but yet, the most time is not spent enumerating the primes and their modular class, but factoring q-1. Anyhow, this is another discussion, not related to the (current) title of the subforum

[James Heinrich]

Originally Posted by LaurV

it would be very useful if, when somebody search for a factor and you can not find it in the db ... add the pair to the database.

And since you were kind enough to provide the code, it now does just that.

[LaurV]

Originally Posted by James Heinrich

And since you were kind enough to provide the code, it now does just that.

You are on the way to rival Scott, who fixes the Misfit bugs few minutes before we report them!
Good job, thanks a lot. I go to bed now (23:40 here) and tomorrow is my working Saturday (here we work alternating Sat's)

[James Heinrich]

Any suggestions for how to fully factor moderately-large (50-150 digit) numbers? I run into these most often as k values, and the ones that are <50 digits I can factor pretty much instantly, but the large ones can take some time. Until now I've just been aborting and saying "too large" and not showing the relevant details, but I've now started collecting them in hopes of finding some kind of offline processing. I've manually tried a few of them with Dario's Java ECM tool, and some are factored within a second while others (e.g. "5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836") have been crunching for more than 5 hours already. So I'd like to find some kind of offline tool that runs under Windows where I can feed it a list of presumably-composite numbers and let it chew on them and spit out the factorization. Suggestions?