#5 Possible optimization

[Anonymous]

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,
or 9.

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
P%c.

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_)
and repeats.

Now the question is if the savings are worth that
pesky f(y)%3.

Note that this trick works for every 7th number if you
express everything in base 8 and every 11 in base 12
etc.

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.

[PDG1]

Logged In: YES
user_id=1076107

that actually sounds pretty good
however, it's been like... 3 years since you posted this..
maybe they're dead