Let n be a binary number of 512 bytes. Given <a = n mod P> for some prime P. How can we calculate most efficiently < n' mod P> when n' is n without its MSB and added LSB (0 or 1) ?
Is there any special trick?
So this number can be as large as .
I'm not sure what rules the question designer intended; is the MSB allowed to equal 0? Does "without its LSB" mean a bit shift, or does it mean set the LSB to 0?
I think this thread (Post #7) as well as this Wikipedia article give some ideas but don't give a full answer to the problem. Would it be possible to find out more about the rules so that I don't spend time trying to answer the wrong problem?
Well if we know 000010010 'mod' P, then 000010011 'mod' P is easy because it's just the first result plus 1. (Unless the first result is P-1, then the second value is 0.)
Is it right to assume that occupies all 4096 bits? If so, then the MSB being 1 signifies a summand of . If not, it's not hard to adjust according to the location of the MSB.
But assuming all 4096 bits are necessary to store , then , if we let the new LSB = 0. So we want to find
In other words,
Depending on the size of , we can use Fermat's little theorem to reduce the size of the exponent 4096, and afterwards we can use fast exponentiation as described in my first post. If p > 4097, then I believe it will take steps to get , just by successively squaring the current result. But if you're doing this operation a lot, you can store the value(s) in a table.
Does all this seem reasonable to you?
(Edit: Added the part in green for correctness, since we need common residue.)