「膨大な桁数の素因数分解が可能なアルゴリズム」を開発したら政府機関に殺されてしまうのか？
代表的な公開鍵暗号の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
Tsukasa #01 (4x vaccinated) on Twitter: "真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 https://t.co/ApzLqRmjqR"
真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 https://t.co/ApzLqRmjqR
GolangでMiller-Rabin素数判定法を実装してみる - 逆さまにした
背景 Wikipedia にも記載されていますが、 Miller-Rabin素数判定法は 与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種で、乱択アルゴリズムです。 フェルマーテストでは、以下のフェルマーの小定理を用いて 素数判定を行いますが、カーマイケル数と呼ばれる合成数を、誤って(素数と)判定してしまいます。 例えば、最小のカーマイケル数は561ですが、のため、素数ではありません。 フェルマーの小定理 素数 と互いに素となる整数 に対して が成り立つ。 フェルマーテストを改良したのがMiller-Rabin素数判定法です。 詳細はWikipediaを参照頂ければと思いますが、与えられた素数を奇素数(素数判定をしたいのは、大きい整数なので、奇素数を考えれば目的は十分に果たせます)と考え、 と表現します。ここで は正整数で、 は奇数です。すると式(1)は以下のように書けます。
A - Uncommon/みんプロ2018本戦 - D言語で競プロ
問題概要 集合が与えられる。 各整数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)とします。
拡張ユークリッドの互除法 - 唯物是真 @Scaled_Wurm
\(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(
フェルマーの小定理
ｐ を素数，ｘをｐで割り切れない整数とする。 このとき，ｘｐ−１−１はｐで割り切れる。即ち， ｘｐ−１ ≡１ (mod ｐ) が成立する。 整数の合同と１次合同式の項で，ｍを法とする整数の逆元のことを説明しました。ｍを法とする逆元はｘとｍが互いに素のとき，存在しました。これは，ｍ＝ｐ：素数の場合は，ｘがｐで割り切れないことを意味しますから，フェルマーの定理はｍ＝ｐ：素数の場合，ｐを法とするｘの逆元はｘｐ−２であることを示しています。 例えば 101 は素数ですから，１100−１，２100−１，３100−１，４100−１，．．．．９８100−１，９９100−１，１００100−１ が すべて，101 で割り切れることが得られます。 この定理を使うと，ｐを法とする高い冪の計算が，ｐ以下の冪の計算に還元されることが分かります。 例えば， ９７１２３４≡９７３４＊（（９７１
素因数の個数の平均 - inamori’s diary
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] =
mod p の逆元
おめ @omeometo @ut_math 特に名前とかはなさそうですがrng-hos法とかrng-hos-ome法とか呼ぼうとしてたこともありました たとえば23^-1 mod 97を計算するなら23*4=-5 5*19=-2 2*49=1より23^-1=(-1)^2*4*19*49=38とやるだけです
高速素因数分解 - メモ用紙2.0 | 日記 - 2013-10
2013-10-27 まどか☆マギカ 劇場版まどか☆マギカ観てきました。感想。 とても良い話だった。 色紙は杏さやでした。杏子かわいい！ 2013-10-25 研究 前回の記事にツッコミが入ったので更新しました。 なんかやりたいことは溜まってるんですが、研究してPOJ解いてアニメ観ると1日が終わっているのでなかなか進捗のない1週間でした。 まあ、研究している分だけ良いとも言いますが。 でも今やってる作業は、自分の研究に関わってくるかというと半々くらいのとこなので、手放しで喜べない感じもします。楽しいけど。 2013-10-17 高速素因数分解 知ってしまえば当たり前の話ですが、意外と蟻本にも載っていない話なので。 しばらく前に、Project Eulerの問題で素因数分解をする必要に迫られました。 素因数分解をするには、当然ながら素数を求めなくてはいけません。 これはエラトステネスの篩など
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Shin-ichiro Seki on Twitter: "「6以上の任意の整数nに対して、不等式 nlogn < p_n < nlogn+nloglogn が成り立つ。ただし、p_nはn番目の素数とする。(Rosser-Schoenfeld)」 は素数定理より強く、素数定理より簡単に述べられる。"
tsujimotter 日曜数学者 on Twitter: "ミラーラビンって確定的にもできたんですね！楽しいです！ https://t.co/gmeZXR5VSD"
じゃがりきん on Twitter: "今はやりの素因数分解の可視化、俺もやってみたぜ！ https://t.co/27ZGdcXZMS"
互いに素である a,b の組を効率良く列挙しよう
tmnghryk on Twitter: "最大公約数を求めるのに、ユークリッドの互除法より速いとも言えるのが、ニコマコスの算法を拡張したブレントの算法。ビットシフトを用いる。a,bがともに偶数なら割り続け、回数を記録。一方が偶数なら割り続け、大から小を引く(奇ー奇＝偶がポイント)。これを繰り返して、一致したらGCD。"
http://arc360.info/algo/privatekey.html