真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 https://t.co/ApzLqRmjqR
Tsukasa #01 (4x vaccinated) on Twitter: "真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 https://t.co/ApzLqRmjqR"
真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 https://t.co/ApzLqRmjqR
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 で割り切れることが得られます。 この定理を使うと，ｐを法とする高い冪の計算が，ｐ以下の冪の計算に還元されることが分かります。 例えば， ９７１２３４≡９７３４＊（（９７１
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とやるだけです 2012-01-09 21:45:44
高速素因数分解 - メモ用紙2.0 | 日記 - 2013-10
2013-10-27 まどか☆マギカ 劇場版まどか☆マギカ観てきました。感想。 とても良い話だった。 色紙は杏さやでした。杏子かわいい！ 2013-10-25 研究 前回の記事にツッコミが入ったので更新しました。 なんかやりたいことは溜まってるんですが、研究してPOJ解いてアニメ観ると1日が終わっているのでなかなか進捗のない1週間でした。 まあ、研究している分だけ良いとも言いますが。 でも今やってる作業は、自分の研究に関わってくるかというと半々くらいのとこなので、手放しで喜べない感じもします。楽しいけど。 2013-10-17 高速素因数分解 知ってしまえば当たり前の話ですが、意外と蟻本にも載っていない話なので。 しばらく前に、Project Eulerの問題で素因数分解をする必要に迫られました。 素因数分解をするには、当然ながら素数を求めなくてはいけません。 これはエラトステネスの篩など
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
じゃがりきん on Twitter: "今はやりの素因数分解の可視化、俺もやってみたぜ！ https://t.co/27ZGdcXZMS"
互いに素である a,b の組を効率良く列挙しよう
tmnghryk on Twitter: "最大公約数を求めるのに、ユークリッドの互除法より速いとも言えるのが、ニコマコスの算法を拡張したブレントの算法。ビットシフトを用いる。a,bがともに偶数なら割り続け、回数を記録。一方が偶数なら割り続け、大から小を引く(奇ー奇＝偶がポイント)。これを繰り返して、一致したらGCD。"
http://arc360.info/algo/privatekey.html