アフィン暗号に関する問題についての質問です。

[けん]

アフィン暗号についての問題です。

問題は、AOJのものです。
問題です。
http://judge.u-aizu.ac.jp/onlinejudge/d ... sp?id=0040

自分は次のように書きました。

コード:

#include<stdio.h>
#include<string.h>
int main(void)
{
	int i,j,m,p,s,len;
	int A,B,C[26];
	int x,y,z;
	int d,e;
	char moji[256];
	
		for(j=0;j<25;j++)
		{
		for(m=0;m<25;m++)
		   {
		    for(p=0;p<25;p++)
				{
				for(s=0;s<25;s++)
					{
						if((((A*('a'+j)+B)%26)=='t')&&(((A*('a'+m)+B)%26)=='h')&&(((A*('a'+p)+B)%26)=='a')&&(((A*('a'+s)+B)%26)=='i'))
				
						{
								d=A;
								e=B;
						}
						
					}
				}
			}
						
		}
     printf("%d,%d\n",d,e);
	gets(moji);
	len=strlen(moji);
	for(i=0;i<len;i++)
	{
		if(moji[i]!=' ')
		{
			moji[i]-='a';
		}
	}
	for(i=0;i<len;i++)
	{
		if(moji[i]==' ')
		C[i]=moji[i];
		else
		C[i]=(d*moji[i]+e)%26;
	}
	for(i=0;i<len;i++)
	{
		printf("%c",C[i]);
	}
		
}

αをA,ベータをBとしました。
エラーは出ないのですが、答えを入力すると文字化けしてしまいます。
例えばpnopと打った場合、thatがでるはずなのですが（入力、出力例より）文字化けしてしまいます。
また、途中でｄ＝Aとe＝Bの値を表示するようにしたのですが、値が大きすぎる気がします。
どこが間違っているのでしょうか？
教えていただけますでしょうか。

よろしくお願いします。

[usao]

人にコードを見せて何かを確認してもらおうという場合，
少なくとも自分のコードの各所が何をやっている（やろうとしている）のかくらい説明した方が良いと思いませんか？
現状ではコードから「あなたがどういう作戦で問題に臨んでいるのか」というレベルから読み取らねばなりません．
100人いたら100人がまず同じことをやるような非常に簡単な話ならまだしも，
人によって解法が異なるかもしれない類の問題なのだとしたら，あなたのやろうとしていることを読み取れなければ
回答できない→その分有用な回答を得られるチャンスが減る　わけで，損だと思いませんか？


で，問題を見た限り，A,Bの値は公開されておらず，これを推定する必要があるのかもしれませんが，
それに対してどのようなアプローチをとっていますか？
とりあえずコードをざっと拝見した限りだと，A,Bの値は不定なまま演算に用いられているように見えるのですが．

[けん]

ご回答ありがとうございます。

確かにそうだと思います。人に質問する態度ではなかったです。
本当に失礼しました。今後はこのように人を不快にするようなことがないように気をつけます。
あと、ご指摘ありがとうございます。　

コードを再度貼り、説明を加えさせて頂きます。

自分が考えた解放としては、まずA,Bの値を求めます。この際、ｐnop(解答例より)がthatになれば上手くいっていると判断します。今回の問題は、this,thatが入っていなければならず、まずthat,thisを表示するためのA,Bを求めようとしました。
この時、if((((A*('a'+j)+B)%26)=='t')&&(((A*('a'+m)+B)%26)=='h')&&(((A*('a'+p)+B)%26)=='a')&&(((A*('a'+s)+B)%26)=='i'))を使います。
A*('a'+j)+B)%26だけだと、A,Bの値はひとつに定まらないので、A*('a'+m)+B)%26)=='hをくわえました。また、this,thatが表示できるように残りの２つもつけ、A,Bの値を定めていこうと思い、書きました。
よろしくお願いします。

