RFC70 日本語訳
0070 Note on Padding. S.D. Crocker. October 1970. (Format: TXT=12790 bytes) (Updated by RFC0228) (Status: UNKNOWN)
プログラムでの自動翻訳です。
RFC一覧
英語原文
Network Working Group S. Crocker Request for Comments #70 UCLA 15 October 70
コメント#70UCLA1970年10月15日を求めるネットワークワーキンググループS.医者要求
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.
メッセージにおける詰め物はフォーム10*のストリングです。語長16、32、48などがあるHosts、長い何ビットも、このストリングは必ずImpから受け取られた締め括りの言葉にあります。 16(しかし、長さ少なくとも16ビットである)の倍数でない語長があるHostsに関しては、1ビットが最後に言い表す締め括りの言葉か次のどちらかにあるでしょう。 もちろん、1ビットが最後に言い表す次にあるなら、締め括りの言葉はすべてゼロです。
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.
不快なコード化タスクは単語の中で1ビットのビット位置を発見することです。 1つの明白なテクニックは繰り返して下位のビットをテストすることです、まさしく1つが下位のビットがゼロであるなら位置に噛み付いたという単語を移行させて。 以下のテクニックは、より快いです。
Isolating the Low-Order Bit
下位のビットを隔離します。
Let W be a non-zero word, where the word length is n. Then W is of the form
Wが非ゼロ単語であることをさせてください。そこでは、語長がnです。 そして、Wはフォームのものです。
x....x10....0 \__ __/\__ __/ V V n-k-1 k
x.…x10…0 \__ __/\__ __/ V V n-k-1 k
where 0<=k<n
どこk0<=<n
and the x's are arbitrary bits.
そして、xのものは任意のビットです。
Assuming two's complement arithmetic,
2の補数演算を仮定します。
W-1 = x....x01....1 _ _ -W = x....x10....0 _ _ _ W = x....x01....1
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.
これらの量の様々な組と共にAND、OR、および排他的論理和を使用することによって、役に立つ新しいフォームを得ます。
For example,
例えば
[Page 1] Network Working Group A Note on Padding RFC 70
[1ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。
W AND W-1 xx...x00....0 \__ __/\__ __/ V V n-k-1 k
W AND W-1 xx…x00…0 \__ __/\__ __/ V V n-k-1 k
thus removing the low-order 1 bit;
その結果、下位を1ビット取り除きます。
also W AND -W = 0....010....0 __ __/__ __/ V V n-k-1 k
Wとも-W=0…010....0 __ __/__ __/V V n-k-1k
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
ビットが孤立しているビットの位置であることがわかるための2つの明白なテクニックは、繰返し上のテストで移行して、浮いている正常化ハードウェアを使用することです。 PDP-10では、*を命令するのをJFFO指示を特に、します。16進正常化、例えば、IBM360とXDS Sigmaのもの7があるマシンでは、正常化ハードウェアはそれほど便利でないかもしれません。 異なるアプローチは分割とテーブル索引を使用します。1ビットがオンのk A単語はk0<のための2の符号のない整数値がk<nとの等しさにします。 それぞれにおいて、私たちがpを選ぶのでモッズ(2、p)が異なるなら
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
0 k<=<n、私たちはモッズ(2、p)とkの間で通信を与える長さpのテーブルをkにすることができます。 紙が関するこの残り
the selection of an appropriate divisor p for each word length n.
各語長nのための適切な除数pの選択。
*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
*いくつかのCDCマシンには、kが一言で言えばビットの数を与える「人口カウント」指示があります。 2 -1をちょうどkビットを持っていることに注意してください。
on.
オン。
[Page 2] Network Working Group A Note on Padding RFC 70
[2ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。
Example
例
Let n = 8 and p = 11
nを8とp=11との等しさにしてください。
Then
その時
0
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
10 6 5 5 8 4 4 3 2 2 1 1モッズ(2、11)=モッズ(2、11)=モッズ(2、11)=モッズ(2、11)=モッズ(2、11)=モッズ(2、11)=モッズ(2、11)は9 7モッズ(2、11)=7と等しいです。
This yields a table of the form
これは形式のテーブルをもたらします。
remainder bit position
残りビット位置
0 --
0 --
1 0
1 0
2 1
2 1
3 --
3 --
4 2
4 2
5 4
5 4
6 --
6 --
7 7
7 7
8 3
8 3
9 6
9 6
10 5
10 5
[Page 3] Network Working Group A Note on Padding RFC 70
[3ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。
Good Divisors
良い除数
The divisor p should be as small as possible in order to minimize the
除数pができるだけわずかであるべきである、最小にする。
length of the table. Since the divisor must generate n distinct
テーブルの長さ。 以来に除数がnを発生させなければならない、異なる。
remainders, the divisor will certainly need to be at least n. A
確かに、残りであり、除数は、少なくとも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
しかしながら、ゼロの残りは除数がj2のパワーである場合にだけ起こることができます。 j<n-1のための2は、除数が2のわずかなパワーであるならそうすると言います。
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
n異なった残りを発生させてください。 除数がn-1n2の、より大きいパワーであるなら、通信テーブルは、長さが、2か2です。 私たちはそうすることができます。
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
語長より多くの最少の1つ。 事実上、このバウンドは達成されます。
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.
R(p)が2人の相次ぎより高い強国に分割されるとpが発生させる異なった残りの数であることをさせてください。 異なった残りは2人のR(p)の最も低い強国のためにすべて起こります。 変なpはおもしろいだけです、そして、以下のテーブルは変なpのためにR(p)に1と21の間与えます。
p R(p) p R(p)
p R(p)p R(p)
1 1 13 12
1 1 13 12
3 2 15 4
3 2 15 4
5 4 17 8
5 4 17 8
7 3 19 18
7 3 19 18
9 6 21 6
9 6 21 6
11 10
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.
より多くの異なった残りを発生させるよりわずかな除数があるので、このテーブルは、7、15、17、および21が役に立たない除数であることを示します。 '私たちの留意をそのようなp>R(p)そのp>p'=>R(p')に制限するなら、私たちは役に立つ除数の以下のテーブルをp<100に入手します。
[Page 4] Network Working Group A Note on Padding RFC 70
[4ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。
p R(p) p R(p)
p R(p)p R(p)
1 1 29 28
1 1 29 28
3 2 37 36
3 2 37 36
5 4 53 52
5 4 53 52
9 6 59 58
9 6 59 58
11 10 61 60
11 10 61 60
13 12 67 66
13 12 67 66
19 18 83 82
19 18 83 82
25 20
25 20
Notice that 9 and 25 are useful divisors even though they generate only 6 and 20 remainders, respectively.
それらは6と20残りだけをそれぞれ発生させますが、9と25が役に立つ除数であるのに注意してください。
Determination of R(p)
Rの決断(p)
If p is odd, the remainders
pが変であるなら残り
0
0
mod(2 ,p) 1 mod(2 ,p)
モッズ(2、p)1人のモッズ(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
… tは1とp-1の間で包括的になるでしょう。 2は、そこでは、k tが2の何らかのパワーで繰り返された残りになると言って、そうはいくらかのk<tのためのそれです、2 = 2 モッズp.t+1k+1Since2 = 2モッズp t+2k+2と2 = 2モッズp
. . . etc. 0 t-1 all of the distinct remainders occur for 2 ...2 . Therefore, R(p)=t.
…など 0 異なった残りのすべてが起こるt-1 2…2 . したがって、R(p)はtと等しいです。
[Page 5] Network Working Group A Note on Padding RFC 70
[5ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。
Next we show that
次に、私たちはそれを示しています。
R(p) 2 = 1 mod p R(p) k We already know that 2 = 2 mod p
R(p)2 = 1モッズp R(p)k Weは既にそんなに2 = 2にモッズpを知ります。
for some 0<=k<R(p). Let j=R(p)-k so 0<j<=R(p). Then
およそ0のために、<はk<R(p)と等しいです。 0<j<がR(p)と等しいようにj=R(p)-kをさせてください。 その時
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
pが変であるので2*2 = 2モッズp j kか(2 -1)*2 = 0モッズp k j k+j k2 = 2モッズp j k kか現在のpが2を割らないので、pは2 -1に分割されなければなりません。 このようにして
j 2 -1 = 0 mod p j 2 = 1 mod p
j2 -1 = 0モッズp j2 = 1モッズp
Since j is greater than 0 by hypothesis and since ther is no k other than 0 less than R(p) such that
仮説とther以来jが0以上である時から0を除いたkがないのがR(p)より少ないそのようなものである、それ
k 0 2 = 2 mod p,
k0 2 = 2モッズ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 私たちがj=R(p)を持たなければならない、その結果、さもなければ、モッズp.k Weはk=0、1に、変なpに関して、残りモッズ(2、p)がユニークであることを示しました…, R(p)-1とその時はまさに始めを繰り返します。
R(p) 2 = 1 mod p.
R(p)2 = 1モッズp。
We now consider even p. Let
私たちは現在、pさえ考えます。 貸されます。
q p = p'*2 , k k k where p' is odd. For k<q, mod(2 ,p) is clearly just 2 because 2 <p.
'q pはp'*2、p'が変であるk k kと等しいです。 k<qに関しては、モッズ(2、p)が明確にただ2歳である、2<p。
For k>=q, k q k-q mod(2 ,p) = 2 *mod(2 ,p').
'k>=qに関して、k q k-qモッズ(2、p)は2*モッズ(2、p')と等しいです。
[Page 6] Network Working Group A Note on Padding RFC 70
[6ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。
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
これから、私たちは、残りの系列には1、2のq-1の初期のセグメントがあるのを見ることができます…長さq、および2つの繰り返しているセグメント
length R(p'). Therefore, R(p) = q+R(p'). Since we normally expect
'の長さR(p')。 'したがって、R(p)はq+R(p')と等しいです。 以来、通常、私たちは予想します。
R(p) ~ p,
R(p)~p
even p generally will not be useful.
一般に、pは役に立ちさえしません。
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.
私は当然のことnのためのpを選ぶダイレクト方法を知りませんが、前のテーブルはUCLAで以下のFortranプログラム走行からSEXシステムの下で発生しました。
0
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
Fortranはコンピュータの役に立つ除数にプログラムを作ります。
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.
プログラム、公判中の撮影が評価するpのKでは、Nは連続した残りの値を呈します、そして、LはR(p)まで数えます、そして、Mは前の最も大きいR(p)を覚えています。 実行はかなり迅速です。
[Page 7] Network Working Group A Note on Padding RFC 70
[7ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。
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
R(p)が通常、書かれたオード川2であり、pであるので上と呼ばれた量は「2モッズpの注文」を読みました。 totientは、時々オード川2の最大値がpオイラーのオイラーのファイ関数によって与えられると呼びました。 aのtotient
positive integer p is the number of integers less than p which are
正の整数pはそうするpより少ない整数の数です。
relatively prime to p. The totient is easy to compute from a
pに比較的主要です。 totientはaから計算しやすいです。
representation of p as a product of primes:
盛りの製品としてのpの表現:
n n n Let p = p 1 * p 2 ... p k 1 2 k
n n n Let pはp1*p2…p k1 2kと等しいです。
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
pが異なった盛りであるところ。 次に、i k-1k-1k-1phi(p)は(p--1)*p1*(p--1)*p2と等しいです… (p--1) * p k1 1 2 2k k
If p is prime, the totient of p is simply
pが主要であるなら、pのtotientは単に主要です。
phi(p) = p-1.
phi(p)はp-1と等しいです。
If p is not prime, the totient is smaller.
pが主要でないなら、totientは、より小さいです。
If a is relatively prime to p, then Euler's generalization of Fermat's theorem states
aがp、フェルマーの定理州に関する当時のオイラーの一般化に比較的主要であるなら
phi(m) a = 1 mod p.
φ(m)aは1人のモッズpと等しいです。
It is this theorem which places an upper bound Ord 2, because Ord 2 is p p the smallest value such that
それが上限オード川2を置くこの定理であり、オード川2が最も小さくp pであるのでそのようなものを評価してください、それ
Ord 2 2 p = 1 mod p
オード川2 2pは1人のモッズpと等しいです。
Moreover it is always true that phi(p) is divisible by Ord 2. p
そのうえ、phi(p)がオード川2pで分割可能であることは、いつも本当です。
[Page 8] Network Working Group A Note on Padding RFC 70
[8ページ]ネットワーク作業部会はRFC70を水増しすることに関する注です。
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.
ボブ・カーンは、早めの草稿を読んで、博覧会を改良した多くのコメントをしました。 アレックス・ハーウィッツは、検索技術がR(p)を計算するのに必要であることを私に知らせて、私が発見した量と定理に名前を提供しました。
[ This RFC was put into machine readable form for entry ] [ into the online RFC archives by Guillaume Lahaye and ] [ John Hewes 6/97 ]
そして、[このRFCはエントリーのためのマシンに入れられた読み込み可能なフォームでした]、[ギヨームLahayeによるオンラインRFCアーカイブ、][ジョン・ヒューズ6/97]
[Page 9]
[9ページ]
一覧
スポンサーリンク