FastECPP software and >50000 digit primality proof (reposted from NMBRTHRY)

[paulunderwood]

Originally Posted by sweety439

For (10^1031-1)/9, N-1 can be easily >= 1/3 factored, and N-1 primality proving can be used, I think 10^1000+453 (which is the next prime after 10^1000) may be better.

The factors of N+-1 don't matter for a test number. I could have equally said 2^4253-1.

[frmky]

The latest git commit replaces GMP's mpz_probab_prime_p() with a 2-SPRP test for numbers >= 3000 bits. This is a significant speedup for those not using GWNUM.

[bur]

Originally Posted by paulunderwood

Those are accumulative times. Each step is quicker than the last. It runs at O(log(n)^4) meaning a number twice in length takes 16 times as long to compute. So as each of the two stages finish it will look like it is speeding up.

Thanks, I'd have assumed it'd be along O(log(n)^2) like, afair, NFS factoring and LLR testing is. Generally, what I was after though, is it possible to say which value these parameters qroot/etc. will end up with when the proof is done? What I'd like is, to look at the current output and get an estimate how far the proof has progressed.

I suggest that you start with some small test cases like (10^1031-1)/9.

Yes, I proved a 1200 digits prime from factordb's list that was already gone when I submitted it (quite some activity there now, apparently). Then a larger 3000 digits one. So I got a feeling for how long the proof takes, but especially for long proofs it'd be nice to look at the output and know "it's 50% done".



Also, is it possible to explain the meaning of qroot, Cornacchia, trial div, primality in this context to someone with only some grasp of the underlying mathematical concepts? Thanks.

[paulunderwood]

Originally Posted by bur

Thanks, I'd have assumed it'd be along O(log(n)^2) like, afair, NFS factoring and LLR testing is. Generally, what I was after though, is it possible to say which value these parameters qroot/etc. will end up with when the proof is done? What I'd like is, to look at the current output and get an estimate how far the proof has progressed.

Yes, I proved a 1200 digits prime from factordb's list that was already gone when I submitted it (quite some activity there now, apparently). Then a larger 3000 digits one. So I got a feeling for how long the proof takes, but especially for long proofs it'd be nice to look at the output and know "it's 50% done".



Also, is it possible to explain the meaning of qroot, Cornacchia, trial div, primality in this context to someone with only some grasp of the underlying mathematical concepts? Thanks.

I do it like this. If the current number of bits is for example 3/4 of the starting number of bits, then it has left (3/4)^4 == 3^4/4^4 = 81/256 about 1/3 to go. Note also each step is about 70 bits on average.

https://en.wikipedia.org/wiki/Elliptic_curve_primality

[bur]

I do it like this. If the current number of bits is...

Sorry, if I'm being dense, but where do I find the current number of bits in the output?

https://en.wikipedia.org/wiki/Elliptic_curve_primality

I was hoping someone would feed me a simplyfied version ;) I'll try and understand the general concept and then hopfully be back with more specific questions.

[paulunderwood]

Originally Posted by bur

Sorry, if I'm being dense, but where do I find the current number of bits in the output?

I was hoping someone would feed me a simplyfied version ;) I'll try and understand the general concept and then hopfully be back with more specific questions.

In stage one is says "Step [X]: xxxxx bits". The number of bits is also printed in stage 2.

A good start would be to learn about the arithmetic of rational points on elliptic curves: https://en.wikipedia.org/wiki/Elliptic_curve

[bur]

Thanks! I can sort of follow the wikipedia article on ECPP. The "trial division" from the output relates to finding a prime factor q of m?

I don't really see why the number of bits reduces, that makes it look like a recursive algorithm like Goldwasser-Kilian, in Atkins-Morain I can't find an iterative step. Or is it the construction of the curve?

[charybdis]

Originally Posted by bur

I don't really see why the number of bits reduces, that makes it look like a recursive algorithm like Goldwasser-Kilian, in Atkins-Morain I can't find an iterative step. Or is it the construction of the curve?

The Atkin-Morain example given on Wikipedia is too small for you to see the recursion in action. In real life, the value of q or the largest prime factor of s will be almost as big as N and must itself be proved prime; in the example that was 13.

[bur]

So the continually decreasing bitsize is the size of the current q? Which is also why the steps get faster while proceeding through the algorithm, because ecpp proving the current q gets faster?

The trial factoring is really trial factoring of q? If so, what does the displayed value mean?

Cornacchia is the algorithm for finding a and b from the discriminant, correct? What does the value that fastecpp displays mean?

qroot seems to be related to the creation of the elliptic curve, correct? (and again, what does the displayed value mean)

What happens during the second step? Is it the creation of the certificate?

Thanks.

[ryanp]

W117239 = \((2^{117239}+1)/3\) has been proven prime with ecpp-mpi, and the certificate is processing on factordb.com.

[ryanp]

Originally Posted by sweety439

Wow!!!

Can you also run this number? This number is just few digits longer.

No. (And I believe the administrators have requested that you stop asking others to test numbers for them.)