• 締切済み

素数判定について

stomachmanの回答

  • stomachman
  • ベストアンサー率57% (1014/1775)
回答No.1

回答になってないんですが... 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年）でヒットしますから、コピー入手可能でしょう。また、国内の何処やらの大学の修論発表会のリストにも載ってますから、その大学に問い合わせる手もあるかも。 　なお、他にも楕円関数論を使った高速な方法がある。もちろんこの分野の話を理解するには最低限代数学・ゼータ関数の知識は要求されるでしょうから、いっぱい勉強しないといけないですね。

この回答がついた質問に戻る
回答 全件
「コンピュータと素因子分解」和田秀男著 発行遊星社・発売星雲社 Ｉ…
  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 一桁の自然数の倍数の判定法

    一桁の自然数の倍数の判定法の中から一つ選び、証明せよ いくら考えても思い付きません 証明お願いしますm（_ _）m

  • 数学Ａ　場合の数の問題について

    数学Ａの場合の数の問題で、解き方がわからなかったので投稿しました。 「５桁の整数 ０，１，２，３，４を使って４桁の整数をつくる。 このとき、４の倍数になるのは何通りか」 という問題なのですが、ぜひ解法を教えていただきたいです。

  • 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進数の表記を作り上げると思います。 と、ここまでは理解できたのですが なぜ整数では、小さい桁から、まとまりを作っていくのに 小数では大きい桁から、まとまりを作っていくことになるのでしょうか？ この疑問を自分の中でうまく言葉に出来ず、もどかしいので説明できる方がいましたら 私のレベルでも理解できるように説明していいだけないでしょうか。 よろしくお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する
質問する