Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Difference between revisions of "Gerbicz error checking"

From Prime-Wiki
Jump to: navigation, search
m (External links: Cleaning up link URLs)
(Cleaning up variables and prose)
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
'''Gerbicz error checking''' is a technique to verify validity of primality tests. It was proposed by Robert Gerbicz at [[MersenneForum]] in August 2017.
+
'''Gerbicz error checking''' is a technique to verify validity of primality tests. It was proposed by [[Robert Gerbicz]] at [[MersenneForum]] in August 2017.
  
Among [[GIMPS clients]], the technique is used to ensure validity of PRP tests for Mersenne numbers:
+
Among [[GIMPS clients]], the technique is used to ensure validity of PRP tests for [[Mersenne number]]s:
 
*in [[Prime95]] since version 29.4
 
*in [[Prime95]] since version 29.4
 
*in [[gpuOwL]].
 
*in [[gpuOwL]].
 +
 +
It is also used by [[LLR]] and [[LLR2]] to ensure validity of [[Proth prime|Proth]] tests and PRP tests on base-2 [[Riesel prime]] candidates, and by those programs and [[PRST]] in an extended version for PRP tests on additional number forms.
 +
 +
==Theory==
 +
The following describes the original formulation of the Gerbicz error check for [[Proth's theorem|Proth tests]], as described in [https://www.mersenneforum.org/showthread.php?t=22510 this MersenneForum thread]:
 +
 +
Let <math>p</math> be a Proth number, and let <math>k</math>, <math>n</math>, and <math>a</math> be defined as on [[Proth's theorem]], with <math>a</math> a [[quadratic residue|quadratic non-residue]] modulo <math>p</math>. Let <math>L</math> be a constant (originally defined as 2000, but described as possibly depending on <math>n</math>). We have the following equations:
 +
# <math>u(t) \equiv (a^k)^{2^t} \pmod{p}</math>
 +
# <math>d(t) \equiv \displaystyle\prod_{i=0}^t u(iL) \pmod{p}</math>
 +
# <math>d(t+1) \equiv d(t)*u((t+1)L) \pmod{p}</math>
 +
# <math>d(t+1) \equiv u(0)*d(t)^{2^L} \pmod{p}</math>
 +
 +
We store the following values (where <math>i</math> is the current iteration and <math>j = \lfloor i / L \rfloor</math>):
 +
# <math>d(j)</math> (for identity (3))
 +
# <math>u(0) \equiv a^k \pmod{p}</math>
 +
# <math>d(j - j \bmod L)</math>
 +
# <math>u(i - i \bmod L^2)</math>
 +
 +
Every <math>L</math> terms of the <math>d</math> sequence (i.e. every <math>L^2</math> iterations), we check identity (4). If this identity does not hold, then we roll back to the last stored <math>u</math> value (value (4) above). If we roll back too much (e.g. 100 times to the same term), then we just restart the computation completely.
 +
 +
For the last few squarings in <math>u</math>, we also force a computation of (4). This leaves all potential errors in the (at most) last <math>L</math> squarings in <math>u</math>, or very unlikely errors earlier in <math>u</math> or <math>d</math>.
 +
 +
The overhead is <math>n/L</math> [[Modular arithmetic#Modular multiplication|mulmods]] in (3) and <math>n / L^2 * L = n/L</math> [[Modular arithmetic#Modular exponentiation|squaremods]] and <math>n / L^2</math> mulmods in (4), so over the <math>n-1</math> mulmods of the Proth test, there are approximately <math>n/1000</math> mulmods, if we count everything in mulmods. Therefore, the overhead is 0.1% in time.
 +
 +
We could check all terms of <math>d</math>, but in that case the overhead in the error checking would be <math>n / L * (L+1) > n</math> mulmods, which is slightly more time what is spent on the Proth test squarings.
  
 
==See also==
 
==See also==
Line 11: Line 36:
 
*[https://www.mersenneforum.org/showthread.php?t=22510 Original proposal of the technique for Proth numbers]
 
*[https://www.mersenneforum.org/showthread.php?t=22510 Original proposal of the technique for Proth numbers]
 
*[https://www.mersenneforum.org/showthread.php?t=22471&p=465431 Original proposal of the technique for Mersenne numbers]
 
*[https://www.mersenneforum.org/showthread.php?t=22471&p=465431 Original proposal of the technique for Mersenne numbers]
[[Category:Math]]
+
 
 +
[[Category:Error checking]]

Latest revision as of 14:59, 3 October 2023

Gerbicz error checking is a technique to verify validity of primality tests. It was proposed by Robert Gerbicz at MersenneForum in August 2017.

Among GIMPS clients, the technique is used to ensure validity of PRP tests for Mersenne numbers:

It is also used by LLR and LLR2 to ensure validity of Proth tests and PRP tests on base-2 Riesel prime candidates, and by those programs and PRST in an extended version for PRP tests on additional number forms.

Theory

The following describes the original formulation of the Gerbicz error check for Proth tests, as described in this MersenneForum thread:

Let [math]\displaystyle{ p }[/math] be a Proth number, and let [math]\displaystyle{ k }[/math], [math]\displaystyle{ n }[/math], and [math]\displaystyle{ a }[/math] be defined as on Proth's theorem, with [math]\displaystyle{ a }[/math] a quadratic non-residue modulo [math]\displaystyle{ p }[/math]. Let [math]\displaystyle{ L }[/math] be a constant (originally defined as 2000, but described as possibly depending on [math]\displaystyle{ n }[/math]). We have the following equations:

  1. [math]\displaystyle{ u(t) \equiv (a^k)^{2^t} \pmod{p} }[/math]
  2. [math]\displaystyle{ d(t) \equiv \displaystyle\prod_{i=0}^t u(iL) \pmod{p} }[/math]
  3. [math]\displaystyle{ d(t+1) \equiv d(t)*u((t+1)L) \pmod{p} }[/math]
  4. [math]\displaystyle{ d(t+1) \equiv u(0)*d(t)^{2^L} \pmod{p} }[/math]

We store the following values (where [math]\displaystyle{ i }[/math] is the current iteration and [math]\displaystyle{ j = \lfloor i / L \rfloor }[/math]):

  1. [math]\displaystyle{ d(j) }[/math] (for identity (3))
  2. [math]\displaystyle{ u(0) \equiv a^k \pmod{p} }[/math]
  3. [math]\displaystyle{ d(j - j \bmod L) }[/math]
  4. [math]\displaystyle{ u(i - i \bmod L^2) }[/math]

Every [math]\displaystyle{ L }[/math] terms of the [math]\displaystyle{ d }[/math] sequence (i.e. every [math]\displaystyle{ L^2 }[/math] iterations), we check identity (4). If this identity does not hold, then we roll back to the last stored [math]\displaystyle{ u }[/math] value (value (4) above). If we roll back too much (e.g. 100 times to the same term), then we just restart the computation completely.

For the last few squarings in [math]\displaystyle{ u }[/math], we also force a computation of (4). This leaves all potential errors in the (at most) last [math]\displaystyle{ L }[/math] squarings in [math]\displaystyle{ u }[/math], or very unlikely errors earlier in [math]\displaystyle{ u }[/math] or [math]\displaystyle{ d }[/math].

The overhead is [math]\displaystyle{ n/L }[/math] mulmods in (3) and [math]\displaystyle{ n / L^2 * L = n/L }[/math] squaremods and [math]\displaystyle{ n / L^2 }[/math] mulmods in (4), so over the [math]\displaystyle{ n-1 }[/math] mulmods of the Proth test, there are approximately [math]\displaystyle{ n/1000 }[/math] mulmods, if we count everything in mulmods. Therefore, the overhead is 0.1% in time.

We could check all terms of [math]\displaystyle{ d }[/math], but in that case the overhead in the error checking would be [math]\displaystyle{ n / L * (L+1) \gt n }[/math] mulmods, which is slightly more time what is spent on the Proth test squarings.

See also

External links