mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2022-06-30, 19:02   #177
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×1,063 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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.
paulunderwood is offline   Reply With Quote
Old 2022-06-30, 23:39   #178
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

22×3×7×29 Posts
Default

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.
frmky is offline   Reply With Quote
Old 2022-07-01, 05:50   #179
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

11048 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
bur is offline   Reply With Quote
Old 2022-07-01, 06:19   #180
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

425210 Posts
Default

Quote:
Originally Posted by bur View Post
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
paulunderwood is offline   Reply With Quote
Old 2022-07-01, 09:35   #181
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

22·5·29 Posts
Default

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.
bur is offline   Reply With Quote
Old 2022-07-01, 10:55   #182
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

109C16 Posts
Default

Quote:
Originally Posted by bur View Post
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
paulunderwood is offline   Reply With Quote
Old 2022-07-01, 11:02   #183
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

22·5·29 Posts
Default

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?
bur is offline   Reply With Quote
Old 2022-07-01, 14:43   #184
charybdis
 
charybdis's Avatar
 
Apr 2020

14358 Posts
Default

Quote:
Originally Posted by bur View Post
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.
charybdis is offline   Reply With Quote
Old 2022-07-01, 19:00   #185
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

22·5·29 Posts
Default

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
bur is offline   Reply With Quote
Old 2022-07-22, 20:23   #186
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

409 Posts
Default

W117239 = \((2^{117239}+1)/3\) has been proven prime with ecpp-mpi, and the certificate is processing on factordb.com.
ryanp is offline   Reply With Quote
Old 2022-07-22, 21:49   #187
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

6318 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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
ryanp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
For which types of primes is GPU primality test software available? bur GPU Computing 6 2020-08-28 06:20
Fastest software for Mersenne primality test? JonathanM Information & Answers 25 2020-06-16 02:47
APR-CL as primality proof f1pokerspeed FactorDB 14 2014-01-09 21:06
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
PRIMALITY PROOF for Wagstaff numbers! AntonVrba Math 96 2009-02-25 10:37

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


Fri Aug 12 08:58:10 UTC 2022 up 36 days, 3:45, 2 users, load averages: 1.61, 1.43, 1.37

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