SSブログ

MarriageTheoremさんの2929問題に答えてみる [Others]


ちょっとした問題 - 出題編
http://d.hatena.ne.jp/MarriageTheorem/20100109/1262963130

回答編も書かれているとのことですが,とりあえず見ずに回答してみる.
昼休み考えて,さっき内職して書いてみた.

■問題1
(難易度:ふつう) 29292929・・・と、「29」をいくつか繋げてできる数を
考えます。この数が29の二乗の倍数になることはあるでしょうか?
もしあるとしたら、そのような最も小さい数は、「29」をいくつ繋げた数でしょうか?

29を10進数としてn個並べた数字は
29 * Σ(i=1,...,n)100^(i-1) で表現できる.

29^2で割り切れるためには
Σ(i=1,...,n)100^(i-1) が 29 で割り切れればOK

100 mod 29 = 21 なので
Σ(i=1,...,n)100^(i-1) =
1 + 100 + 10^4 + ... = 1 + g + g^2 + ... where g = 21
が 29 で割れるnを求める問題であることがわかる.

g の位数が何かを考えたい,なぜなら,もし g^k = -1 mod 29 であれば
1 + g + g^2 +... + g^k + g^(k+1) + g^(2k-1) =
{1 + g + g^2 +... + g(k-1)} + (-1){1 + g + g^2 +... + g(k-1)} = 0 mod 29

実際 21^7 mod 29 = -1 なので 14個並べればOKとわかる.
ただ,k<7 で {1 + g + g^2 +... + g(k-1)} が 0 となるケースがあるかチェック
するしかない. 21^7 mod 29の計算も含め手計算でそれは無いことを確認

■問題2
(難易度:そこそこ難しい) 素数pについて、pを(10進数表記して)
k個繋げてできる数(kは正整数)をN(p,k)と書くことにします。
例えばN(5,3) = 555、N(29,2) = 2929です。このとき、「N(p,k)がpの二乗の倍数となる最小のkの値はk=pである」・・・(*)という条件を
満たす2桁以内の素数pは全部でいくつあるでしょう?

pが2桁のケースは問題1が問題2を解く上での実値になっている.
g = 100 mod p とおいたとき g = 1 のときだけ満たす.
なぜなら g^k = -1 mod p になると問題1のようなケースに帰着してしまうから.

2桁の素数をすべてチェックするのは面倒のように見えるけど50以上はないよね.
11,13,17,19,23,29,31,37,41,43,47 は大きい順につぶしてみる.
すると mod 11 で g=1となるので2桁では11のみ.

pが1桁(p=2,3,5,7)のケースは g = 10 mod p で考えればよい.これは3のみ.

答え:3,11 の2個だけ.

■問題3
(難易度:けっこう難しい) 同様に、今年は平成22年ということで
条件(*)を満たす22桁以内の素数pは全部でいくつあるでしょう?

d桁のときに g = 100^(d-1) mod p が 1になるときを探す問題
→ 100^(d-1) -1 が p で割り切れる問題に.

d=3のとき 9999 = 3^2 * 1111 = 3^2 * 11 * 101 なので3桁になる素数は
101,303,909 の3ケースのみ.

d=4のとき 999999 = 3^2 * 111111 = 3^2 * 111 * 1001 = 3^3 * 37 * 1001 =
3^3 * 37 * 7 * 11 * 13 なので
満たす素数は無し

d=5のとき 99999999 = 3^2 * 11111111 = 3^2 * 1111 * 10001
10001 が素数かどうか知らないので "手計算でやるの" 終了...

糸冬 もうやだこの問題...

少なくとも 10^d + 1 が素数かどうかに帰着することがわかった.
@factoring_bot たんにさっき調べてもらったら d=5,6,7 のときに該当する
ものは無いことが判明.
posted by ac at nice!(0)  コメント(0)  トラックバック(0) 

今週末 改ざんサイトでナニを踏んでしまう前に [Others]

標題の「ナニ」はGumblarやらGumblar.Xやら/*GNU GPL*/ やら/*GNU LGPL*/ やら ru:8080 やら,とにかく何と呼んでもいいんですけど,流行の「ナニ」です.耳にした被害から推測するにゴキブリ10倍理論と同じで,かなりのメジャーサイトがやられていることがわかってきましたね.以下には23のサイトが紹介されています.

