Cryptography Reference
In-Depth Information
Minimizing Extra State Any extra bits must be transported through
a separate channel at the end and so they should be kept to a
minimum. For that reason, all strings should be predefined as
constants. They can't be changed. If they could be changed,
then the final state of all strings would need to be shipped to
the recipient. This would be too much baggage.
Arithmetic Arithmetic is generally not reversible. 3+2 is not revers-
ible, but it can be reversed if one half of the equation is kept
around. So adding the contents of register
A 1 and register
A 2
and placing the result in register
A 1 is reversible. The contents
of
A 2
can be subtracted from
A 1
to recover the original value of
A 1
.
For the most part, addition, subtraction, multiplication, and
division are reversible if they're expressed in this format. The
only problem is multiplication by zero. This must be forbidden.
Structure of Memory What form will the memory take? Ordinary
computers allowprogrammers to grab and shift blocks of mem-
ory at a time. This is not feasible because it would require too
many extra waste bits would need to be stored. Block moves of
data are not reversible. Swaps of information are.
For that reason, there is an array of registers. Each one holds
one number that can be rounded off in some cases. The final
state of the registers will be shipped as extra state to the recipi-
ent so any programmer should aim to use them sparingly. Un-
fortunately, the rules of reversibility can make this difficult.
Conditional Statements Most conditional statements that choose
between branches of a program can be reversed, but some-
times they can't be. Consider the case that says, “If
x
is less than
100, then add 1 to
x
.Otherwise,add1to
p
.”Whichpathdoyou
take if you're running in reverse and
x
is 100? Do you subtract 1
from
p
or not? Either case is valid.
One solution is to execute each branch storing results in tem-
porary variables. When the conditional statement is encoun-
tered, the proper choices are swapped into place.
Another solution is to forbid the program to change the con-
tents of the variables that were used to choose a branch. This
rules out many standard programming idioms. Here's one way
to work around the problem:
Search WWH ::




Custom Search