• 締切済み

素数判定アルゴリズム内の剰余計算

今勉強している任意倍長精度整数の素数を判定するアルゴリズム内で x^q mod n という計算をするところがあるのですが、 正確に計算しようとすると計算量が膨れ上がってしまって 高速にできなくて困っています。 参考にしている文献に "x^q mod nの計算ではx^q mod nを正確に求める必要は無く、 x^q ≡ x^q' (mod n)となる x^q'でよい"という記述があるのですが どういう意味なのかよくわかりません。 どなたか教えていただけないでしょうか？

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.3

ん～, 「繰り返しごとにやると計算量が増えてしまい」の意味が今一つわからない (ビット数が減るので x^q を計算してから n で割るよりは高速なはず) んですけど.... とりあえず, 「現在どのように計算しているのか」を挙げてもらえればヒントになるかもしれません.

  • rabbit_cat
  • ベストアンサー率40% (829/2062)
回答No.2

フェルマーの小定理（オイラーの定理）は使ってますか？ http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

どうせ x^q は一発で計算できないわけです. 言い替えれば何らかの処理を繰り返して x^q を計算するんだから, その繰り返しごとに mod n を計算すれば出てくる数値は必ず n 未満になりますよね.

dentu-taro
質問者

お礼

回答ありがとうございます。 qが９桁前後で、繰り返しごとにやると計算量が増えてしまい 高速にできなくて困っています

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. その他（プログラミング・開発）

