2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

1 :132人目の素数さん:02/01/10 02:14
任意のある文字列(8文字)をトリップキーとして入れたときに生じたトリップの
◆を除いた部分をまたトリップキーとして新たなトリップを作成する。

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

2 :132人目の素数さん:02/01/10 02:18
いやです

3 :132人目の素数さん:02/01/10 02:20
俺も嫌です。自分でやってください。

4 ::02/01/10 02:21
世知辛い世の中よのぉ・・・・

5 :132人目の素数さん:02/01/10 02:30
>>1
成り立たない。

6 ::02/01/10 02:31
>>5
理由を述べて下さい

7 :132人目の素数さん:02/01/10 02:32
>>6
zzzzzzzzにならない。

8 ::02/01/10 02:36
>>7
もう少し分かりやすくお願い

9 :132人目の素数さん:02/01/10 02:40
>>8
zzzzzzzzから始めればzzzzzzzzにならないので成り立たない。

10 ::02/01/10 02:49
>>9
なるほど。確かにそうですよね・・・

じゃあ、問題変えます。


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

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

11 :132人目の素数さん:02/01/10 02:52
いやです

12 :132人目の素数さん:02/01/10 02:54
俺も嫌です。自分でやってください。

13 ::02/01/10 02:54
世知辛い世の中よのぉ・・・・

14 :132人目の素数さん:02/01/10 03:16
俺はトリップの仕組みしらんけど。
1の方法で次々に変換させて行った時、循環する部分集合はどんな感じなんだろね?
トリップの仕組みさえ分かればいいんだけど。

15 :132人目の素数さん:02/01/10 18:56
問題を出す人はその問題がそれだけの情報で解けるように、
不備が無いようにして問題を出すのが礼儀だけど思うけどなぁ…

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

16 :132人目の素数さん:02/01/10 20:02
&rlo;test

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

17 :132人目の素数さん:02/01/10 20:11
天丼ワラタ

18 :132人目の素数さん:02/01/10 20:19
>>16
逆関数を求められれば楽しいんだが。

19 :132人目の素数さん:02/01/10 20:27
>>1-4>>10-13
みたいなのってなんで「天丼」って言うのかな

20 :132人目の素数さん:02/01/10 20:59
天丼ってなんだよオィ

21 :132人目の素数さん:02/01/10 21:01
>>20
同じギャグが忘れた頃にまた現れること。

22 :132人目の素数さん:02/01/10 21:05
でも本当に忘れられても拙い

23 :132人目の素数さん:02/01/10 22:01
「発生しうるトリップ」をキーにして生成させたトリップが
まったく重複しないならそのうち元に戻ってくる。
重複があるならその分生成できないトリップ
(すなわち循環しないトリップ)が存在する。

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

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

24 :名無しの歌が聞こえてくるよ♪:02/01/10 23:25
4文字なら数分、5文字なら数時間、6文字なら数日かかる。
これらをx分、y時間、z日とした場合、x、y、zは2以上。
2≦x<60
2≦y<24
2≦z
x/60:y=y:24z
xz=2.5y^2

y=2のとき xz=10  x=2のときz=5
y=4のとき xz=40  x=2のときz=20
y=8のとき xz=160 x=2のときz=80
y=16のときxz=640 x=2のときz=320

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

25 :132人目の素数さん:02/01/10 23:43
途中で局所的なループにならないことを証明しないといけないわけね?
そりゃきつそうだなぁ。cryptだもんね。
http://www.big.or.jp/~mio/ca/ca_old/pl/plscr/plcrypt.htm

26 :132人目の素数さん:02/01/11 00:27
cryptがどういう仕組みで暗号化してるのか教えて貰わないと恥マラねぇぞ

27 :132人目の素数さん:02/01/11 00:27
最悪だ

28 :132人目の素数さん:02/01/11 00:42
この問題は数学板だけでは解決しないのではないだろうか
webprogあたりの人いる?

29 :132人目の素数さん:02/01/11 00:57
さっき帰ったよ。

