Let f(x) be the sum of all digits in integer x.
if f(x) % 3 = 0, then x % 3 = 0.
by itself isn't useful, since summing the digits is
expensive due to the atoi conversion.
Now, let y be a 299 digit number and z be any
number from 1 to 999999999 which ends in 1, 3, 6,
The client checks all numbers of the form c =
(10^10y + z) for the condition P % c = 0, where P is
the public key. It does so by finding the first such c
which is not divisible by 2, 3, 5 or 7, then
incrementing c by 2 until a succesful condition is met
or c > 999999999.
But , we know that every third candidate is a
composite number. (The proof is trivial : one of c,
c+2, c+4 must be divisible by three and then every 6
from then on).
With some precomputing it's possible to identify and
skip which "every third" to skip without calculating
Calculate f(y)%3. (only need to do this once per y.)
find the lowest z such that c=(10^10y+z) is not
divisible by 2, 5 or 7. If
f(y)%3 = 0, then d=c is a composite
f(y)%3 = 1, then d=c + 2 is a composite
f(y)%3 = 2, then d=c + 4 is a composite
The main loop then checks (d and d+2, _skips d+4_)
Now the question is if the savings are worth that
Note that this trick works for every 7th number if you
express everything in base 8 and every 11 in base 12
I _know_ there's a better way of expressing all this,
but it's late and I'm tired. I'm sure there are more
ways to skip even more candidates in the loop, but it's
on the tip of my brain. Need to sleep on it for a while.