トリップが循環することを証明せよ

任意のある文字列（８文字）をトリップキーとして入れたときに生じたトリップの
◆を除いた部分をまたトリップキーとして新たなトリップを作成する。

同様にしてこの過程を何度も繰り返すと、いつかは元のトリップキーが
トリップとして現れることを証明せよ。
また、これが成り立たないときは成り立たないことを証明せよ。

いやです

俺も嫌です。自分でやってください。

世知辛い世の中よのぉ・・・・

>>1
成り立たない。

>>5
理由を述べて下さい

>>6
zzzzzzzzにならない。

>>7
もう少し分かりやすくお願い

>>8
zzzzzzzzから始めればzzzzzzzzにならないので成り立たない。

>>9
なるほど。確かにそうですよね・・・

じゃあ、問題変えます。


全部で８文字で、最後の1文字を【.26AEIMQUYcgkosw】のどれかとする任意のある文字列を
トリップキーとして入れたときに生じたトリップの ◆を除いた部分をまたトリップキーとして
新たなトリップを作成する。

同様にしてこの過程を何度も繰り返すと、いつかは元のトリップキーが
トリップとして現れることを証明せよ。
また、これが成り立たないときは成り立たないことを証明せよ。

いやです

俺も嫌です。自分でやってください。

世知辛い世の中よのぉ・・・・

俺はトリップの仕組みしらんけど。
１の方法で次々に変換させて行った時、循環する部分集合はどんな感じなんだろね？
トリップの仕組みさえ分かればいいんだけど。

問題を出す人はその問題がそれだけの情報で解けるように、
不備が無いようにして問題を出すのが礼儀だけど思うけどなぁ…

そんな事もせずにいきなり自分の欲求だけ書いてくる奴が出てくるとは
本当に世知辛い世の中だね

&rlo;test

トリップ解析って本当に解析するんじゃなくて
例えて言うと、
f(x)=0という方程式を解くのに
xにいろいろな数を代入する方法に似てる。
１がだめなら２を、２がだめなら３をって具合にね。

天丼ﾜﾗﾀ

>>16
逆関数を求められれば楽しいんだが。

>>1-4>>10-13
みたいなのってなんで「天丼」って言うのかな

天丼ってなんだよｵｨ

>>20
同じギャグが忘れた頃にまた現れること。

でも本当に忘れられても拙い

「発生しうるトリップ」をキーにして生成させたトリップが
まったく重複しないならそのうち元に戻ってくる。
重複があるならその分生成できないトリップ
（すなわち循環しないトリップ）が存在する。

トリップ解析式を知らなくてもこのくらいの結論は出さないと。

【注意】その前に「発生しうるトリップ」の全集合を
念入りに確認すべきである。

４文字なら数分、５文字なら数時間、６文字なら数日かかる。
これらをｘ分、ｙ時間、ｚ日とした場合、ｘ、ｙ、ｚは２以上。
２≦ｘ＜６０
２≦ｙ＜２４
２≦ｚ
ｘ/６０：ｙ＝ｙ：２４ｚ
ｘｚ＝２．５ｙ＾２

ｙ＝２のとき　ｘｚ＝１０　　ｘ＝２のときｚ＝５
ｙ＝４のとき　ｘｚ＝４０　　ｘ＝２のときｚ＝２０
ｙ＝８のとき　ｘｚ＝１６０　ｘ＝２のときｚ＝８０
ｙ＝１６のときｘｚ＝６４０　ｘ＝２のときｚ＝３２０

６文字は、やめたほうがいいのか。

途中で局所的なループにならないことを証明しないといけないわけね？
そりゃきつそうだなぁ。cryptだもんね。
http://www.big.or.jp/~mio/ca/ca_old/pl/plscr/plcrypt.htm

cryptがどういう仕組みで暗号化してるのか教えて貰わないと恥ﾏﾗねぇぞ

最悪だ

この問題は数学板だけでは解決しないのではないだろうか
webprogあたりの人いる？

さっき帰ったよ。

放送で呼ぶ？

>>1よ。あなたの情報は不完全過ぎる。もっと提供しろ。情報を

>>1
前にやってみたがダメだった。
っていうかダメじゃなきゃ採用しないだろ。

>>32
何故。

>>33
こんなのが成り立ったら、余りにも単純すぎるからなんじゃない？

とりあえず実験してみようぜ。

　#1HaSine

