- 締切済み
2のn乗+1
nビットのハッシュ関数の出力は0から2のn乗の、合計すると2のn乗+1のパターンがあるってことで合ってますか？ それとも0から2のn乗-1で、合計2のn乗パターンですか？ もしくは0はなくて1から2のn乗までですか？ 実際の出力をみると0000……FA16みたいなケースもあるので、そうすると全部0という出力も有り得るのですか？ また最大値はn+1ビットも有り得るのですか？最大桁が1で残りが全て0とすると、2のn乗は2進数だと最大桁に1が来て、残りが全部0ですがその0の数は、n個になると思いますが、そうすると何々ビットのハッシュ関数といいつつ、最大値でみるとビット数は2のn乗+1となりますが、認識正しいでしょうか？
- nbitmaxmin
- お礼率100% (1/1)
- その他([技術者向] コンピューター)
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- kmee
- ベストアンサー率55% (1857/3366)
nビットで表現できるのは、最大2のn乗通りです。 2のn乗+1通りのパターンを表現するには、最低(n+1)ビット必要です。 例えば、 n=2で考えてください。 00 01 10 11 の4通りしかありません。 この4つで0～4の5通りをどうやって表現したらよいのでしょう? ですから > 合計すると2のn乗+1のパターンがある 「出力nビット」の場合は有り得ません。 関数内ではnビット超で計算している可能性はありますが、出力nビットなら、取り得る値は最大2のn乗通りです。 > 1から2のn乗までですか？ こちらは、最大2のn乗通りなので、nビットで表現できます。 ただし、一般的な10進⇔2進変換では対応できないので、工夫が必要です。 例えば、 n=2の1～4を対応させる場合。 00=1 01=2 10=3 11=4 と割り当てる、という方法が考えられます。 # 全部でnPn通りの割り当て方があります。 ですが、ハッシュで大切なのは「同じか、違うか」であって、具体的な値ではありません。 こんな面倒な割り当てをするより、素直に0～2のn乗-1を使った方が便利です。 > 全部0という出力も有り得るのですか？ ハッシュ関数の作り方次第です。 ・0を使わなければならない(2のn乗通り全てが出力されなればならない) ・0を使ってはならない(2のn乗通り全てが出力されてはならない) いずれの規則もありません。 > 最大桁が1で残りが全て0とする >その0の数は、n個になる 最大桁の「1」用の1桁 + 0のn桁 = n+1桁です。 nビットで 「最大桁が1で残りが全て0とする」となると 最大桁の「1」用の1桁 + 0の(n-1)桁 = n桁 です。
関連するQ&A
- ナンバーズ4の各桁の合計数がNのときの組み合わせの数
ナンバーズ4についての質問です。 ナンバーズ4の各桁を合計した値をNとします（0≦N≦36、Nは自然数） ⇒ナンバーズ4は0000～9999の中から数字を選択するため 各桁の合計値がNのときにナンバーズ4の組み合わせは 何パターンあるのか求める方法を教えてください。 例）N=0のときは0000の1パターン N=1のときは0001 0010 0100 1000の4パターン これを上記のようなアナログなやり方ではなく 数式で求めたいのです。 よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- ０の０乗＝１……かな？
０の０乗はいったい何なのかを考えていたら、ある本の中にあった、lim（ｎ→∞）ｎ＾1/n＝１の証明を見て少しひらめきました。 f(x)＝(1+x)^n－(1+nx) という関数はｘ＞０で微分可能ですから。 f'(x)＝n(1+x)^n-1－n＝n{(1+x)^n-1-1}＞０ である事がわかります。すると、f(0)=0であり、f(x)はｘ＞＝０で増加するから、ｘ＞０のときf(x)＞０で、つまり (1+x)^n＞(1+nx) ここで、ｘ＝1/√ｎとおくと (1+1/√n）^n＞1+√n＞√n この式の左辺と右辺を2n乗すると (1+1/√n）^2n＾2＞n^n ここでn＞１ならn^n＞１ですから (1+1/√n）^2n＾2＞n^n＞１ さらにlim（n→0)とすると (1+1/√n）^2n＾2→1 となり、n^nは1で両側から挟み撃ちにされるので lim(n→0)n^n＝1 つまり、０の０乗は１ってことにならないでしょうか。長々とした証明でした。読んでくださってありがとうございました。
- ベストアンサー
- 数学・算数
- 複素数のn乗について
a,bを整数、nを自然数として、 (a+bi)^n としたときに(iは虚数単位) a+biの絶対値をn乗すればよいのでしょうか？ つまり(a+bi)^n=(a^2+b^2)^nなのでしょうか？
- ベストアンサー
- 数学・算数
- パスワードの最良な決め方について(長文)
パスワードを最大限に複雑に決めたいとします。 当然、覚えられないので、適当な言葉で決めて、seedを付けてハッシュ関数へ入力し、出力をそのままパスワードとして使うとします。 （ハッシュ関数の出力は16進数ですが、文字数を少なくしたいので、使える文字を全て使用して、文字へ割り当てます。） seedは秘匿し、適当な言葉にあたる部分はブログ等に公開でもいいからメモっておくとします。 例えば、この質問サイト(OKWaveからログインしてます)であれば、 OKWavePassword_change#_0 といったような言葉を決めて、SNSのプロフに載っけておくとかです。 実際に使う際には、頭に(どこでもいいのですが)seedを付けて、 myseedOKWavePassword_change#_0 のようにして、ハッシュ値を取り、文字割り当てしてクリップボードへコピーして パスワード欄に貼り付けるかんじです。 ここからが質問です。 【質問１．ハッシュ関数はどれを使えば良いでしょうか？】 SHA-2シリーズはlength-extension攻撃に弱いので、HMACの形式にして使わなければならず、またその場合、Windowsのコマンドプロンプトで使える手軽な実装が見つからないのもあって(コマンドプロンプトにこだわる訳は要望があれば補足で説明したいと思います)、使用は避けたいです。 そこで、SHA-3シリーズが策定されてるようなので、この中で最大のビット数のものを選べば良いと思っていたのですが、Wikipediaを見たら、SHAKE128、同256というのがあり、読んでみると、 出力長を、任意に設定できる そうですが、だとすると、SHA-3の最大ビット数(SHA-3 512)と比べて、上述の使い方で考えると、どちらが良いでしょうか？ もしくは、他により良いハッシュ関数がありますか？ というのは、SHA-3 512では(というか、SHAKE以外のSHA-3では)出力長は固定なので、必要であれば(ほぼ全てのケースだと思いますが) そのパスワードで使用できる最大文字数にしなければならず、 その方法としては、文字割り当てまで終わってから、ただ単に頭から文字数分取るとか、間の文字を抜いて詰めるくらいしか思いつかないので、 それでどの程度、一様性が下がって(偏りが生じて)、危険になるかは、良く分からないのですが、 それであれば、512ビットより落ちる256ビットであるとしても、SHAKEであれば、ハッシュ値が得られた時点で過不足の少ない(0にはならないみたいですが、実装のせい？)情報量に収まっているので扱いやすいこともあり、いいかなと思っているのですが、どうでしょうか？ 要するに、512ビット固定長のハッシュ値を文字割り当てしてから(16進表現の時点では難しそうなので)、頭から一定の大きさまで削った場合と、 SHAKE256で最初から過不足の少ないハッシュ値を得て文字割り当てした場合とで、どちらがよりマシかということになると思いますが…… 例えば、例としてGmailのパスワードで考えると、確か、ASCII印字文字95種フルフルで使えて最長64文字だったと思いますが、 この場合だと512ビット固定長のがマシになりそうですが…… (512ビットを95進数表現すると78文字(桁)だから、78文字の先頭から文字を取るなり、間を詰めるなりして64文字にするほうが、256ビット分(95進数で39桁)を無理に引き伸ばすより安全そうというのが理由) ↑のようなパスワードを使うことが多ければ、というか多くなくても今後10年くらいは変えたくないので(SHA-1やSHA-2の寿命から;2はまだ死んでませんが)後々の事を考えればSHA-3 512で統一しておいたほうが結局無難でしょうか。 或いは、どっちもダメということもあるのでしょうか…… そもそも、ハッシュ関数を使うという考え方自体がダメだったりするのでしょうか…… 【質問２．仮にSHAKE256を使うとすると、出力長はどうやって求めれば良いでしょうか？】 例えば、OKWaveでは、パスワードの文字条件が、 使える文字がa～z, A～Z, 0～9, -, _で、文字数が最大10文字だそうですが、 この場合、パスワードの総パターン数を16進数で表した文字数にすればいいのでしょうか。 具体的には、総パターン数は64の10乗通りで1152921504606846976個、 16進数にすると1000000000000000で16文字で合ってますか？ また、多くの実装では、出力値が0起算のため、例えば今の例だと実際に取り得る値は 0～((64の10乗)-1) の範囲になるかと思いますが、つまり、 000000000000000～FFFFFFFFFFFFFFF が実際に出てくる値の最小～最大となるため、15文字で設定すれば良いということでしょうか？ 【質問３．具体的な例で確認したいのですが？】 SHAKE256で15文字として、seedはなしとすると、 OKWavePassword_change#_0 のハッシュ値は 911C7E7009C307 と出ましたが合ってますか。(HashSum使用←バイト単位でしか設定できないので、8byteだと文字割り当て後、11文字になるパターンが有り得るので7バイトで設定(1byteは16進数2文字)) またこれを64進数に変換すると、 02 17 07 07 57 48 02 28 12 07 になると思いますが合ってますか。 またこれを文字割り当て(ASCII文字コード表の通りの順番で、使用できる文字だけ拾って割り当て)すると、 1G66tk1RB6 となりましたが、合っているでしょうか。一応10文字にはなりましたが。 あと、HashSumがバイト単位の設定なので7バイトにしましたがこれだと9文字になるパターンも有り得ますよね。 その場合は10文字になるまで、入力値のOKWavePassword_change#_0の最後の0を1とか2とかに変えていけばいいかと思ってますが。 まぁそれ用に項目を置いてOKWavePassword_dummy#0_change#_0とかにしてこの場合dummy#の直後の数字を変えるという決めにするとかしとけば、パスワードを今まで何回変更したか知りたい(そんな要望あるのかはともかく)ときにゴッチャにならないで済むけど。 みたいな細かい問題は出てくると思いますが、このように柔軟に対応できると思っていますが、何か他に対応の難しい問題はありそうですか？ 【質問４．全体的にどうでしょうか？】 みたいな。 なんか結局、今まで考えていた通りにSHA-3 512でやっとけば良さそうな気がしてきましたが、全体通して総評ください。 以上、よろしくご回答の程、お願いいたします。
- 締切済み
- その他（ITシステム運用・管理）
- 複素数のn乗について2
前回の質問でよくわからない部分があったのでサイド質問させていただきます。 解説の抜粋なのですが、 z=a+bi (a,bは自然数 i は虚数単位） とし (a^2+b^2)^n=(|z|^2)^n=|z|^2n=(|z|^n)^2 というくだりがあるのですが、 a+biの絶対値の２乗はどうしてa^2+b^2になるのでしょうか？ 回答よろしくお願いします
- ベストアンサー
- 数学・算数
- ハッシュ関数
ハッシュ関数について悩んでいます． ハッシュ関数の例として以下Wikiの引用です http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0 unsigned int hash(char *s) { unsigned int h = 0; for (;*s != '\0'; s++) { h = h * 137 + *s; } return h % 1987; } このハッシュ関数において， 「hの更新計算で用いる137という数は、2(7乗)+2(3乗)+2(0乗) というものであり、乗法した後にも2進数表現の下位の桁にも 情報が残るようになっている。そのため前の方の文字の情報が 桁あふれによって失われることはない。」 と記述されているのですが，私が考えてしまうのは以下の通りです． 「最終的にハッシュ値は合計を1987で割った余りになるのだから， 下位の桁（1～1987）に情報を残さなければならない． それぞれのsの上位から下位までの情報を合計の数値の下位に 残すのであれば，137は掛けるのではなく割るべき．」 もちろん私の考え方が間違っているのはわかりますが， なぜ137を掛けるのかを理解できません． どなたかわかりやすくご教授いただけたら幸いです．
- ベストアンサー
- C・C++・C#
- １．自然数nの正の約数において、１を含み、nを含まない約数の総和がnに
１．自然数nの正の約数において、１を含み、nを含まない約数の総和がnに等しいとき、nを完全数という。 (1)２０および２８は完全数かどうか調べよ。 (2)p,qを互いに異なる素数として、n=pqとおく。nが完全数のとき、pをqを用いて表せ。 さらに、n=pqの形の完全数nを求めよ。 (3)pを素数として、n=p4乗とおく。このとき、どのような素数pに対してもnは完全数とはならないことを証明せよ。 ２．次の３直線l,m,nで囲まれる三角形の周および内部の領域をＤとおく。 l:3x-4y＋1=0 m:x-4y＋3=0 n:5x＋4y-33=0 (1) lとmの交点をA,mとnの交点をB,nとlの交点をCとおくとき、A,B,Cの座標を求めよ。 (2) 点(x,y)が領域Ｄ内の点であるとき、(x-3)2乗＋(y-1)2乗の最大値と最小値を求めよ。 また、最大値および最小値を与える点(x,y)も求めよ。 (3) 領域Ｄ内の点Ｐを中心とする半径１の円がある。点Ｐが領域Ｄ内のすべてを動くとき、円が通過する部分の面積を求めよ。 上記２問、どうしても解けません。 申し訳ありませんが、お助け下さい。
- 締切済み
- 数学・算数
- n進法についての問題です。
nを2以上の整数とした時 n進法で表されて4桁の数abcd(ｎ)のうちa=d≠０ b=cであるものを n進法の4桁回文とよぶ。 (1) 4進法の4桁回文全ての最大公約数を求めよ。 (2) n進法の4桁文は全てn＋1で割り切れる事を示せ。 ※宜しくお願いします。
- 締切済み
- 数学・算数
- 非同期型２のｎ乗カウンタ回路
観覧ありがとうございます。 質問は、 非同期型の２のn乗加カウンタにおいて、FFのクロック入力から出力が変化するまでの時間をtFとすると、正しい出力がまったく得られなくなる周波数はどのように表わされるか。 自分で調べてみましたが、わかりませんでした。 回答お願いします。
- ベストアンサー
- 物理学
お礼
何々ビットのハッシュ関数では、 2のn乗通りの区別が出来るということ、 0から2のn乗-1か、1から2のn乗かは、そのハッシュ関数の作り次第ということが理解できました。 回答ありがとうございました。
補足
先にお礼を書いてしまって、誤記してしまったので修正させてください。 >何々ビットのハッシュ関数では、 nビットのハッシュ関数では、 でした。