30 :132人目の素数さん:02/01/11 01:50
放送で呼ぶ?

31 :132人目の素数さん:02/01/11 20:36
>>1よ。あなたの情報は不完全過ぎる。もっと提供しろ。情報を

32 :132人目の素数さん:02/01/11 20:39
>>1
前にやってみたがダメだった。
っていうかダメじゃなきゃ採用しないだろ。

33 :132人目の素数さん:02/01/12 01:50
>>32
何故。

34 :132人目の素数さん:02/01/13 05:58
>>33
こんなのが成り立ったら、余りにも単純すぎるからなんじゃない?

35 : ◆fByuCO7s :02/01/14 07:20
とりあえず実験してみようぜ。

 #1HaSine

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

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

36 : ◆sO.1NZVY :02/01/14 13:25
どれどれ

37 : ◆3Sskg1oA :02/01/14 13:26
2回目

38 : ◆rPnToHbg :02/01/14 13:26
#3Sskg1oA
3回目

39 : ◆VvjDefjY :02/01/14 13:34
#rPnToHbg
sageでやれば?

40 : ◆3w44ef/U :02/01/14 13:38
#VvjDefjY
>>39
分かりました。

41 :132人目の素数さん:02/01/14 14:22
トリップの生成はハッシュで行っている
ハッシュは循環しない。
よってトリップは循環しない。
証明終わり。

42 :132人目の素数さん:02/01/14 14:44
>>41
あなたは人類の希望を打ち砕きました

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

44 :132人目の素数さん:02/01/17 21:43
>>35
トリップとして出てくるのは8文字だから
◆1HaSineは出てこないと思うけど…

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

45 : ◆Oa0KZNbE :02/01/20 11:55
#3w44ef/U

46 : ◆br7JFcDY :02/01/20 11:56
#Oa0KZNbE  

47 : ◆roL6zv/o :02/01/20 11:56
#br7JFcDY       

48 : ◆lgoR.e9c :02/01/20 11:57
#roL6zv/o              

49 : ◆7BYHdmCU :02/01/20 11:57
#lgoR.e9c      

50 : ◆RDdoNSjw :02/02/27 21:19
#7BYHdmCU

51 : ◆mU9WSYvM :02/02/27 23:31
#7BYHdmCU

52 :51:02/02/27 23:32
あれ?違ってるよ、、、

53 : ◆mU9WSYvM :02/02/27 23:55
#7BYHdmCU

54 : ◆4l/dypLk :02/02/28 01:00
#RDdoNSjw

55 : ◆algZp7KA :02/02/28 01:02
#mU9WSYvM

56 : ◆1Pzn2AxA :02/02/28 01:34
#algZp7KA

57 : ◆hN/LtuoM :02/02/28 02:48
#1Pzn2AxA

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

58 :132人目の素数さん:02/02/28 12:03
#1HaSineから2000万個検索したが、
まったく循環は見つからんかったよ。
残念だったな。

59 :132人目の素数さん:02/02/28 12:41
数学板なんだから発生式から証明きぼん

60 :132人目の素数さん:02/02/28 13:18
有限桁の乱数は、どんなアルゴリズムを用いても、
循環すると思うけど?
2000万個では少ないね。
64進数で8桁なんだから、64^8=約281.475兆通りだよ・・・