からスタートしてみました。1000までに
　1HaSine
がトリップとして出るか試して見ませう。

次の方は名前のところに
　#fByuCO7s
を入れて下さい。

どれどれ

２回目

#3Sskg1oA
３回目

#rPnToHbg
sageでやれば？

#VvjDefjY
>>39
分かりました。

トリップの生成はハッシュで行っている
ハッシュは循環しない。
よってトリップは循環しない。
証明終わり。

>>41
あなたは人類の希望を打ち砕きました

ハッシュはある一定の長さを持つ文字列だけから決まる。
一定の長さの文字列は有限個しか存在しない。
よってハッシュを繰り返せば有限回で以前に現れたことがある
文字列が得られる。(ただし初期値に戻ってくる保証は無い)

>>35
トリップとして出てくるのは8文字だから
◆1HaSineは出てこないと思うけど…

最初の7文字が1HaSineってんなら出てくるかもね

#3w44ef/U

#Oa0KZNbE　　

#br7JFcDY　　　　　　　

#roL6zv/o　　　　　　　　　　　　　　

#lgoR.e9c　　　　　　

#7BYHdmCU

#7BYHdmCU

あれ？違ってるよ、、、

#7BYHdmCU

#RDdoNSjw

#mU9WSYvM

#algZp7KA

#1Pzn2AxA

ところで違うパスワードが同じトリップになることはありえるの？

#1HaSineから2000万個検索したが、
まったく循環は見つからんかったよ。
残念だったな。

数学板なんだから発生式から証明きぼん

有限桁の乱数は、どんなアルゴリズムを用いても、
循環すると思うけど？
２０００万個では少ないね。
６４進数で８桁なんだから、６４＾８＝約２８１．４７５兆通りだよ・・・

>>57
パスワードの組み合わせ総数にくらべて、
トリップの可能な文字列の組み合わせの方が少ないから、ありえる。
ラウンジのトリップスレで具体的に例があったような気がした。

…過去ログ掘り起こし中…

あった。
http://saki.2ch.net/entrance/kako/1003/10032/1003215929.html
の242

242 名前： 白い彗星 ◆7000000g 投稿日： 01/10/23 19:24 ID:???

SakuRau. : #(ghX:HBx
SakuRau. : #l$$｢ｾq`'
前にあったけどおんなじトリップで違うキー

同スレの250-261あたりも参考に。
組み合わせ総数とかトリップの生成式とか書いてある。

そうですねぇ・・・。ご意見は正解です。それを今井が認めます。

>>60の言うとおり循環を始めるのは明らか。
でも、この問題の本質は、一番最初に用いたキーが
その循環に含まれるかどうかだと思う。

つーか、#1HaSineからはじめたら、そのキーが循環に含まれないのは
明らかだし。文字数違うから。

文字数は関係ないだろ？
あくまで内部では固定桁数の２進数演算なんだから。
ちなみに、循環するか、最後にある値を無限回繰り返すか、の
２通りになる。

？？？じゃあ◆1HaSineが現れることもある？

最後にある値を無限回繰り返すのも循環の1種だよな。

>65 トリップで得られる文字列は必ず8桁ですよー
とりあえず◆ooooooooから10万回回して循環列がないか調べてみるわ。
途中でメモリが足りなくなるか19時になったらやめよう。

８桁と言っても、１桁は６４種類、つまり２進数の６ｂｉｔだから、
実質８桁＝４８ｂｉｔだろう・・・
２＾４８＝約２８１．４７５兆ね。

>>67
#1HaSineから2000万まわしても循環列はまったくなかったんで、
10万くらいじゃあみつからないかと。
でも、循環列があるのだけは確実なんだから、何か１つは見つけたいよねぇ。

ところで、cryptの解説をしてるサイトってどこかに無いですかね？
今のところ、JAVAに用意されたライブラリを使ってやってるんですけど、
ソース読むのが面倒で・・・。

なんだ、58さんはちゃんと途中の循環も見てたのか・・・無駄な時間を過ごした。
副産物のトリップでも付けとこ。

トリップが２８１兆通り有るのが解らんのか？（ｗ

>>71
誰に向かっていってるのかな？
ここにいる人は全員そんなことはわかってると思うよ。

>>70
ちゃんと途中の循環も調べましたよ〜。
おかげで、Celeron1.2GHzで1晩かかったよ。
あんまり高速化を考えずに作ったせいもあるけど。