関連するQ&A

  • 剰余の問題について

    基本情報技術者試験の問題にて、 pを2以上の整数とする。任意の整数nに対して、 n=kp+m (0 <= m < p) を満たす整数kとmが一意に存在する。このmをnのpによる剰余といい、 n mod pで表す。（-10000）mod 32768に等しくなるものはどれか。 ア -(10000 mod 32768) イ (-22768)mod 32768 ウ 10000 mod 32768 エ 22768 mod 32768 という問題があります。 この問題の解答は「エ」となるのですが、 解き方がどうしても理解することができません。 解説では （-10000）mod 32768と等しいのは 32768+(-10000)=22768から 22768mod32768となる。 と書いてあるのですが、このように解答していく プロセスがさっぱり見えてきません。 この解法の仕方をレクチャーしていただけないでしょうか。

  • アルゴリズム

    アルゴリズムの勉強をしていて、時間計算量に関する問題があり、解いたのですが、解答が載ってなく困ってます。正誤の判断と、もし間違っているなら、何が間違っているのかを教えて頂けると助かります。 ある問題において、大きさ(データ量)nに対して、アルゴリズムA、B、Cの時間計算量が、それぞれn、n^2(nの2乗)、2^n(2のn乗)であるとする。 (1)アルゴリズムAを用いて10秒間にn=100の問題が解けた。20秒かけるとき扱える問題の大きさnの値を求めよ。 解) n=100*2 =200 (2)ある計算機を用いてアルゴリズムBで10秒間にn=100の問題が解けた。100倍早い計算機を用いたとき、10秒間に扱える問題の大きさを求めよ。 解) 求める問題の大きさをxとおくと n=(100^2)*100 =10000*100 =1000000 (3)アルゴリズムCを用いて1時間にn=20の問題が解けた。n=40の問題を解くのに何時間かかるか。 解) 2^40=(2^20)*(2^20) =1*(2^20) =2^20[時間]

  • 剰余の法が大きい場合のアルゴリズム

    プログラミング等でよく"x^n(mod m)を解け"といった問題がよく挙がりますが、法"m"が 大きい場合については触れているものが少ないので質問させていただきます。 例えば単純に除法で求める場合、"x^n"については展開できるので、何でもよい数として 簡単に"x"とおくと、"x/m"をニュートン法で求め"x-round(x/m)*m"で余を求める、という ような感じになります。ここで"m"は"1024bit"程度の大きい数を想定しています。よい アルゴリズムがあれば教えてください。

  • 2進アルゴリズムの時間計算量

    ベキ乗計算を2進アルゴリズムで解いた場合の時間計算量を求める方法を教えてください。 x^nの時の時間計算量でn=2,3以外の時でn=2p,2p+1の時で場合わけして(pは整数)数学的帰納法で解いてあるのは見た事はあるのですが、どこからその仮定を持ってきたのか見当がつきません。 どうかお願いします。 n>3のときの時間計算量kは　k<=(2*log(n))-1 となっていました。

  • 中国剰余定理　3数

    余りが条件式を満たすがわからないので質問します。 p,q,rどの2つをとっても、互いに素な自然数とする。a,b,cを任意の整数とする。このとき、　x≡a mod(p),x≡b mod(q),x≡c mod(r) を満たす整数ｘが、0からpqr-1までの間に1つ存在する。この定理の証明は、 (qr)s≡1 mod(p),(rp)t≡1 mod(q),(pq)u≡1 mod(r),を満たすs,t,uを求めることから始まります。sであれば、(qr)s+py=1・・・(1)という１次不定方程式を解くことで、得られます。q,rがpと互いに素であるから、qr,pが互いに素なので(1)を満たすs,yは存在します。同様にt,uが得られます。x=a(qr)s+b(rp)t+c(pq)u・・・(2)とおけば、xは条件式を満たします。(2)をｐで割った余りは、a*1+0+0=aとなります。qで割れば余りb,rで割れば余りc,となります。ここからがわからない箇所です。このxをpqrで割った余りも条件式をみたします。 まず、自分の計算では、x=a(qr)s+b(rp)t+c(pq)u=pqr{as(1/p)+bt(1/q)+cu(1/r)}となり余りが出ません。そして条件式x≡a mod(p),x≡b mod(q),x≡c mod(r) を満たしているとも思えません。どなたか自分の考えの間違いを教えてください。お願いします。

  • 平方根を求めるアルゴリズムについて・・・

    次の文章の平方根を求めるアルゴリズムの疑似言語での記述の仕方を教えてください。 変数名等は任意に設定して良い。またアルゴリズムは任意の正数の平方根を求められるようにすること。求める精度は１０－８とする。 （√のない計算機） Ｔ君はある資格試験を受験しに行った。その試験では、電卓を持ち込むことができる。当然に計算問題が出題され、計算した結果、答えは√１４とでた。回答しようとしたところ、選択肢は小数で書いてある。ところが平方根を計算しようと思ったら√キーがない電卓だった。 どうしよう・・・ まず４×４＝１６であるから、とりあえず１４を４で割ってみた。 １４÷４＝３．５ 言わずもがなであるが、√１４は二乗すると１４になる正の数のことである。 √１４は４と３．５の間にあることが分かる。 とりあえず、今度は１４を４と３．５のあいだの３．７５で割ってみる。 １４÷３．７５＝３．７３３３３３３３３３ ということは√１４は３．７５と３．７３３３３３３３３３のあいだにあるわけだから同じように１４を３．７４１６６６６６７で割ってみる。 １４÷３．７４１６６６６６７＝３．７４１６４８１０７ これで√１４が小数点第４位までが求められた。あとはこの作業を繰り返せば、徐々に精度は良くなるはずである。

  • N個の整数の並び替えるアルゴリズム

    N個の整数1,2,3,...Nから任意のM個（M < N )を取り出すのですが、重複はダメという場合、どのようなアルゴリズムがあるでしょうか。重複ありなら、Nまでの一様乱数を発生させて整数化して取り出すことは可能です。今回は重複なしです。重複があったらやり直して重複なしになるまでやり続けるというのはダメだなと思っています。 データ処理言語のRはコマンド１つのようですが。言語はFortranなのですが、アルゴリズムのレベルだとどれでも同じと考えています。よろしくお願いします。

  • 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 合同」の意味で使用しています。) -----終了----- これはなぜなのでしょうか？　なぜ公約数が見つかるのでしょうか？ アドバイスよろしくお願いします。

  • 単位計算のアルゴリズム

    プログラム中で自動的に単位換算を行わせたいと思っております つまり、例えば [MPa] = 1000[kPa] = 10[bar] = 1000000[N/m2]・・・(1) [bar] * [m2] = 100000[N]・・・・・・・・・・・・・・・・・・・・・(2) など、普段人間が行う任意の単位変換と単位の計算をプログラムが自動で行うようなアルゴリズムを求めております。 具体的にはcsvファイルなどにデータを蓄積して（そのデータには単位を添える）、そのデータを計算させ（この時、数値の計算以外に単位のチェック＆計算を行わせたい）、出力することを想定しております。出力される数値は単位の換算の影響を受けて（例えば(2)であったら、数値は100000倍）される）出力したいです。 単位の文字列を一度すべてMKSA単位系（等）の文字列に変換する一覧表を作って、出力するときに、再変換を行えば（ここもどうやるのかわかりません）いいかとも考えておるのですが。 ご存知の方、アイデアをお持ちの方、どうぞよろしくお願いいたします。

  • 有効数字　　特に、約分・計算順序について

    とある問題で、 　　　 9.8 × ( 24 × 60 × 60 )^2 　　━━━━━━━━━━━━━　　　 ←÷の分数表記です 　　　4 × ( 3.14 )^2 × 6.4 × 10^5 という数の計算がありました。　どう計算するのがもっとも精度がいいのでしょうか？ ※　有効数字は　9.8　 ２桁　 　　　　　　　　　 　　3.14　３桁 　　　　　　　　 　　　6.4　 ２桁 　　　　　　　　　　　 24 × 60 × 60 は正確な値としてよい。　 　　　　　　　　　 　 4 　　は正確な値としてよい。 なお、値の精度は、誤差○.○～□.□があるから、ではなく、桁数のみで判定してください。（大学入試的な意味で） ちなみに、手元の答えでは≒2.9 × 10^2となっています。私は初め2.3 × 10^2になりました（←計算間違いではなく　泣　） 計算途中の切り捨て、約分、計算の順序、四捨五入、等、できるだけ詳しく計算過程を記述してほしく思います。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する