Odd behaviour in ECM with p95 v29.4

[lavalamp]

As a lark I decided to do some ECM on an unreasonably large number, which has some known factors already; 3^5198+1

I remember that Prime95 seems to be faster at stage 1 than GMP-ECM, so I decided to try it for this. From the documentation, it is possible to set up ECM in the worktodo.txt file as follows:

ECM2=k,b,n,c,B1,B2,curves_to_run[,"comma-separated-list-of-known-factors"]

Unfortunately I encountered 2 issues.

Firstly, Prime95 seems to either crash or enter an infinite loop if I jam all of the known factors together, such as this:

ECM2=1,3,5198,1,1000000,1000000,1000,39144695176586244470086916951706412096252695690001050295503066390090860724430123140913783684262335502958184703622641033499578807467353838957246838778730

I have to open up task manager and force close Prime95 to stop it when it enters an infinite loop, but a couple of times it told me there was uncaught exception and asked me if I wanted to debug. So I figured perhaps there is some (undocumented) limit to the size of factors given that way (even though this is "only" 152 digits).

But the second issue is that even when I give the prime factors individually, they seem to be ignored. As a test I ran this:

ECM2=1,3,5198,1,11000,11000,100,2

There are few small factors, but when the only factor I gave it is 2, it still sometimes "finds" the factor 2 for me, then stops.

As a user I would like to be able to supply all known factors, then have it divide them out and run ECM on the remainder. Or better yet if there were simply a way to directly input the number I want to run ECM on, insted of requiring it be representable as k*b^n+c first.

Reporting already known factors seems like unexpected behaviour, and in this case prevents me from running ECM at all, as it is overwhelmingly likely to find one of the small factors then stop.

If it matters, I am running this on Windows 7 on a Haswell CPU with the FMA3 FFT.

[retina]

Originally Posted by lavalamp

Or better yet if there were simply a way to directly input the number I want to run ECM on, insted of requiring it be representable as k*b^n+c first.

k=0
b=0
n=0
c=<your number>

[lavalamp]

Originally Posted by retina

k=0
b=0
n=0
c=<your number>

I believe the same issue occurs when using large numbers as inputs here too.

Edit: But please tell me what you believe 0^0 is.

Edit 2: I ran a quick test on this (with n=1), and c = c2329. The result was, "Cannot initialize FFT code, errcode=1003"

[nordi]

Originally Posted by lavalamp

ECM2=1,3,5198,1,1000000,1000000,1000,39144695176586244470086916951706412096252695690001050295503066390090860724430123140913783684262335502958184703622641033499578807467353838957246838778730

You need to put double quotes around the known factors like this:

ECM2=1,3,5198,1,1000000,1000000,1000,"39144695176586244470086916951706412096252695690001050295503066390090860724430123140913783684262335502958184703622641033499578807467353838957246838778730"

[retina]

Originally Posted by lavalamp

Edit: But please tell me what you believe 0^0 is.

Any finite value will do. Since k=0 also.

But seriously, yes, you caught me there. n=1 and/or b=1 might be a better choice.

[lavalamp]

Originally Posted by nordi

You need to put double quotes around the known factors like this:

ECM2=1,3,5198,1,1000000,1000000,1000,"39144695176586244470086916951706412096252695690001050295503066390090860724430123140913783684262335502958184703622641033499578807467353838957246838778730"

This also seems to crash P95.

Edit: Correction, it didn't crash it, but it temporarily wiped all text from the worker window, but then started running again. Albeit very slowly. I will investigate further.

Edit 2: OK, that seems to work now. I think the PC was a bit overloaded with some other work.

[axn]

Originally Posted by lavalamp

This also seems to crash P95.

Edit: Correction, it didn't crash it, but it temporarily wiped all text from the worker window, but then started running again. Albeit very slowly. I will investigate further.

Edit 2: OK, that seems to work now. I think the PC was a bit overloaded with some other work.

The recommended way is:

ECM2=1,3,5198,1,1000000,1000000,1000,"2,5,2713,12553493,18495731521,3536878321177,70601370627701,798087896392921,31181934032520084217683832052280453426721598216094871026492932287412448715951254226575121"

i.e. comma-separate the list of factors, instead of taking their products. But I suppose that might work also.
The whole point of using P95 is that it can run k*b^n+/-c numbers very efficiently. If the number is not of that form, you might as well use GMP-ECM for stage1, because it wouldn't be run efficiently by P95 (assuming it can run it at all -- I dont think P95 supports arbitrary numbers).

[lavalamp]

Originally Posted by axn

The whole point of using P95 is that it can run k*b^n+/-c numbers very efficiently. If the number is not of that form, you might as well use GMP-ECM for stage1, because it wouldn't be run efficiently by P95 (assuming it can run it at all -- I dont think P95 supports arbitrary numbers).

That's a little bit what I assumed, but then I thought the factors would be divided out and that it would become a general number.

If the k*b^n+c form is faster for ECM, then would it make sense to search for representations of general numbers in that form, akin to searching for polynomials in GNFS? Although I can see the value for c becoming quite large.

[axn]

Originally Posted by lavalamp

That's a little bit what I assumed, but then I thought the factors would be divided out and that it would become a general number.

No. The factors are used while doing the gcd (at the very end), and if it finds any that is already in the list, it ignores it and keeps going.

Originally Posted by lavalamp

If the k*b^n+c form is faster for ECM, then would it make sense to search for representations of general numbers in that form, akin to searching for polynomials in GNFS? Although I can see the value for c becoming quite large.

Only a very small fraction of numbers can be represented using the k*b^n+c form (assuming some restriction on the sizes of each of those constants). Let's say that k,b,n,c all are restricted to be at most 64 bits. Then there are only 256 bits worth of numbers that we can represent. It is highly unlikely that we can find a viable (k,b,n,c) represenation for an arbitrary number so that it can be handled by P95.