- 締切済み
素数判定について
- みんなの回答 (2)
- 専門家の回答
みんなの回答
- yumikowoyorosiku
- ベストアンサー率100% (2/2)
「コンピュータと素因子分解」和田秀男著 発行遊星社・発売星雲社 ISBN4-7952-6889-4 本体2000円+税 の第7章にずばり解説されてます。 手元にある本によると 1999年4月に改訂版第1刷発行とありますから まだ手に入ることでしょう。 また、同じ著者による 「高速乗算法と素数判定」 上智大学講究録No.15 という本にも解説されています。 そちらのお求めは、 東大赤門前の有隣社(03-3814-0275)か 東大病院前(というか旧数学科の前)のマテマティカ (03-3816-3724)まで。 本格的に勉強なされるのでしたら、 「A Course in Computational Algebraic Number Theory」Henri Cohen著 Graduate Texts in Mathematics 138, Springer-Verlag ISBN3-540-55640-0 ISBN0-387-55640-0 を手元に置かれると宜しいかと思われます。 書き込むのが遅すぎましたかもしれませんが、 お役に立てれば幸いです。
- stomachman
- ベストアンサー率57% (1014/1775)
回答になってないんですが... APR Testというやつ。話にしか聞いてません。多項式時間に非常に近い高速な方法だそうで、今時のPCなら100桁どころじゃないでしょう。 という訳で、この際、面白そうだから探してみましたが駄目ですねえ。でも、1990年頃に改良版が出たようで、Googleで探すと→Bosma, W. and van der Hulst, M.-P. ``Faster Primality Testing.'' Advances in Cryptology, Proc. Eurocrypt '89, Springer-Verlag, 652-656, 1990. が出てきました。この文献は、国会図書館http://www.ndl.go.jp/の検索(タイトル=Eurocrypt ,刊行=1990年)でヒットしますから、コピー入手可能でしょう。また、国内の何処やらの大学の修論発表会のリストにも載ってますから、その大学に問い合わせる手もあるかも。 なお、他にも楕円関数論を使った高速な方法がある。もちろんこの分野の話を理解するには最低限代数学・ゼータ関数の知識は要求されるでしょうから、いっぱい勉強しないといけないですね。
関連するQ&A
- 数学A 場合の数の問題について
数学Aの場合の数の問題で、解き方がわからなかったので投稿しました。 「5桁の整数 0,1,2,3,4を使って4桁の整数をつくる。 このとき、4の倍数になるのは何通りか」 という問題なのですが、ぜひ解法を教えていただきたいです。
- ベストアンサー
- 数学・算数
- nが素数であるかどうかの判定
素数判定の勉強をしています。 次の文の内容が成立する理由がわかりませんでした。 -----内容----- n-1 = 2^(t-1) * m としたとき とある整数a (aは2以上n-2以下)において もし a^{(2^j)*m} ≡ 1 mod n かつ a^[{(2^(j-1)}*m] ≠ ±1 mod n ならば a^[{(2^(j-1)}*m] -1 と nの自明でない最大公約数がみつかりnは素数ではないと判断できる。 (ここで、jは1以上t-1以下の自然数。また記号「≠」を「not 合同」の意味で使用しています。) -----終了----- これはなぜなのでしょうか? なぜ公約数が見つかるのでしょうか? アドバイスよろしくお願いします。
- ベストアンサー
- 数学・算数
- 『博○の愛した数学』のような…
この本の中で用いられる数学は、どんなジャンルに分類されるのでしょうか? 整数についての性質や特徴が本当に面白かったのでどんどん調べて行きたいのですが、書店で『整数論』のような専門書を読んでもよくわかりません。 双子素数や友愛数、このようなものを学べる数学ジャンル、学べる本など、ご存知の方いらっしゃいましたら教えてください。
- 締切済み
- 数学・算数
- 場合の数について
大学受験の数学の問題でわからないものがありました。 2000年の東京大学の入試問題です。 次の条件を満たす正の整数全体の集合をSとおく。 各桁の数字は互いに異なり、どの2つの桁の数字の和も9にならない。 ただし、Sの要素は10進法で表す。また、1桁の正の整数はSに含まれるものとする。 (1)Sの要素でちょうど4桁のものは何個あるか。 (2)小さい方から数えて2000番目のSの要素を求めよ。 解答は、 (1)1728個 (2)8695 です。 解説は(1)について、「9・8・6・4個」と書いてありました。 考えてみたもののわかりません。 考え方を教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 24の倍数の判定方法、それ以外でもOK
倍数の判定方法について、たとえば、 http://www004.upp.so-net.ne.jp/s_honma/number/multiple.htm が参考になります。 有名な話として、整数が3の倍数であることを判定するには、各桁を足した数が3で割れるかどうかを判定すればいいです。 ところで、そのサイトに書かれていない、24の倍数であるか否かの判定方法があれば教えていただきたいです。 そのサイトに書かれていないその他の数字でもOKです。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素数判定アルゴリズム内の剰余計算
今勉強している任意倍長精度整数の素数を判定するアルゴリズム内で x^q mod n という計算をするところがあるのですが、 正確に計算しようとすると計算量が膨れ上がってしまって 高速にできなくて困っています。 参考にしている文献に "x^q mod nの計算ではx^q mod nを正確に求める必要は無く、 x^q ≡ x^q' (mod n)となる x^q'でよい"という記述があるのですが どういう意味なのかよくわかりません。 どなたか教えていただけないでしょうか?
- 締切済み
- その他(プログラミング・開発)