Cryptography Reference
In-Depth Information
1101
101
1101 (1)
00000 (0)
110100 (1)
1000001
To reverse this, you have as input 100001 and 1101, and you want to recover
101. You can do this by subtracting and right-shifting:
1000001
(65)
110100
001101
(13 left shifted twice
13 * 2 2
13 * 4
52)
011010
(52 right-shifted once — do nothing)
001101
001101
(52 right-shifted twice — back to the original value of 13)
000000
If you just keep track of which iterations involved a subtraction — that is, which
right-shifts yielded a value less than the current value of the dividend — you
get “subtract” “nothing” “subtract” or, in binary, 101, which is exactly the value
you were looking for.
Of course, there's one immediate problem with implementing this: How do
you know to left-shift 13 twice before subtracting it? You could look at the bit-
length of the dividend — 65 in the example — and compare it to the bit-length
of the divisor (13), which tells you that you need to left-shift by two positions.
However, fi nding the bit-length of a value is somewhat non-trivial. An easier
(and faster) approach is just to keep left-shifting the divisor until it's greater
than the dividend.
Finally, you're doing integer division here — there's no compensation for
uneven division. So what happens if you divide 14 by, say, 5?
1100
1010
(5 left-shifted once)
0100
101
(do nothing, 5 > 4)
0100
Now you get a quotient of 10 (2) and the dividend, at the end of the operation,
is 4, which happens to be the remainder of the division of 14 by 5. Remember
Search WWH ::




Custom Search