mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2013-09-09, 17:05   #12
jack
 
Jul 2013

3 Posts
Default

Quote:
Originally Posted by WraithX View Post
Good job on finding a problem certificate.
Assuming the verifier correctly computes the values, i.e., assuming the Hasse interval is defined using integer square root and not real one... but is it the case?

Quote:
we now use the ceil(sqrt(n)) in the calculations instead of floor(sqrt(n)).
What about floor(2*sqrt(n))?
jack is offline   Reply With Quote
Old 2013-09-09, 19:40   #13
jack
 
Jul 2013

3 Posts
Default

Quote:
Originally Posted by jack View Post
Assuming the verifier correctly computes the values, i.e., assuming the Hasse interval is defined using integer square root and not real one... but is it the case?

What about floor(2*sqrt(n))?
Of course, I meant "What about floor(2*sqrt(n)) instead of 2*floor(sqrt(n))?" If the decimal part of sqrt(n) is greater than or equal to 1/2, this is not the same.
jack is offline   Reply With Quote
Old 2013-09-09, 22:36   #14
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32×101 Posts
Default

Two independently written ECPP implementations generated similar M (R*S) values. I noticed that Primo uses the smaller value, which is probably an optimization (search the smallest m values first). I made my program sort the m values by size and I get the same value Primo uses.

Two separate verifiers end up doing the same calculations. I had looked at the conditions to generate m from u and v, but I missed this gotcha. Yes, both verifiers are doing all integer math. Using FP math would add a lot of complication.

Technically I don't believe these conditions are even required, as the theorem's conditions consist of "let m be an integer, let q be a prime dividing m and q > (N^1/4+1)^2, ..." (Atkin/Morain 5.2). But we know from the proof of the theorem and ECPP implementations that m is going to be within the Hasse interval (Goldwasser & Killian 3.3(1) or Atkin & Morain 4.2). m = N + 1 - t where |t| <= 2sqrt(N). The test is an easy sanity check that things look reasonable and the EC calculations have a chance of succeeding. So WraithX's solution of using 2*ceil(sqrt(N)) looks good to me. Perhaps ceil(sqrt(4N)) for a slightly tighter bound.

Edit: actually given the limits, I think floor(sqrt(4N)) should do it, which is basically what Jack just wrote. :)

Last fiddled with by danaj on 2013-09-09 at 23:04
danaj is offline   Reply With Quote
Old 2013-09-10, 05:13   #15
jack
 
Jul 2013

112 Posts
Default

Quote:
Originally Posted by danaj View Post
Using FP math would add a lot of complication.
Yes but there is no need of FP math. Assuming you have an integer N, in order to know whether the decimal part (dp) of its integer square root (isqrt) is less than 0.5 or greater than or equal to 0.5, all you have to do is to compute isqrt(4N). Now, if the root is even then dp(sqrt(N)) < 0.5 whereas if it is odd then dp(sqrt(N)) >= 0.5. And, of course, if what you wanted was isqrt(N), there is no need to re-compute a root, just shift by one to the right the integer value isqrt(4N).

For instance, isqrt(4*7) = 5. Since 5 is odd, we know that the first digit of the decimal part of sqrt(7) is greater than or equal to 5 (and also that isqrt(7) = 5 >> 1 = 2). As a matter of fact, all this stuff is easy to understand with the binary representations of the numbers:
isqrt(4*7) --> 101
sqrt(7) --> 10.1xx...
jack is offline   Reply With Quote
Old 2013-09-10, 07:24   #16
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32·101 Posts
Default

Jack, I wasn't sure if you were advocating FP or not. At the end of my post I came to the same idea -- isqrt(4n), and then did the edit from ceil to floor after looking at the code and trying it out. I also noted it was a long winded way of arriving at your floor(2*sqrt(n)) suggestion. mpz_root(4*N) should give us the right number.
danaj is offline   Reply With Quote
Old 2022-07-07, 18:10   #17
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

2×3×433 Posts
Default

Is there a command line, parallel PRIMO certificate verifier available? WraithX's verifier doesn't support v4 certificates, and neither his or danaj's is parallel.

PRIMO will verify certificates quickly in parallel, but the GUI is a PITA for me to use. I have to use a couple tricks to forward the GUI from a cluster compute node, I can't seem to resize the window, and on my laptop the Load button on the bottom is below the bottom of the screen unless I muck with my screen resolution.
frmky is offline   Reply With Quote
Old 2022-07-07, 18:39   #18
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

101001011002 Posts
Default

The verification is quite well documented in the Primo executable's archive, it is named verifier-f4.txt. This is not directly a program, but maybe 80 % of it...?
kruoli is online now   Reply With Quote
Old 2022-12-22, 06:32   #19
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

259810 Posts
Default

Quote:
Originally Posted by frmky View Post
Is there a command line, parallel PRIMO certificate verifier available?
I made danaj's verifier parallel using OpenMP. I also disabled MPU certificate support in the process. (Ironic, perhaps, since it's a part of MPU, but there's little demand for a parallel MPU certificate verifier.) All of the verification steps remain intact but required numerous changes to remove global variables. It has been lightly tested on Primo v3 and v4 certificates so consider it a work in progress for now. Please let me know if you find a bug. Compile it with something like...
Code:
gcc -O3 -fopenmp -o vcertomp vcertomp.c -lgmp -lm
https://github.com/gchilders/Math-Pr...les/vcertomp.c
frmky is offline   Reply With Quote
Old 2022-12-22, 06:51   #20
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

32·1,231 Posts
Default

Quote:
Originally Posted by frmky View Post
I made danaj's verifier parallel using OpenMP. I also disabled MPU certificate support in the process. (Ironic, perhaps, since it's a part of MPU, but there's little demand for a parallel MPU certificate verifier.)
Excellent... 8^)
chalsall is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primo ET_ FactorDB 214 2022-11-16 15:36
Primo Browser? PawnProver44 Information & Answers 14 2016-04-09 05:49
factorDB verifier doesn't like my cert? schickel FactorDB 3 2015-08-09 17:21
PRIMO 3.0.7 Cybertronic Five or Bust - The Dual Sierpinski Problem 17 2009-08-13 20:42
primo question fivemack Math 35 2009-04-28 15:03

All times are UTC. The time now is 10:36.


Fri Feb 3 10:36:09 UTC 2023 up 169 days, 8:04, 1 user, load averages: 0.97, 0.81, 0.83

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

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