mersenneforum.org FastECPP software and >50000 digit primality proof (reposted from NMBRTHRY)
 Register FAQ Search Today's Posts Mark Forums Read

2022-06-30, 19:02   #177
paulunderwood

Sep 2002
Database er0rr

2·19·113 Posts

Quote:
 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.

 2022-06-30, 23:39 #178 frmky     Jul 2003 So Cal 2·11·113 Posts 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.
2022-07-01, 05:50   #179
bur

Aug 2020
79*6581e-4;3*2539e-3

601 Posts

Quote:
 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.

Quote:
 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.

Last fiddled with by bur on 2022-07-01 at 05:56

2022-07-01, 06:19   #180
paulunderwood

Sep 2002
Database er0rr

2·19·113 Posts

Quote:
 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

Last fiddled with by paulunderwood on 2022-07-01 at 06:27

2022-07-01, 09:35   #181
bur

Aug 2020
79*6581e-4;3*2539e-3

601 Posts

Quote:
 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?

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.

2022-07-01, 10:55   #182
paulunderwood

Sep 2002
Database er0rr

2×19×113 Posts

Quote:
 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

Last fiddled with by paulunderwood on 2022-07-01 at 10:56

 2022-07-01, 11:02 #183 bur     Aug 2020 79*6581e-4;3*2539e-3 601 Posts 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?
2022-07-01, 14:43   #184
charybdis

Apr 2020

2·3·11·13 Posts

Quote:
 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.

 2022-07-01, 19:00 #185 bur     Aug 2020 79*6581e-4;3*2539e-3 601 Posts 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. Last fiddled with by bur on 2022-07-01 at 19:05
 2022-07-22, 20:23 #186 ryanp     Jun 2012 Boulder, CO 2·211 Posts W117239 = $$(2^{117239}+1)/3$$ has been proven prime with ecpp-mpi, and the certificate is processing on factordb.com.
2022-07-22, 21:49   #187
ryanp

Jun 2012
Boulder, CO

2·211 Posts

Quote:
 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.)

Last fiddled with by ryanp on 2022-07-22 at 21:49

 Similar Threads Thread Thread Starter Forum Replies Last Post bur GPU Computing 6 2020-08-28 06:20 JonathanM Information & Answers 25 2020-06-16 02:47 f1pokerspeed FactorDB 14 2014-01-09 21:06 princeps Math 15 2012-04-02 21:49 AntonVrba Math 96 2009-02-25 10:37

All times are UTC. The time now is 02:08.

Fri Oct 7 02:08:21 UTC 2022 up 49 days, 23:36, 0 users, load averages: 0.68, 0.85, 0.91