61 :132人目の素数さん:02/02/28 13:29
>>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`'
前にあったけどおんなじトリップで違うキー

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

63 :今井弘一:02/02/28 13:38
そうですねぇ・・・。ご意見は正解です。それを今井が認めます。


64 :132人目の素数さん:02/02/28 13:49
>>60の言うとおり循環を始めるのは明らか。
でも、この問題の本質は、一番最初に用いたキーが
その循環に含まれるかどうかだと思う。

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



65 :132人目の素数さん:02/02/28 16:11
文字数は関係ないだろ?
あくまで内部では固定桁数の2進数演算なんだから。
ちなみに、循環するか、最後にある値を無限回繰り返すか、の
2通りになる。

66 :132人目の素数さん:02/02/28 16:52
???じゃあ◆1HaSineが現れることもある?

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


67 :132人目の素数さん:02/02/28 17:58
>65 トリップで得られる文字列は必ず8桁ですよー
とりあえず◆ooooooooから10万回回して循環列がないか調べてみるわ。
途中でメモリが足りなくなるか19時になったらやめよう。

68 :65:02/02/28 18:07
8桁と言っても、1桁は64種類、つまり2進数の6bitだから、
実質8桁=48bitだろう・・・
2^48=約281.475兆ね。

69 :132人目の素数さん:02/02/28 18:19
>>67
#1HaSineから2000万まわしても循環列はまったくなかったんで、
10万くらいじゃあみつからないかと。
でも、循環列があるのだけは確実なんだから、何か1つは見つけたいよねぇ。

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

70 :67 ◆Swa/p57k :02/02/28 18:42
なんだ、58さんはちゃんと途中の循環も見てたのか・・・無駄な時間を過ごした。
副産物のトリップでも付けとこ。

71 :65:02/02/28 19:44
トリップが281兆通り有るのが解らんのか?(w

72 :58=64=69:02/02/28 19:55
>>71
誰に向かっていってるのかな?
ここにいる人は全員そんなことはわかってると思うよ。

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

73 :132人目の素数さん:02/02/28 20:56
プログラム公開してくれますか?
ウチのAthlon1.2GHzでよければ回します

74 :132人目の素数さん:02/02/28 20:59
1.大人には割れないけど子供には割れる
2.女にはきれいなのに男には汚い
3.犬には見えるのに猫にはなかなか見ることができない
4.車ならできるけど家では無理がある
5.天気の良い日には現れることもあるが 雨の日には見る  ことができない
6.どちらかというと理科室より職員室の方が住みやすい
7.みんな触れたことがある
これらの問題にすべてあてはまる答えを教えてください。
答えは1つだそうです。



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

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

76 :あいうえお ◆afKcqVYM :02/02/28 21:23
もしかしてここの人達
トリップを解析できるんですか…

77 :132人目の素数さん:02/02/28 21:25
>>75
多分出来なさそうだけどウチのマシンが空いてるのでとりあえず回して見たら
運が良ければいけるかなと思って.
よければ公開してください.

78 :58:02/02/28 22:04
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;
}
}

79 :58:02/02/28 22:05
//ログに追加
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;
}
}

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

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

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

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


81 :132人目の素数さん:02/02/28 22:57
循環1つ発見しました。
これから確認作業をするので、それで間違いなければ、公表します。

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

83 :132人目の素数さん:02/02/28 23:22
cryptってサーバーによって違くなんじゃなかった?


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

85 :132人目の素数さん:02/02/28 23:51
すげー!遂に発見したのか・・・
ちょっと感動

86 :132人目の素数さん:02/03/01 00:28
>>82
え?
循環する列が存在するということの確認が、何故
>>1or>>10の命題が「偽」ということになるの?

87 :81:02/03/01 01:07
>>86
ちょっと書き方が悪かったですね。すんません。

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

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

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

88 :132人目の素数さん:02/03/01 10:17
つーか、トリップは約70兆通りっす。
トリップ8文字目は16種類しか出ないので。

89 :132人目の素数さん:02/03/01 13:39
数学板らしく、問題にしてみまーす

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

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

90 :132人目の素数さん:02/03/01 17:14
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 :塾講師 ◆sBphv96s :02/03/01 19:05
入力したトリップがそのまま出るのってあるんか?

92 :132人目の素数さん:02/03/01 19:46
>>91
不動点はまだ見つかっていません

93 :132人目の素数さん:02/03/01 19:46
>>91
それ面白そうだな・・・

94 :あぼーん:あぼーん
あぼーん

95 :132人目の素数さん:02/03/01 21:35
>>91
それくらいなら力技で見つかりそうですね。邪道ですが。
1秒に1万個は検索できるから、全部調べても1週間で終わります。

96 :132人目の素数さん:02/03/01 21:38
>>95
1万倍ほど甘く見積もってないかい?

97 :132人目の素数さん:02/03/01 23:12
不動点を見つける確率=トリップをクラックする確率
ではないのか?

98 :132人目の素数さん:02/03/01 23:24
>>97
チョット違う。
不動点の場合はキーも6bit8文字なのに対し、
トリップのクラックは1文字当たり7bit (だよね?
で、文字数も8文字とは限らない。

99 :132人目の素数さん:02/03/02 20:24
99 モキャモキャ

100 : ◆100getRo :02/03/02 21:46
げっと

101 :132人目の素数さん:02/03/04 23:39
あげてみる。
だれか>>89の問題2か>>91解ける人いない?
俺はギブアップだ。

102 :(w作:02/03/04 23:50
不動点チェックなら検索プログラムに組み込んでもいいかもね

103 :132人目の素数さん:02/03/05 01:20
ていうか、検索プログラムでの総当り検索で
数学板の住人は納得してくれるのでしょうか?
それなら、プログラマー板とかでやれって感じのような
気がするんですが。

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

104 :132人目の素数さん:02/03/05 10:03
crypt()の中身書いてあるのどっかにない?

105 :age:02/03/06 13:37
age

106 :132人目の素数さん:02/03/07 01:03
なんだ、せっかくスレの杜で紹介されたのに
何でだれもいないんだ。

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

107 :132人目の素数さん:02/03/07 01:04
>>106
間違えた。
http://www.criptix.org/
だった。

108 :132人目の素数さん:02/03/07 08:25
>>106-107
http://www.cryptix.org/で合ってる?

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

109 :106:02/03/07 10:00
>>108
あ、そうそう。それそれ。
2回連続で間違えた、打つ出し脳。

110 :はなしはそれるが:02/03/07 17:12
>>74

の答、何?

111 :132人目の素数さん:02/03/11 02:46
期待age

112 :_:02/03/11 03:51
重複
http://kaba.2ch.net/test/read.cgi/stationery/1012891221/

113 :132人目の素数さん:02/03/11 20:45
>>9
> zzzzzzzzから始めればzzzzzzzzにならない

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

114 :132人目の素数さん:02/03/11 20:50
>>113
>>1>>10の違いを見ればわかるでしょ。

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

116 :132人目の素数さん:02/03/11 21:26
zzzzzzzzから始めても途中から22222222から始まる小循環
に入る可能性だって十分あるよね


117 :132人目の素数さん:02/03/11 23:41
>>115
「循環しない」とは誰も言っていない。
1の条件では「成り立たない」と言っている。

118 :132人目の素数さん:02/03/12 11:52
>>115
1から全部ログを読み直せ

119 :わたなべ:02/03/12 12:38
とりっぷってようするになんなのよ

120 :132人目の素数さん:02/03/12 15:17
初心者板に池

121 :132人目の素数さん:02/04/01 20:17
                 ┌─┐
                 |誰|
                 |も. |
                 │来│
                 │ね│
                 │え |
                 │よ .|
                 │ !!.│
                 └─┤    プンプン
                    |   ◎ /   ⌒ヽ◎
                    |    '  ノノ)ノレノノ
 ドウシタンダヨ  サクラ4カヨ ?     |    イ イ |  | |'  ミ3
    ヽ(`Д´)ノ ヽ(`Д´)ノ  (`Д´)ノ    ヘレゝ 〜/
    | ̄ ̄ ̄|─| ̄ ̄ ̄|─| ̄ ̄ ̄|─□( ヽ┐U
〜 〜  ̄◎ ̄  . ̄◎ ̄   ̄◎ ̄   ◎−>┘◎

          ヽ(`Д´)ノ オマエラ モット ガンバレヨ!!
            (  )   ウワァァン!!
            / ヽ


25 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)