From 4bfd864f10b68b71482b35c818559068ef8d5797 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Wed, 27 Nov 2024 20:54:24 +0100 Subject: doc: Add RFC documents --- doc/rfc/rfc70.txt | 507 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 507 insertions(+) create mode 100644 doc/rfc/rfc70.txt (limited to 'doc/rfc/rfc70.txt') diff --git a/doc/rfc/rfc70.txt b/doc/rfc/rfc70.txt new file mode 100644 index 0000000..9f4463b --- /dev/null +++ b/doc/rfc/rfc70.txt @@ -0,0 +1,507 @@ + + + + + + +Network Working Group S. Crocker +Request for Comments #70 UCLA + 15 October 70 + + 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....x10....0 + \__ __/\__ __/ + V V + n-k-1 k + +where 0<=k p' => +R(p) > R(p'), we obtain the following table of useful divisors for +p < 100. + + + + + + [Page 4] + +Network Working Group A Note on Padding RFC 70 + + + 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] + +Network Working Group A Note on Padding RFC 70 + + +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=q, + k q k-q + mod(2 ,p) = 2 *mod(2 ,p'). + + + + [Page 6] + +Network Working Group A Note on Padding RFC 70 + + +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] + +Network Working Group A Note on Padding RFC 70 + + +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] + +Network Working Group A Note on Padding RFC 70 + + +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 and ] + [ John Hewes 6/97 ] + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + [Page 9] + -- cgit v1.2.3