サイト改ざん(2) ハウス食品、民主党、ローソンなど被害サイト23の改ざん状況
http://www.so-net.ne.jp/security/news/view.cgi?type=2&no=2113

で,どういう対策をしないといけないか,なんですけど,JPCERT/CC Alert では不十分かなと思いました.
http://www.jpcert.or.jp/at/2010/at100001.txt

各お詫びページにも書かれているかと思いますが,以下が割とまとまっているかなと思ったので掲載
http://pc11.2ch.net/test/read.cgi/sec/1261855221/753

今北さん用、GENO(Gumblar)ウイルス対処法。

行っておくべき事項を箇条書きにしました。
細かなことは他にもいろいろありますが、とりあえず以下を実施して下さい。

(1)Microsoft Update(Windows Update)を実行しシステムを最新の状態にする
(2)Adobe Readerを最新版に更新する
(3) Adobe ReaderのAcrobat JavaScriptを無効に設定
(4) JRE(Java Runtime Environment)を最新版に更新する
(5) Flash Playerを最新版に更新する
(6) QuickTimeを最新版に更新する

(1)~(4)を行っていれば、現時点で改ざんサイトを閲覧してもウイルスには感染しない。
攻撃コードは変化する可能性もあるので、念のため全て行っていただきたい。
Adobe Readerなどのアップデート方法については下記のトピックスを参照のこと。
Acrobat JavaScriptを無効にする方法は以下の通り。

(1)Adobe Readerを起動し[編集]メニューの[環境設定]を選択
(2)「分類」の中の「JavaScript」を選択
(3)「Acrobat JavaScriptを使用」のチェックをクリア
(4)「OK」ボタンを押す

-----
いずれにせよAbobeがクソ対応なことは間違いないです.週明けにしかPatchださねぇと言ってる.
Security Advisory for Adobe Reader and Acrobat
Release date: January 7, 2010
Vulnerability identifier: APSB10-02
http://www.adobe.com/support/security/bulletins/apsb10-02.html

他のBlogでも推奨されてますが,PDF Readerクローンを利用することを本気で考える時期なのかもしれません.特にお気に入りなものはありませんが,見てみて下さいな.

Foxit Reader
http://www.foxitsoftware.com/pdf/reader/

Perfect PDF Reader
http://www.soft-xpansion.com/index.php?p=pdftech/pdfqr

Brava! Reader
http://www.bravaviewer.com/reader.htm
posted by exploit at nice!(0)  コメント(0)  トラックバック(0) 

TSA Logo Contest [Others]

politicsな匂いがぷんぷんするのですが,一応書いとこう.

TSA Logo Contest @ Schneier on Security
http://www.schneier.com/blog/archives/2010/01/tsa_logo_contes.html

2月6日まで締め切りとか書いてるけど,貰って嬉しいものはない.でも,a fake boarding pass on any flight for any date は見てみたいかも.あー.このコンテスト自体が批判記事で,実際には行われないということかな.

ToDO:時間があればロゴ作成して貼ってみる.

追記:
2月22日に勝者が決まった模様
http://www.schneier.com/blog/archives/2010/02/tsa_logo_contes_2.html
posted by exploit at nice!(0)  コメント(0)  トラックバック(0) 

RSA-768が素因数分解されました [cryptography]

Factorization of a 768-bit RSA modulus
http://eprint.iacr.org/2010/006

既に終わったRSA解読コンテストのひとつであるRSA-768(768ビット合成数)の素因数分解を80台のマシンで半年かけて完了したようです.これまでの記録は2005年の663ビットでしたから大きな進歩といえなくはないですね.

参考1:
Preliminary Design of Post-Sieving Processing for RSA-768
http://cado.gforge.inria.fr/workshop/slides/montgomery.pdf

参考2:
RSA-768(今回解読対象となった合成数)
http://en.wikipedia.org/wiki/RSA_numbers#RSA-768
http://www.rsa.com/rsalabs/challenges/factoring/challengenumbers.txt
#当時はRSAセキュリティ社から5万ドルの懸賞金がかけられていました.

