代表的な公開鍵暗号の1つであるRSA暗号は、「桁数が大きい合成数の素因数分解が困難である」ということを安全性の根拠とした暗号方式です。そのため、「膨大な桁数の素因数分解を可能にするアルゴリズム」が開発されてしまえば、その安全性は揺るぎます。もし、「膨大な桁数の素因数分解を可能にするアルゴリズム」を開発した場合に何が起きるのかについて、実名制Q&AサイトのQuoraでさまざまな人々が独自の見解を発表しています。 If I solve integer factorization, will I get killed because I would have broken cryptography? - Quora https://www.quora.com/If-I-solve-integer-factorization-will-I-get-killed-because-I-would-ha
背景 Wikipedia にも記載されていますが、 Miller-Rabin素数判定法は 与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種で、乱択アルゴリズムです。 フェルマーテストでは、以下のフェルマーの小定理を用いて 素数判定を行いますが、カーマイケル数と呼ばれる合成数を、誤って(素数と)判定してしまいます。 例えば、最小のカーマイケル数は561ですが、のため、素数ではありません。 フェルマーの小定理 素数 と互いに素となる整数 に対して が成り立つ。 フェルマーテストを改良したのがMiller-Rabin素数判定法です。 詳細はWikipediaを参照頂ければと思いますが、与えられた素数を奇素数(素数判定をしたいのは、大きい整数なので、奇素数を考えれば目的は十分に果たせます)と考え、 と表現します。ここで は正整数で、 は奇数です。すると式(1)は以下のように書けます。
問題概要 集合が与えられる。 各整数k = 1, 2, ..., Mについて、kと互いに素であるAの要素の個数を求めよ。 制約 解法 愚直にやると少なくともO(N*M)かかってしまうのでまとめて数え上げるなどの高速化が必要になります。 kを固定したときに、kとa_iが互いに素であるというのは、gcd(k, a_i) = 1であるというのが定義ですがこの条件はまとめて数え上げようとするときには少し使いにくいので別の同値な条件に言い換えてみます。 という感じにkを素因数分解したとします。(p_jは素数) このとき、kとa_iが互いに素であることの必要十分条件は、a_iがどのp_jでも割りきれないこととなります。逆に、kとa_iが互いに素でないことは、a_iがあるp_jで割り切れることと同値です。 この事実を使ってkと互いに素でないa_iの個数を求めることにします。その個数をn(k)とします。
\(a, b\)の2つの正の整数が与えられたときに\(ax+by=\gcd(a, b)\)となるような整数\(x, y\)のうちの1つの組を計算するアルゴリズム たとえば5リットルの入れ物と7リットルの入れ物を使って11リットルの水を汲む方法などが計算できる 昔こんなツイートをしてたようですがようやく理解できた気がします(遅すぎ。中国の剰余定理の方はまだ) 中国の剰余定理とか拡張ユークリッドの互除法とかわかってない(´・ω・`)— 無限猿(id:sucrose)@39月病 (@Scaled_Wurm) 2014年12月23日 Wikipediaの説明を読んだらよくわからなくて???となったがいろいろググってなんとか理解した \(a, b\)の2つの整数についてユークリッドの互除法をやるときに、\(ax_1+by_1=a\)と\(ax_2+by_2=b\)みたいに両辺がある形で考えて\(a(
p を素数,xをpで割り切れない整数とする。 このとき,xp−1−1はpで割り切れる。即ち, xp−1 ≡1 (mod p) が成立する。 整数の合同と1次合同式の項で,mを法とする整数の逆元のことを説明しました。mを法とする逆元はxとmが互いに素のとき,存在しました。これは,m=p:素数の場合は,xがpで割り切れないことを意味しますから,フェルマーの定理はm=p:素数の場合,pを法とするxの逆元はxp−2であることを示しています。 例えば 101 は素数ですから,1100−1,2100−1,3100−1,4100−1,....98100−1,99100−1,100100−1 が すべて,101 で割り切れることが得られます。 この定理を使うと,pを法とする高い冪の計算が,p以下の冪の計算に還元されることが分かります。 例えば, 971234≡9734*((971
Problem 468の計算量を見積もるときにこんな問題が思い浮かびました。 N以下を素因数分解したとき、素因数の個数の平均は? 例えば、2、3、4 = 22、5なら1個、6 = 2 * 3なら2個とします。logNよりはずっと小さいと思われます。とりあえずコードを書いて調べてみましょう。 from itertools import * def div_pow(n, d): e = 0 while n % d == 0: e += 1 n /= d return e, n def make_factors_table(N): a = range(N + 1) for p in takewhile(lambda p: p * p <= N, (n for n in count(2) if a[n] == n)): for m in xrange(p, N + 1, p): if a[m] =
2013-10-27 まどか☆マギカ 劇場版まどか☆マギカ観てきました。感想。 とても良い話だった。 色紙は杏さやでした。杏子かわいい! 2013-10-25 研究 前回の記事にツッコミが入ったので更新しました。 なんかやりたいことは溜まってるんですが、研究してPOJ解いてアニメ観ると1日が終わっているのでなかなか進捗のない1週間でした。 まあ、研究している分だけ良いとも言いますが。 でも今やってる作業は、自分の研究に関わってくるかというと半々くらいのとこなので、手放しで喜べない感じもします。楽しいけど。 2013-10-17 高速素因数分解 知ってしまえば当たり前の話ですが、意外と蟻本にも載っていない話なので。 しばらく前に、Project Eulerの問題で素因数分解をする必要に迫られました。 素因数分解をするには、当然ながら素数を求めなくてはいけません。 これはエラトステネスの篩など
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く