A Note on Padding
- The padding on a message is a string of the form 10*. For Hosts with
-
- word lengths 16, 32, 48, etc., bits long, this string is necessarily in
-
- the last word received from the Imp. For Hosts with word lengths which
-
- are not a multiple of 16 (but which are at least 16 bits long), the 1
-
- bit will be in either the last word or the next to last word. Of
-
- course if the 1 bit is in the next to last word, the last word is all
-
- zero.
-
- An unpleasant coding task is discovering the bit position of the 1 bit
-
- within its word. One obvious technique is to repeatedly test the
-
- low-order bit, shifting the word right one bit position if the
-
- low-order bit is zero. The following techniques are more pleasant.
-
- Isolating the Low-Order Bit
-
- Let W be a non-zero word, where the word length is n. Then W is of the
-
- form
-
x
\__ __/\__ __/
V V
n-k-1 k
- where 0<=k<n
-
- and the x's are arbitrary bits.
-
- Assuming two's complement arithmetic,
-
W-1 = x....x01....1
_ _
-W = x....x10....0
_ _ _
W = x....x01....1
- By using AND, OR and exclusive OR with various pairs of these
-
- quantities, useful new forms are obtained.
-
- For example,
-
[Page 1]
-
W AND W-1 xx...x00....0
\__ __/\__ __/
V V
n-k-1 k
- thus removing the low-order 1 bit;
-
also W AND -W = 0
__ __/__ __/
V V
n-k-1 k
- thus isolating the low-order bit.
-
- Below, we will focus solely on this last result; however, in a
-
- particular application it may be advantageous to use a variation.
-
- Determining the Position of an Isolated Bit
-
- The two obvious techniques for finding the bit position of an isolated
-
- bit are to shift repetitively with tests, as above, and to use floating
-
- normalization hardware. On the PDP-10, in particular, the JFFO
-
- instruction is made to order*. On machines with hexadecimal
-
- normalization, e.g. IBM 360's and XDS Sigma 7's, the normalization
-
- hardware may not be very convenient. A different approach uses
-
- division and table look-up.
-
k
- A word with a single bit on has an unsigned integer value of 2 for
-
k
- 0<=k<n. If we choose a p such that mod(2 ,p) is distinct for each
-
- 0<=k<n, we can make a table of length p which gives the correspondence
-
k
- between mod(2 ,p) and k. The remainder of this paper is concerned with
-
- the selection of an appropriate divisor p for each word length n.
-
- *Some of the CDC machines have a "population count" instruction which
-
k
- gives the number of bits in a word. Note the 2 -1 has exactly k bits
-
- on.
-
[Page 2]
-
- Example
-
Let n = 8 and p = 11
Then
0
mod(2, 11) = 1
1
mod(2, 11) = 2
2
mod(2, 11) = 4
3
mod(2, 11) = 8
4
mod(2, 11) = 5
5
mod(2, 11) = 10
6
mod(2, 11) = 9
7
mod(2, 11) = 7
This yields a table of the form
remainder bit position
0 --
1 0
2 1
3 --
4 2
5 4
6 --
7 7
8 3
9 6
10 5
[Page 3]
-
- Good Divisors
-
- The divisor p should be as small as possible in order to minimize the
-
- length of the table. Since the divisor must generate n distinct
-
- remainders, the divisor will certainly need to be at least n. A
-
- remainder of zero, however, can occur only if the divisor is a power of
-
j
- 2. If the divisor is a small power of 2, say 2 for j < n-1, it will
-
- not generate n distinct remainders; if the divisor is a larger power of
-
n-1 n
2, the correspondence table is either 2 or 2 in length. We can
- thus rule out zero as a remainder value, so the divisor must be at
-
- least one more than the word length. This bound is in fact achieved
-
- for some word lengths.
-
- Let R(p) be the number of distinct remainders p generates when divided
-
- into successively higher powers of 2. The distinct remainders all occur
-
- for the R(p) lowest powers of 2. Only odd p are interesting and the
-
- following table gives R(p) for odd p between 1 and 21.
-
p R(p) p R(p)
1 1 13 12
3 2 15 4
5 4 17 8
7 3 19 18
9 6 21 6
11 10
- This table shows that 7, 15, 17 and 21 are useless divisors because
-
- there are smaller divisors which generate a larger number of distinct
-
- remainders. If we limit our attention to p such that p > p' =>
-
- R(p) > R(p'), we obtain the following table of useful divisors for
-
- p < 100.
-
[Page 4]
-
p R(p) p R(p)
1 1 29 28
3 2 37 36
5 4 53 52
9 6 59 58
11 10 61 60
13 12 67 66
19 18 83 82
25 20
- Notice that 9 and 25 are useful divisors even though they generate only
-
- 6 and 20 remainders, respectively.
-
- Determination of R(p)
-
- If p is odd, the remainders
-
0
mod(2 ,p)
1
mod(2 ,p)
.
.
.
t
- will be between 1 and p-1 inclusive. At some power of 2, say 2 , there
-
k t
- will be a repeated remainder, so that for some k < t, 2 = 2 mod p.
-
t+1 k+1
Since 2 = 2 mod p
t+2 k+2
and 2 = 2 mod p
.
.
.
etc.
0 t-1
all of the distinct remainders occur for 2 ...2 . Therefore, R(p)=t.
[Page 5]
-
- Next we show that
-
R(p)
2 = 1 mod p
R(p) k
We already know that 2 = 2 mod p
- for some 0<=k<R(p). Let j=R(p)-k so 0<j<=R(p). Then
-
k+j k
2 = 2 mod p
j k k
or 2 *2 = 2 mod p
j k
or (2 -1)*2 = 0 mod p
k j
- Now p does not divide 2 because p is odd, so p must divide 2 -1. Thus
-
j
2 -1 = 0 mod p
j
2 = 1 mod p
- Since j is greater than 0 by hypothesis and since ther is no k other
-
- than 0 less than R(p) such that
-
k 0
2 = 2 mod p,
R(p)
- we must have j=R(p), or 2 = 1 mod p.
-
k
- We have thus shown that for odd p, the remainders mod(2 ,p) are unique
-
- for k = 0, 1,..., R(p)-1 and then repeat exactly, beginning with
-
R(p)
2 = 1 mod p.
- We now consider even p. Let
-
q
p = p'*2 ,
k k k
- where p' is odd. For k<q, mod(2 ,p) is clearly just 2 because 2 <p.
-
- For k>=q,
-
k q k-q
mod(2 ,p) = 2 *mod(2 ,p').
[Page 6]
-
- From this we can see that the sequence of remainders will have an
-
q-1
- initial segment of 1, 2, ...2 of length q, and repeating segments of
-
- length R(p'). Therefore, R(p) = q+R(p'). Since we normally expect
-
R(p) ~ p,
- even p generally will not be useful.
-
- I don't know of a direct way of choosing a p for a given n, but the
-
- previous table was generated from the following Fortran program run
-
- under the SEX system at UCLA.
-
0
CALL IASSGN('OC ',56)
1 FORMAT(I3,I5)
M=0
DO 100 K=1,100,2
K=1
L=0
20 L=L+1
N=MOD(2*N,K)
IF(N.GT.1) GO TO 20
IF(L.LE.M) GO TO 100
M=L
WRITE(56,1)K,L
100 CONTINUE
STOP
END
Fortran program to computer useful divisors
- In the program, K takes on trial values of p, N takes on the values of
-
- the successive remainders, L counts up to R(p), and M remembers the
-
- previous largest R(p). Execution is quite speedy.
-
[Page 7]
-
- Results from Number Theory
-
- The quantity referred to above as R(p) is usually written Ord 2 and is
-
p
- read "the order of 2 mod p". The maximum value of Ord 2 is given by
-
p
- Euler's phi-function, sometimes called the totient. The totient of a
-
- positive integer p is the number of integers less than p which are
-
- relatively prime to p. The totient is easy to compute from a
-
- representation of p as a product of primes:
-
n n n
Let p = p 1 * p 2 ... p k
1 2 k
- where the p are distinct primes. Then
-
i
k -1 k -1 k -1
phi(p) = (p - 1) * p 1 * (p - 1) * p 2 ... (p - 1) * p k
1 1 2 2 k k
- If p is prime, the totient of p is simply
-
phi(p) = p-1.
- If p is not prime, the totient is smaller.
-
- If a is relatively prime to p, then Euler's generalization of Fermat's
-
- theorem states
-
phi(m)
a = 1 mod p.
- It is this theorem which places an upper bound Ord 2, because Ord 2 is
-
p p
- the smallest value such that
-
Ord 2
2 p = 1 mod p
- Moreover it is always true that phi(p) is divisible by Ord 2.
-
p
[Page 8]
-
- Acknowledgements
-
- Bob Kahn read an early draft and made many comments which improved the
-
- exposition. Alex Hurwitz assured me that a search technique is
-
- necessary to compute R(p), and supplied the names for the quantities
-
- and theorems I uncovered.
-
[ This RFC was put into machine readable form for entry ]
[ into the online RFC archives by Guillaume Lahaye 6/97 ]
[Page 9]
-