A C++14-compatible physical units library with no dependencies and a single-file delivery option. Emphasis on safety, accessibility, performance, and developer experience.
The Baillie-PSW is the star of the show: it's fully deterministic for
all 64-bit integers, and there are no known counterexamples of any size.
In order to reach it, we need to combine the existing Miller-Rabin test
with a Strong Lucas test, the latter of which is the "hard work" part
of this PR.
The first step is to find the right value of the "D" parameter to use:
the first from the sequence {5, -7, 9, -11, ...} whose Jacobi symbol
(see parent PR) is -1. We represent this as an uint64_t-and-bool
struct, rather than a simple int, for two reasons. First, it's easier
to write this incrementing/alternating pattern with a separate sign.
Second, when we use D.mag in calculations, it's convenient if it's
already a uint64_t like almost all of the rest of our types.
Oh --- and, this step won't work if n is a perfect square, so we add a
separate guarding step to filter this situation out.
Now for the meat of the calculation. We need to compute elements of the
Lucas Sequences, $U_k$ and $V_k$ for certain specific indices. To do
that efficiently, we use the fact that $U_1 = V_1 = 1$, and apply the
index-doubling and index-incrementing relations:
The above are derived assuming the Lucas parameters $P=1$, $Q=(1-D)/4$,
as is always done for the best-studied parameterization of Baillie-PSW.
We use a bit-representation of the desired indices to decide when to
double and when to increment, also commonly done (see the Implementation
section in the Strong Lucas reference).
Finally, we are able to combine the new Strong Lucas test with the
existing Miller-Rabin test to obtain a working Baillie-PSW test.
We use the same kinds of verification strategies for Strong Lucas and
Baillie-PSW as we used for Miller-Rabin, except that we don't test
pseudoprimes for Baillie-PSW because nobody has ever found any yet.
The Baillie-PSW is the star of the show: it's fully deterministic for all 64-bit integers, and there are no known counterexamples of any size. In order to reach it, we need to combine the existing Miller-Rabin test with a Strong Lucas test, the latter of which is the "hard work" part of this PR.
The first step is to find the right value of the "D" parameter to use: the first from the sequence {5, -7, 9, -11, ...} whose Jacobi symbol (see parent PR) is -1. We represent this as an
uint64_t-and-boolstruct, rather than a simpleint, for two reasons. First, it's easier to write this incrementing/alternating pattern with a separate sign. Second, when we useD.magin calculations, it's convenient if it's already auint64_tlike almost all of the rest of our types.Oh --- and, this step won't work if
nis a perfect square, so we add a separate guarding step to filter this situation out.Now for the meat of the calculation. We need to compute elements of the Lucas Sequences, $U_k$ and $V_k$ for certain specific indices. To do that efficiently, we use the fact that $U_1 = V_1 = 1$, and apply the index-doubling and index-incrementing relations:
The above are derived assuming the Lucas parameters $P=1$, $Q=(1-D)/4$, as is always done for the best-studied parameterization of Baillie-PSW. We use a bit-representation of the desired indices to decide when to double and when to increment, also commonly done (see the Implementation section in the Strong Lucas reference).
Finally, we are able to combine the new Strong Lucas test with the existing Miller-Rabin test to obtain a working Baillie-PSW test.
We use the same kinds of verification strategies for Strong Lucas and Baillie-PSW as we used for Miller-Rabin, except that we don't test pseudoprimes for Baillie-PSW because nobody has ever found any yet.
Helps #217.