Comment by marshray

Suggestion: Forget the modulus and remainder trick and just use a cryptographically strong MAC to decide what to ignore and what to process. Even a truncated HMAC.