20130909, 17:05  #12  
Jul 2013
3 Posts 
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:


20130909, 19:40  #13 
Jul 2013
3 Posts 
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.

20130909, 22:36  #14 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}×101 Posts 
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 20130909 at 23:04 
20130910, 05:13  #15 
Jul 2013
11_{2} Posts 
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 recompute 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... 
20130910, 07:24  #16 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}·101 Posts 
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.

20220707, 18:10  #17 
Jul 2003
So Cal
2×3×433 Posts 
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. 
20220707, 18:39  #18 
"Oliver"
Sep 2017
Porta Westfalica, DE
10100101100_{2} Posts 
The verification is quite well documented in the Primo executable's archive, it is named verifierf4.txt. This is not directly a program, but maybe 80 % of it...?

20221222, 06:32  #19  
Jul 2003
So Cal
2598_{10} Posts 
Quote:
Code:
gcc O3 fopenmp o vcertomp vcertomp.c lgmp lm 

20221222, 06:51  #20 
If I May
"Chris Halsall"
Sep 2002
Barbados
3^{2}·1,231 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primo  ET_  FactorDB  214  20221116 15:36 
Primo Browser?  PawnProver44  Information & Answers  14  20160409 05:49 
factorDB verifier doesn't like my cert?  schickel  FactorDB  3  20150809 17:21 
PRIMO 3.0.7  Cybertronic  Five or Bust  The Dual Sierpinski Problem  17  20090813 20:42 
primo question  fivemack  Math  35  20090428 15:03 