コード:

 
#include<stdio.h>
#include<string.h>
int main(void)
{
	int i,j,m,p,s,len;
	int A,B,C[26];//αをA、βをBとし、Cは暗号解読し終わった文字列を入れます。
	int d,e;//AとBの値が確定した時、ｄにAの値を、eにBの値を入れます。
	char moji[256];//この配列の中に文字列を入れていきます。
	
		for(j=0;j<25;j++)
		{
		for(m=0;m<25;m++)
		   {
		    for(p=0;p<25;p++)
				{
				for(s=0;s<25;s++)
					{
						if((((A*('a'+j)+B)%26)=='t')&&(((A*('a'+m)+B)%26)=='h')&&(((A*('a'+p)+B)%26)=='a')&&(((A*('a'+s)+B)%26)=='i'))
				　/*ｊ、ｍ．ｐ．ｓについて・・・・aからb,c・・・ｚまで値が変化し、この際、ｔ,h,a,iになるときのA,Bを決めていきます。*/
					{
								d=A;
								e=B;
						}
						
					}
				}
			}
						
		}
     printf("%d,%d\n",d,e);
	gets(moji);//文字を入力します。
	len=strlen(moji);
	for(i=0;i<len;i++)
	{
		if(moji[i]!=' ';
		{
			moji[i]-='a';
		}
	}
	for(i=0;i<len;i++)
	{
		if(moji[i]==' ')
		C[i]=moji[i];
		else
		C[i]=(d*moji[i]+e)%26;
	}
	for(i=0;i<len;i++)
	{
		printf("%c",C[i]);
	}
		
}

[usao]

[コードを拝見して]
・A,Bが不定値なのに演算に用いている点：プログラムとしておかしい．
・いきなりA,Bを求めることが可能なのか？という点．
　入力されてきた文字列をヒントにしなければA,Bを推定することが不可能だと思う．
　（原文が同一でも，暗号側が用いたA,Bの値が異なれば入力文字列が異なるはずなのに，
　　入力を見ずに果たしてA,Bを推定できるであろうか？）

[解法について]
私も現時点で答えがわかるわけではありませんので，感じたことだけ…

とりあえずキーワードが共に４文字なので
　入力文字列を単語に区切って，4文字の単語群のみを見る．
　→４文字のうち，最初と最後が同じやつは，thatであった可能性があるのでそれを手掛かりにする．
　　　"that"のうち，aの値は0ということだから，aの変換式にはBのみが作用していることになるから
　　　Bから先に推定する．
　→キーワードがthisだった場合はどうするのか？
　　　hとi，　tとs　の値が隣同士であることなどをうまいこと利用できないだろうか？

オフトピック

なにこれ難しい…
（modが入った連立方程式になっちゃうんだけど，どうやって解くんだ？人生で一回もやったことないぞそんなこと…
ググったら「合同式」とかいうものになるっぽいんだけど…　数学に拒絶反応発動にて読めず．）

[みけCAT]

>>usaoさん
解法についての見解です。

► スポイラーを表示

mod 26なので、α・βそれぞれの値を0～25の整数にして全探索します。
ただし、αについては0及び26と互いに素でない数は外します。
αは1,3,5,7,9,11,15,17,19,21,23,25の12通り、βは[0..25]の26通りあります。
文字列の長さが最大256文字なので、αの候補数をA、βの候補数をB、文字列の長さをNとすると

コード:

α、βを全探索[O(AB)]
  今のα、βで各アルファベットの変換テーブル(暗号→平文の逆変換テーブル)を作る[O(1)]
  文字列全体を変換(復号)する[O(N)]
  変換した文字列に"this"または"that"が含まれているかを調べる[O(N)]
    含まれていたらその変換した文字列を解として探索を打ち切る
見つかった解を出力

という手順ででき、全体でO(ABN)です。
A=12,B=26,N=256のとき、ABN==79872であり、1ケースだけなら余裕で1秒以内に終わります。
問題文中のテストケース数nの上限がわかりませんが、n<=125くらいなら耐えられるでしょう。

…あまり余裕が無いですね。また、"this"や"that"が現れるα・βの組が複数あったらどうするのでしょうか？

[usao]

>>みけCAT様

► スポイラーを表示

うーん，全探索ですか．
小難しい話を放棄できるのが利点ですが，いきなり最終手段に打って出てる感があるというか…
少しだけでも工夫できればずいぶん計算時間が違う気がするんですよね．
例えば…
βの値の影響って，変換テーブルが回転するだけだと思うので，
thisやthatをあらわすパターンを値そのものではなく，テーブルが回転しても不変な性質で判定できれば
力技で探索するにしてもα側だけで済ませられるかもしれません．
例えば，符号化された４文字を，先頭とその他３文字との間の差分値（→３つの値）で表すとしたら，
あるα値のとき，thisやthatが取り得る表現はβの変動に対して何通りかしかないような気が？
(mod 26によってできる境界がどこに発生するか，がβにより26パターンあるけど，キーワードの４文字に対してのみ考えれば…４パターン…か？）

[みけCAT]

>>usaoさん

► スポイラーを表示

なるほど、それはいい考えですね。
例えばthisが4,18,19,3と符号化されているとき、差分は14,1,-16ですが、
差分として(次の値+26-前の値) mod 26を使えば、14,1,10となり、境界の問題は発生しないと思います。
これを使うと、αが決まればβを1通りに定められるので、O(AN)に落とせそうですね。