• 締切済み

量子コンピュータを用いた素因数分解

量子コンピュータを用いた素因数分解の方法を教えてください。 ある数Aの素因数分解を行うときに、Aより小さい数全ての重ね合わせのような状態で割る事でその全ての余りを出し、0となった物を取り出すと聞いたのですが、これだと、余りが0でない時と0の時の違いを全てチェックし、どれが素数かを調べる必要が出てしまいます。 実際に採用されたアルゴリズムや方法ではどのような方法をとっているのでしょうか？ カテゴリーがどれか分かりませんでした。 カテ違いでしたらすいません。

みんなの回答

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

> Aより小さい数全ての重ね合わせのような状態で割る事でその全ての余りを出し、0となった物を取り出す 　いや、そういうやりかたじゃありません。「Shor 因数分解」で検索してみてはいかが？ 　納得するには、量子の混合状態（状態の重ね合わせ）についての理解の他に、因数分解（や素数判定）の確率的アルゴリズムに関する知識だとか、フーリエ変換に関する知識も必要ですが。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • すばやく素因数分解する方法は？

    「暗号解読」（サイモン・シン（著）青木薫（訳） 新潮社）という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数（合成数）を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法（素因数分解）を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法（アルゴリズム）を知りたいです。

  • 素因数分解

    X４乗+４を素因数分解してください。また文字のついているものを素因数分解する方法を教えてください。

  • 素因数分解

    全ての自然数は、素因数分解出来るのでしょうか? また、出来る場合は、それが証明されているのでしょうか?

  • 素因数分解について

    多分、すごく初歩的な質問だと思いますが、次のことは正しいですか？ １と素数以外の整数は、すべて素因数分解できる。 よろしくお願いします。

  • 素因数分解の問題

    久々に素因数分解の問題を解いてみようとしたところ、いきなり躓いてしまいました。 二桁の整数ｎに１６８をかけると、ある数の二乗になりました。この整数ｎはいくらになるかという問題です。 １６８を素因数分解し、ｎ×１６８＝ｎ×２＾３×３×７となることは分かります。 これから先、どのように組み立てて解けばよいのか分かりません。 解説では、各素数が偶数個になるように解くと書かれており、ある数の二乗になるため、 ｎ＝２×３×７×ｍ＾２となっていました。 どうしてこのような式なるのですか？ A＝A＾p×ｂ＾q×c＾rとなっている時、各指数がすべて偶数（２の倍数）なっていれば、Aは何かの二乗になることは確かめてみました。

  • 素因数分解

    素因数分解はわらずとも解に至ります。それをどうしたら、みなさんにお伝えできるか 数学教育協議会等にも顔を出したり、ずいぶん前から、たくさんの新しい事を創り、双子素数などは、 ペア素数の定理として、すべて一括に実証されます、素因数分解などは、桁数は関係ありません。素因数分解の世界記録、現在NTT総合研究所とドイツのボン大学とスイスのローザンヌ大学とフランス、オランダの研究機関が共同で３年もかかってしまう、わずか２３２桁です、これは、すべて、割るがベースにある からです。割るを、使わずとも、解に至ります。どうして、理解しようとしないのか、わかりません。 古代バビロニアの人々ですらできたのです。４０００年も前です、基本は考え方です。難しく、難解な高等数学入りません。平方根を厳密解を求める、つまり、開平がちゃんと、理解でき、従来の２個ずつ、開くことを拡張して、８個、とか、１６個いっぺんに開く方法もあるので、そういう工夫をすれば、よい。 あとは、大きい数値を、扱えるかどうかです。つまり素因数分解は、one-way-function出はありません。２３２桁も数分でしょう。

  • 脳と量子コンピュータ

    NP問題を多項式時間で「直感的に」解けてしまう人がいたとします。 その場合、人間の脳は、量子コンピュータだと言えるでしょうか？ また、そういう実例というのは存在するでしょうか？ 私は、インドに「素因数分解を瞬時にする双子」がいるとかいううわさを 耳にしたことがありますが、出典は分かりません。 ※1　量子コンピュータの定義は適当にしてくださって結構です。 明らかに間違った定義は困ってしまいますけど＾＾； ※2　カテ違いのような気がしますが、 「NP問題」の説明にあまり自信がなかったので、 「数学」にしてみました。 ※3　回答者同士の議論、まったくもってかまいません。 もちろん、中傷・誹謗などは禁止です。

  • 素因数分解をこの問題でどう使うのか？？

    問題 「a、b、cは自然数とする。 2^3a×3^2b×5^cで表せる６桁の数があり、その中央の４桁は０７３６であることがわかっているとき、a,b,cの値を求めよ。」 これは中学生の問題です。私は家庭教師をしているのですが、情けないことにこの問題がわかりません。この問題のテーマは「素因数分解の利用」ということなのですが、どう素因数分解を利用するのかわかりません。 ～私の解法（素因数分解の利用なし）～ 3^2b＝９の倍数なので、９の倍数の性質と２×５＝１０を利用して６桁の数が「２０７３６０」とわかったのですが、素因数分解を利用していないので、この解法ではないと思います。そもそも９の倍数の性質を知らないと解けない問題自体見たことがありません。 素因数分解を利用する解法がわかる方はぜひ教えて下さい。お願いします。

  • 素因数分解の一意性？？？？？

    m,n,p,qをすべて互いに素な自然数とした時に、 2^n・p^m=q^mにおいて、 素因数分解の一意性より、ｑは2の倍数である。 素因数分解の一意性ってどういうことなのでしょうか？

  • 素因数分解！？

    xは自然数でx^2=736164のときxを求めよ。という問題なのですが、素因数分解してくと2、2、3、3の順で分解できるのはすぐ気づきます。しかし20449でとまってしまいます・・。なんとか143で分解できると気づいてx=858と答え出せたのですが、もっと上手い解き方ありますか？あるいは、2～3桁の素数の積を一瞬で見分ける方法はありますか？わかる方いましたらお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する