- 締切済み
素数判定について
yumikowoyorosikuの回答
- yumikowoyorosiku
- ベストアンサー率100% (2/2)
「コンピュータと素因子分解」和田秀男著 発行遊星社・発売星雲社 ＩＳＢＮ４-７９５２-６８８９-４ 本体２０００円＋税 の第７章にずばり解説されてます。 手元にある本によると １９９９年４月に改訂版第１刷発行とありますから まだ手に入ることでしょう。 また、同じ著者による 「高速乗算法と素数判定」 上智大学講究録Ｎｏ．１５ という本にも解説されています。 そちらのお求めは、 東大赤門前の有隣社（０３－３８１４－０２７５）か 東大病院前（というか旧数学科の前）のマテマティカ （０３－３８１６－３７２４）まで。 本格的に勉強なされるのでしたら、 「A Course in Computational Algebraic Number Theory」Henri Cohen著 Graduate Texts in Mathematics 138, Springer-Verlag ＩＳＢＮ３－５４０－５５６４０－０ ＩＳＢＮ０－３８７－５５６４０－０ を手元に置かれると宜しいかと思われます。 書き込むのが遅すぎましたかもしれませんが、 お役に立てれば幸いです。
関連するQ&A
- 数学Ａ 場合の数の問題について
数学Ａの場合の数の問題で、解き方がわからなかったので投稿しました。 「５桁の整数 ０，１，２，３，４を使って４桁の整数をつくる。 このとき、４の倍数になるのは何通りか」 という問題なのですが、ぜひ解法を教えていただきたいです。
- ベストアンサー
- 数学・算数
- 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年の東京大学の入試問題です。 次の条件を満たす正の整数全体の集合をＳとおく。 各桁の数字は互いに異なり、どの２つの桁の数字の和も９にならない。 ただし、Ｓの要素は１０進法で表す。また、１桁の正の整数はＳに含まれるものとする。 (１)Ｓの要素でちょうど４桁のものは何個あるか。 (２)小さい方から数えて2000番目のＳの要素を求めよ。 解答は、 (１)1728個 (２)8695 です。 解説は(１)について、「9・8・6・4個」と書いてありました。 考えてみたもののわかりません。 考え方を教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 24の倍数の判定方法、それ以外でもOK
倍数の判定方法について、たとえば、 http://www004.upp.so-net.ne.jp/s_honma/number/multiple.htm が参考になります。 有名な話として、整数が３の倍数であることを判定するには、各桁を足した数が３で割れるかどうかを判定すればいいです。 ところで、そのサイトに書かれていない、24の倍数であるか否かの判定方法があれば教えていただきたいです。 そのサイトに書かれていないその他の数字でもOKです。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素数判定アルゴリズム内の剰余計算
今勉強している任意倍長精度整数の素数を判定するアルゴリズム内で x^q mod n という計算をするところがあるのですが、 正確に計算しようとすると計算量が膨れ上がってしまって 高速にできなくて困っています。 参考にしている文献に "x^q mod nの計算ではx^q mod nを正確に求める必要は無く、 x^q ≡ x^q' (mod n)となる x^q'でよい"という記述があるのですが どういう意味なのかよくわかりません。 どなたか教えていただけないでしょうか？
- 締切済み
- その他（プログラミング・開発）
- 10進数→n進法の変換 整数と小数の違いについて
整数の場合 27という10進数の数を2進法にしたい場合 2で割り、2のまとまりを作り余りが出来ると、それを1の位の値にする と、このようなことを繰り返すことで2進法の表記を作り上げると思います。 小数の場合 0.8125という10進数の数を2進法にしたい場合 2を掛ける(=0.5で割る) ことで 0.5のまとまりを作り、商の整数部分を0.5のまとまりと考え少数第一位の値とする と、このようなことを繰り返すことで2進数の表記を作り上げると思います。 と、ここまでは理解できたのですが なぜ整数では、小さい桁から、まとまりを作っていくのに 小数では大きい桁から、まとまりを作っていくことになるのでしょうか？ この疑問を自分の中でうまく言葉に出来ず、もどかしいので説明できる方がいましたら 私のレベルでも理解できるように説明していいだけないでしょうか。 よろしくお願いします。
- ベストアンサー
- 数学・算数