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?
512 bytes = 4096 bits
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?
In what's below, when I use single quotes for 'mod,' I mean the operator that returns the common residue. Without single quotes, mod is used in the usual way for math textbooks.
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.)