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

[wombatman]

Originally Posted by 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?

YAFU. Can churn through a list of numbers, especially if they're 100 digits or less each.

[axn]

Originally Posted by James Heinrich

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.

What is the source of this number? I can't believe that someone found an actual factor of mersenne number this big!

[LaurV]

Originally Posted by wombatman

YAFU. Can churn through a list of numbers, especially if they're 100 digits or less each.

+1.
On your particular C124 example, Yafu gets out small composites and a PRP9, leaving a C109 in few seconds, which survives the 0.33 ECM, therefore the time to factor it will be the time to run GNFS on a C109. In 4-cores, 3.8GHz machine where I tried it, ECM is about 24 minutes, poly search about 12-13 minutes, sieving about 90 minutes to 2 hours depending of how a good a poly you got, then the LA and square root up to a hour depending on your luck with the square root. You can't make it faster, with this hardware.

[James Heinrich]

Originally Posted by axn

What is the source of this number? I can't believe that someone found an actual factor of mersenne number this big!

I don't remember which exponent it's from offhand. These numbers will either k-values of factors, which could either be factors as found (either prime or composite factors), but mersenne.ca also displays k-values of all composite factors of all known prime factors as well, which is probably what my example is.

[LaurV]

Originally Posted by axn

What is the source of this number? I can't believe that someone found an actual factor of mersenne number this big!

Isn't a factor of M1171?

(edit: here is how I found it:

gp > p=2; x=0; until(x==p, a=0; until(a,[p=nextprime(p+1), a=isprime(b=2*k*p+1)]); print(p": "x=getp(b,p+1)))
331: 332
379: 380
1171: 1171
gp > ##
  ***   last result computed in 1,382 ms.
gp >

edit 2: getp() is a slower version of getpfp which does not requires anything to be prime, and does not factor the arguments, working by blind additions and shifts:

/*get smallest p such as n divides 2^p-1*/\
/*print(k++", "ggg=2*k*(1<<31-1)+1", "gggg=getp(ggg,10^10)", "ggg%gggg", "isprime(ggg))*/
getp(n,limt)=
{
    if(n<3 || n%2==0, print("Only odd positive numbers!");return);
    
    rg=1;
    sm=0;
    until(rg==1 || sm>=limt, 
        rg+=n;
        while(rg%2==0 && sm<limt, 
            rg>>=1;
            sm++;
            if(bitand(sm,1048575)==0, printf("...%d...%c",sm,13));
        )
    );
    return(sm);
}

)

edit 3: just realized I didn't give the factors, in case your tool still crunching:

P65 = 79001680667399413021755551127728881024073264821649477463074552981
P44 = 80372772078870023311028629526527251806209541
NFS elapsed time = 8766.1264 seconds.

[axn]

Originally Posted by LaurV

Isn't a factor of M1171?

Indeed, I should've known that this would've come out of a big NFS factor of a small mersenne.

Originally Posted by James Heinrich

I don't remember which exponent it's from offhand. These numbers will either k-values of factors, which could either be factors as found (either prime or composite factors), but mersenne.ca also displays k-values of all composite factors of all known prime factors as well, which is probably what my example is.

k-values of composite factors are meaningless numbers. And it is a good thing you're not showing them on the site (eg:- http://www.mersenne.ca/exponent/1009)

[LaurV]

Originally Posted by axn

And it is a good thing you're not showing them on the site (eg:- http://www.mersenne.ca/exponent/1009)

He does (in tooltips)
Which is ok, even if they are meaningless.
(edit: the "too big" in this case is a very good thing too, they don't need to waste cpu time for factoring)

[James Heinrich]

Originally Posted by axn

k-values of composite factors are meaningless numbers

Thanks. I've taken out the k-values and P-1 bounds for composite factors.

[axn]

Originally Posted by James Heinrich

Thanks. I've taken out the k-values and P-1 bounds for composite factors.

The P-1 bounds for composite factors is derived from the P-1 bounds of the individual prime factors that make up the composite: {max(B1), max(B2)}. AFAICT the values you were displaying was according to this logic, so they were correct (if a bit useless). Obviously, this doesn't involve factoring the composite factor's k -- that part is very much useless.

PS:- I am also unsure of the usefulness of the TF GHz days displayed against composite factors, because it doesn't correspond to the actual way in which TF would discover those factors.

[GP2]

Originally Posted by axn

k-values of composite factors are meaningless numbers.

It's redundant to store both the factor and the k-value in the database, since one is so easily derived from the other, via f = 2kp + 1.

But arguably it's k that we should store and keep track of, and not the full factor.

The factor itself is relatively uninteresting, in the same way that the actual decimal expansion of a Mersenne number is uninteresting, as opposed to the exponent.

At the moment 28,869,906 factors are known, for p between 0M and 1000M. Since p is on average a bit less than 9 decimal digits, that means just under 259MB (247 MiB) of wasted storage, since the factors are stored as strings.

Since the distribution of k skews overwhelmingly toward small values, the savings would be even greater percentage-wise. In the vast majority of cases, we could replace a 9 or 10 digit factor with a one or two digit k value.


On the other hand, one advantage of storing the factor itself is that mathematically any given number can be a factor of at most one Mersenne number with a prime exponent (i.e., the exponents that we care about). So you can make the factor field the primary index of your database table. But presumably it would be just as efficient to use (exponent, k) as a unique index.

[science_man_88]

Originally Posted by GP2

On the other hand, one advantage of storing the factor itself is that mathematically any given number can be a factor of at most one Mersenne number with a prime exponent (i.e., the exponents that we care about). So you can make the factor field the primary index of your database table.

one other positive is that to know which k belong with which p if that is wanted it's to store both k and p separately it takes log_2(k)+log_2(p) bits at very least where as storing the factor alone takes about the same anyways so other than having to figure out the p costing a little more it allows all the functionality and potentially more to store the factor and p values.