プログラム公開してくれますか？
ウチのAthlon1.2GHzでよければ回します

１．大人には割れないけど子供には割れる
２．女にはきれいなのに男には汚い
３．犬には見えるのに猫にはなかなか見ることができない
４．車ならできるけど家では無理がある
５．天気の良い日には現れることもあるが　雨の日には見る　　ことができない
６．どちらかというと理科室より職員室の方が住みやすい
７．みんな触れたことがある
これらの問題にすべてあてはまる答えを教えてください。
答えは１つだそうです。

>>73
偶然で小さい循環が見つからないかと思ってやったんですけど、
どうやら見つかりそうに無いみたいなんで、実行してもあんまり意味無いと思うよ。

「無理っぽいのはわかってるけど、自分でも試してみたい。」
と言うことであれば、公開してもいいですけど。

もしかしてここの人達
トリップを解析できるんですか…

>>75
多分出来なさそうだけどウチのマシンが空いてるのでとりあえず回して見たら
運が良ければいけるかなと思って．
よければ公開してください．

import cryptix.tools.*;

class CryptTest {
static final int LOG_SIZE = 10000; //ログの大きさ
static final int LOG_INTERVAL = 1000; //ログに記録する間隔(初期値
static final int LOG_COMPRESS = 2; //ログ圧縮時の倍率

static String[] g_log = new String[LOG_SIZE];
static int g_logSize = 0;
static int g_logInterval = LOG_INTERVAL;
static int g_count = 0;

public static void main(String args[]){
String s1, s2;
String s = args[0];
for(;;){
UnixCrypt cr = new UnixCrypt(s.substring(1,3));
s1 = cr.crypt(s);
s2 = s1.substring(s1.length() - 8);
search(s2);
g_count++;
if(g_count == g_logInterval){
addLog(s2);
g_count = 0;
}
s = s2;
}
}

//ログに追加
static void addLog(String s){
System.out.println(s + " : " + g_logInterval + " * " + g_logSize);
g_log[g_logSize] = s;
g_logSize++;
if(g_logSize == LOG_SIZE){
logCompress(LOG_COMPRESS);
}
}
//ログの圧縮
static void logCompress(int c){
for(int i = 0 ; i < g_logSize / c ; i++){
g_log[i] = g_log[i * c];
}
g_logSize /= c;
g_logInterval *= c;
System.out.println("Compressed log : log interval = " + g_logInterval);
System.gc(); //なんとなく
}
//ログから検索
static boolean search(String s){
for(int i = 0 ; i < g_logSize ; i++){
if(s.equals(g_log[i])){
System.out.println("Congratulations !!" + s + " is looped");
System.out.println("log size : " + g_logSize);
System.out.println("log interval : " + g_logInterval);
System.out.println("i : " + i);
System.exit(0);
}
}
return false;
}
}

公開するって言ってしまったので、公開しますが、
これをコンパイルして実行できるような人なら、
このくらいのものはすぐに作れそうな気がする・・・。

cryptix3を使用していますので、
http://www.cryptix.org/
からDLしてclasspathを通してください。

つーか、このプログラムは、改善の余地ありまくりなので、
自分で作ったほうが早いかも。
とりあえず、
１. cryptixは処理に無駄がありすぎなので、自分で実装する。
(それができなければ、UnixCryptのインスタンスを必要な分、最初に
　全部作っておくだけでもかなりの効果があると思います）
２. Stringは処理に無駄がありすぎなので、char配列等に直す。
くらいはやったほうがいいと思います。

あと、自分のPCの環境に合わせて最初の定数の値を調節してください。

循環１つ発見しました。
これから確認作業をするので、それで間違いなければ、公表します。

確認しました。
S8cA3Pcgからはじめると周期2945022で循環します。
また、この循環の中に複数のキーから同じトリップが生成されるものが
存在することも確認しました。
これで、>>1および>>10は「偽」であることが証明されました。いじょ。

cryptってサーバーによって違くなんじゃなかった？

>>83それはSALTがサーバーごとに違うからです。
トリップはSALTをパスワードから生成するので、
常に同じになるのです。

すげー！遂に発見したのか・・・
ちょっと感動

>>82
え？
循環する列が存在するということの確認が、何故
>>1or>>10の命題が「偽」ということになるの？

>>86
ちょっと書き方が悪かったですね。すんません。

重要なのは循環列が存在することではなく、
複数のキーから同じトリップが生成されることなんですよ。
>>23に書いてあるとおりですね。

>>61にも例がありますが、この場合は（とか$とかが
含まれているので、これでは反例になりえないかな、と思いまして。

んで、今回循環列を求める過程でその反例が見事に見つかったので、
>>1と>>10が偽であることが証明できたわけです。

つーか、トリップは約７０兆通りっす。
トリップ８文字目は１６種類しか出ないので。

数学板らしく、問題にしてみまーす

・問題１
トリップの生成は、入力した値に対して出力される値が完全にランダムだと仮定して、
循環の周期Tの、(1)期待値、(2)分散、(3)偏差を求めよ。

・問題２
実際にトリップの循環を確認し、問題１と比較して、
循環という視点からcrypt暗号の精度を考察せよ。

1)
全トリップ数=n,T=kとなる確率をP(k)とすると、
P(k)=(1-1/n) * (1-2/n) * (1-3/n) * ... * (1-(k-1)/n) * 1/n
=(n-1)P(k-1)/n^k
期待値はΣ[k=1〜n](n-1)P(k-1)/n^(k-1)

