素数列挙について - MugiCha
Competitive Programming Advent Calendar 3日目は、数学っぽい話をしたいと思います。 N以下の素数をすべて求めよ。 N以下の素数の個数を求めよ。 A以上B以下の素数の個数を求めよ。 こんな感じの問題を見たことがあると思います。また問題としてでなくても、解く過程にこのようなサブ問題を解かなければいけない場合もよくあると思います。素数については説明しなくてもいいですよね？ このような問題を素数列挙と呼ぶことにします。素数列挙ができれば、大きい数の素数判定や素因数分解をめっちゃ高速化したり、トーティエント関数、メビウス関数等、数学系のいろんな関数を求めたりできます。最近のもので素数列挙がほぼ必須のものだと Codeforces Beta Round #86 (Div. 1 Only) C. Double Happiness ICPC 国内予選 2011 A
フェルマーの小定理 - faireal.net
フェルマーの小定理 (2002-06-16) フェルマーの定理「 n が素数なら an ≡ a (mod n) 」を、(a+b)n の展開から説明。原始根の概念まで フェルマーの小定理 2002年 6月16日 記事ID d20616 フェルマーの小定理というのは、「素数 p に対して、勝手な整数 n の p 乗を p で割ると余りは n に戻る」というようなものです。例えば、7は素数ですが、 27 = 128 → 7で割ると商18、余り2 37 = 2187 → 7で割ると商312、余り3 47 = 16384 → 7で割ると商2340、余り4 57 = 78125 → 7で割ると商11160、余り5 …… てな感じで、余りは7乗されたもとの数に戻ります。式で書けば、 np ≡ n (mod p) mod pというのは、pで割った余りで分類して考える、という意味です。例えば、 107 =
RSA暗号と擬素数 - faireal.net
OGMオープンソースに 2003年 1月10日 記事ID d30110 OGMオープンソースに 2003年1月8日 Tobias has joined xiph.org: Ogg Media (OGM) が正式に Ogg の開発もとと統合 2003年1月10日 OGMフォーマット: オープンフォーマットとして確立へ―― 新世代の音声コーデック Ogg Vorbis を含む「Oggシリーズ」の開発元である Xiph.org は、 Tobias 個人が開発、公開を続けてきたマルティメディア形式OGMを正式の ogg の動画形式として採用することを決定した。 Tobias は ogg チームに参加、OggDS は今後オープンソースとなる。 さらに、Xiph.org の CEO、Emmett Plant は、現在すでに広く用いられているOGM動画形式について、 xiph.org が今後開発するもの
強擬素数 - faireal.net
ミラーテストと強擬素数（きょうぎそすう） (2003-01-29) 128ビットRSAの鍵生成のデモ: JavaScript (2003-05-24) JavaScript上で、1分程度で20～40桁の素数を見つける確率的アルゴリズムを実装し、計算の複雑性理論についていくつかの実感をつかむ。 ミラーテストと強擬素数（きょうぎそすう） 2003年 1月29日 記事ID d30129 「RSA暗号と擬素数（ぎそすう） - JavaScript」では、 巨大な整数が素数であるかどうか調べる「確率的」検査法、フェルマーテストを強引に JavaScript 上にもちこんだ。 先に進む前に、関連する話題として、ミラー（Miller）の素数判定法と強擬素数（きょうぎそすう）に触れておく。 ミラーのテスト 巨大な整数が素数か素数でないかを知るのに、 フェルマーテストは実用上それなりに有効だ。 素数でない数
巨大な素数の効率的な作り方 - OKWAVE
（１） 大きな素数を見つけるには、Miller-Rabin法を使うのが良いです。確率的素数判定法の１つです。厳密に素数であることを判定できるわけではありませんが、現実的に十分な信頼度で、高速に判定することができます。 なお、n^2+n+41で生成した数の中から素数を探すと、素数に偏りができてしまいます。512bitの一様な乱数を発生させて、素数かどうか判定するようにしてください。 （２） 整数の四則演算にも使えるプログラミングテクニックはいろいろあります。ビットの立っている位置を探すなら、以下の方法も使えるでしょう。 int mrb[256]; //1が立っている最も下位のビット位置をあらかじめテーブルに入れておく。 unsigned char u; for( ;u;u&=u-1) { //最も下位の1をクリアする。 mrb[u] ← 1が立っているビット位置を順番に取り出せる。 } 回答
ミラー–ラビン素数判定法 - Wikipedia
ミラー–ラビン素数判定法（英: Miller–Rabin primality test）またはラビン–ミラー素数判定法（英: Rabin–Miller primality test）は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や ソロベイ–シュトラッセン素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したMillerテストは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンがこれを無条件の確率的アルゴリズムに修正した。 フェルマーやソロベイ–シュトラッセンの素数判定法と同様、ミラー–ラビン素数判定法も素数に関して成り立つ等式に基づいており、与えられた数についてそれら等式が成り立つかどうかで判定を行う。 まず、有限体 の単位元の平方根についての補題を考える。ここで
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
