Primo Verifier... - Page 2

jack · 2013-09-09, 17:05

Quote:

Originally Posted by WraithX

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 · 2013-09-09, 19:40

Quote:

Originally Posted by jack

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.

danaj · 2013-09-09, 22:36

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

jack · 2013-09-10, 05:13

Quote:

Originally Posted by danaj

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

danaj · 2013-09-10, 07:24

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.

2013-09-09, 22:36	#14
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 1110001100₂ Posts	Two independently written ECPP implementations generated similar M (RS) 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 2ceil(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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Primo	ET_	FactorDB	163	2021-06-02 09:14
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

2013-09-10, 07:24	#16
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 38C₁₆ 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(2sqrt(n)) suggestion. mpz_root(4N) should give us the right number.