Open make-github-pseudonymous-again opened 4 years ago
Let r be the radix of representation, then computing x % r^k-1 can be reduced using the following identity (with R = r^k):
r
x % r^k-1
R = r^k
x = x % R + x // R (mod R-1)
See https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test#Time_complexity
This also works for numbers of the form R-c:
R-c
Let x = hi * R + lo, then x = hi * (R-c) + c * hi + lo = c * hi + lo (mod R-c).
x = hi * R + lo
x = hi * (R-c) + c * hi + lo = c * hi + lo (mod R-c)
Let
r
be the radix of representation, then computingx % r^k-1
can be reduced using the following identity (withR = r^k
):See https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test#Time_complexity