入力したトリップがそのまま出るのってあるんか？

>>91
不動点はまだ見つかっていません

>>91
それ面白そうだな・・・

あぼーん

>>91
それくらいなら力技で見つかりそうですね。邪道ですが。
1秒に1万個は検索できるから、全部調べても1週間で終わります。

>>95
1万倍ほど甘く見積もってないかい？

不動点を見つける確率＝トリップをクラックする確率
ではないのか？

>>97
チョット違う。
不動点の場合はキーも6bit8文字なのに対し、
トリップのクラックは1文字当たり7bit　（だよね？
で、文字数も8文字とは限らない。

99 ﾓｷｬﾓｷｬ

げっと

あげてみる。
だれか>>89の問題2か>>91解ける人いない？
俺はギブアップだ。

不動点チェックなら検索プログラムに組み込んでもいいかもね

ていうか、検索プログラムでの総当り検索で
数学板の住人は納得してくれるのでしょうか？
それなら、プログラマー板とかでやれって感じのような
気がするんですが。

もしそれでもいいんなら、UDみたいなシステム作って、
分散して計算すれば割りと早く終わると思うよ。

crypt()の中身書いてあるのどっかにない？

age

なんだ、せっかくスレの杜で紹介されたのに
何でだれもいないんだ。

>>104
Linuxとかのソースコード
を読めばいいんじゃない？
http://www.criptix.com/
のcryptix3もソースつきだよ。

>>106
間違えた。
http://www.criptix.org/
だった。

>>106-107
http://www.cryptix.org/で合ってる？

とりあえず休日の暇つぶしにトリップの生成方法でも見てみる

>>108
あ、そうそう。それそれ。
2回連続で間違えた、打つ出し脳。

>>74

の答、何?

期待age

重複
http://kaba.2ch.net/test/read.cgi/stationery/1012891221/

>>9
> zzzzzzzzから始めればzzzzzzzzにならない

という反例の理由がわかりません。誰か教えてください。

>>113
>>1と>>10の違いを見ればわかるでしょ。

1と10は比較してみたのですが、わかりません。
最後の1文字を【.26AEIMQUYcgkosw】のどれかにしない場合は「明らかに」循環しない
ということのようですが、その理由がわからないのです。

zzzzzzzzから始めても途中から22222222から始まる小循環
に入る可能性だって十分あるよね

>>115
「循環しない」とは誰も言っていない。
１の条件では「成り立たない」と言っている。

>>115
１から全部ログを読み直せ

とりっぷってようするになんなのよ