参考3:
The RSA Factoring Challenge FAQ
What does it mean when a Challenge Number is factored?
http://www.rsa.com/rsalabs/node.asp?id=2094#WhatDoesItMean
ここに興味深い文章があります.
> Suppose, for example, that in the year 2010 a factorization of RSA-768 is
> announced that requires 6 months of effort on 100,000 workstations.
> In this hypothetical situation, would all 768-bit RSA keys need to be replaced?
> The answer is no.
posted by exploit at nice!(0)  コメント(0)  トラックバック(0) 

R-1ぐらんぷり2010 予選 [Others]


ac です.
12月28日に書いて某所にうpしたものをこちらにも掲載します.最後の追記は今日書いた.

いつと変わらない朝を家族と共にした後,違う路線の電車に向かいました.今日は午前休暇を頂き,渋谷のTEPCOホールへ = R-1東京第1次予選会場へ.

昨年の反省に基づき,観客が疲れていない時間帯に出場できるよう,早めのエントリが功を奏し,一番早いグループAの出場でした.しかしいきなり3番目の登場は,客席が暖まっていない段階だったので少々不利だったかもしれません.これは運でしかないのでしょうがないですね.

今日のエントリ:http://www.r-1gp.com/sche/1228.htm

もうひとつあった昨年の反省点の「あいさつ」についてはちゃんとこなせました.今回は朝一でしたので控え室(というか上手<かみて>の物置エリア)が混雑しておらず,スタッフの皆様を認識可能でしたし,時間帯に違和感もなく「おはようございます!」と挨拶できました.また,待機時間が少なかったので芸人さん方の空気に飲まれることなく,芸人っぽくというか場慣れしている風に振舞うことができました.

しかし肝心のネタ自体は昨年と同レベルの中笑だったと思います.全く笑いがないというわけではないけれど爆笑もずっとは続かないという状況です.また,ちゃんとオチなかったので反省中です.用意した大きめのドッカンの箇所よりも小ネタの方に笑いが大きく,やはりシナリオどおりにはうまくいかないですね.ネタ作りは難しいです.笑いのツボというか感覚を観客にあわせて調整しないといけないことを痛感しました.

今回,一応2本準備しておきました.A:新型インフルエンザ,B:ボイストレーニング のうち昨晩Aで出ると決めてそればっかり練習してたんですが,実際に舞台の状況を思い起こすにBのネタの方がはるかによかったと思います.8:2で女性でしたし,朝でしたのでちょっとエロ系は避けておくべきだったかと.男性の笑い(苦笑)が大きかったように思います,というか引いていた女性もいたかもしれません.集合時間前に入ったドトールで横の席にいた観客の方々は少なくともそうでしたorz

その場で臨機応変にネタやディテールを変える能力が必要とされていると感じました.通常のプレゼンテーションにおいても,そういうことを意識してお話するかどうかで聴衆の理解度や関心度が高いでしょうし,この臨機応変さというアビリティはビジネスにおいても重要ではないかと再認識させられました.

また来年もR-1に限らず,ネタをやっていく機会が多くあるでしょうから,今回得たことを糧に自分を磨いていけたらなと考えています.あ,ちょっと方向性が違うか,どうなんだろう?正直.

/////////////////////////////////////////
追記(所感とか反省など):
小豆まりさんは非常に礼儀正しい方でした.芸人さん全般そういう印象を持ちましたが,特に際立ちました.これから応援しようとおもふ.
・エレベータの乗り降りの関係で,受付に何故か1番乗りしてしまった.
・ピンマイクを使えると勝手に勘違いしてしまい,想定する動きができなくて困った.後で考えるに,動き
・落選し,心も折れたのでSCIS2010ナイトセッションのネタを再考せねばなりません,困った.
・一昨年前も早めに移動してコーヒー飲んでから舞台に立ち,落ちた.このジンクスを抱えるのは嫌なので,ドトールにはもう行かない.
posted by ac at nice!(0)  コメント(0)  トラックバック(0) 

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。