初心者板に池

　　　　　　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　　　　　　｜誰｜
　　　　　　　　　　　　　　　　　｜も. |
　　　　　　　　　　　　　　　　　│来│
　　　　　　　　　　　　　　　　　│ね│
　　　　　　　　　　　　　　　　　│え |
　　　　　　　　　　　　　　　　　│よ .|
　　　　　　　　　　　　　　　　　│ !!.│
　　　　　　　　　　　　　　　　　└─┤　 　 ﾌﾟﾝﾌﾟﾝ
　　　　　　　　　　　　　　　　　　　　|　　　◎ ／　　 ⌒ヽ◎
　　　　　　　　　　　　　　　　　　　　|　　　　'　　ﾉノ)ﾉﾚﾉﾉ
　ﾄﾞｳｼﾀﾝﾀﾞﾖ　　ｻｸﾗ4ｶﾖ ?　　　　　| 　　　ｲ　イ　|　 |　|' 　ミ3
　　　　ヽ(`Д´)ﾉ　ヽ(`Д´)ﾉ　　(`Д´)ﾉ　　　 ﾍﾚゝ 〜／
　　　　|￣￣￣|─|￣￣￣|─|￣￣￣|─□（ ヽ┐U
〜 〜　￣◎￣　　.￣◎￣　　￣◎￣　　 ◎−>┘◎

　　　　　　　　　　ヽ(`Д´)ﾉ　ｵﾏｴﾗ ﾓｯﾄ ｶﾞﾝﾊﾞﾚﾖ!!
　　　　　　　　　　　 （　　）　　 ｳﾜｧｧﾝ!!
　　　　　　　　　　　　/　ヽ

そろそろ再開するか

>>78-79さん、JAVASCRIPTで書いて頂けませんでしょうか。

>>125
円周率ヲタ氏ね

今ある問題

89 名前：１３２人目の素数さん 投稿日：02/03/01 13:39
数学板らしく、問題にしてみまーす

・問題１
トリップの生成は、入力した値に対して出力される値が完全にランダムだと仮定して、
循環の周期Tの、(1)期待値、(2)分散、(3)偏差を求めよ。

・問題２
実際にトリップの循環を確認し、問題１と比較して、
循環という視点からcrypt暗号の精度を考察せよ。


91 名前：塾講師 ◆sBphv96s 投稿日：02/03/01 19:05
入力したトリップがそのまま出るのってあるんか？

【ローカルルール】
単発の質問はさくらスレへ。
学校の授業への不満は違うスレですること。
人の学校の悪口を言うなら学歴板でお相手します。
シモネタ・コピペはやめましょう。Googleに引っかかる恐れが増えます。
【ご注意】
自分の学校の進度が他より早いからといって自慢したり
するのは見苦しいです学歴板住人みんなで絡んで差し上げます。
みんなどんなことやってるんだろうな？とか
大学入ったらどんなことやるの？みたいな感じで
学生さんがたはマターリしましょう。
院生さまがたや社会人の皆様は過去を懐かしむような感じで
マターリしましょう。〜のころここら辺の理解で引っかかったなー
みたいなネタを提供してくださるとグッドです。

sharge

tendann世知辛い世の中よのぉ・・・・

　　　　　　あるネット関連会社の社長は、「いずれにしても2ちゃんねるは
資金が底をつけば終わり。あまり知られていないことだが、
2ちゃんねる内部関係者によると今、大手通信会社系が調査費名目で資金提供している。
だが、それが止まれば続けてはいけないだろう」と証言する。
2ちゃんねるが判決によって力を失った場合、資金提供の打ち切りも予想される。
http://ascii24.com/news/reading/causebooks/2002/07/01/636911-000.html

　以下、別の記事のキャッシュ http://memo2ch.tripod.co.jp/article.html
　2ちゃんねるに近いあるインターネット関連会社の社長は、2ちゃんねるの幹部から得
た話として証言する。「2ちゃんねるは、運営者や幹部などがそれぞれ別々に会社を
作りカネの流れを見え難くしているが、実際の資金源は複数の大手通信会社系からの
調査費名目のカネ。月額で計約700万円と言い、年間にすれば1億円近く。額はともあ
れ、これは通信会社系的には、ぼう大なトラフィックを調査すると言う表向きの理由
が一応は立つ。自社系に都合の悪い書き込みがされた時に優先的に削除してもらうこ
とも期待している」と前置きし「通信会社系の削除の期待も含めて、2ちゃんねるは
総会屋と同じになっている」と言うのだ。
　その具体的な理由として社長は、こう話す。「2ちゃんねるはボランティアの削除人
が書き込みをチェックして、好ましくない書き込みを一所懸命削除している、という
ことになっているが、あれはウソ。削除人には給料が支払われ、その給料の原資と
なっているのが、まずいことを書き込まれた企業が削除要求とともに渡す裏金。これ
はまさに、総会屋の構図そのものだ。これまで裁判になっているのは金額で折り合え
なかったり、裏金を出さない強い態度の企業とだけだ」

（＾＾）

実験しよう

ほしゅったらあげろ！