- ベストアンサー
最大公約数を求める
一般に、a,bが2^nくらいの整数であれば、最大公約数を求めるには、割り算も含めてn^3に比例した計算量が必要であるといわれている。しかし、これを素因数分解して求めると、素因数分解するのに、その数の平方根までの割り算が必要になるので、(√2)^nに比例した計算量が必要になる。 という説明があったのですが、”素因数分解するのに、その数の平方根までの割り算が必要になる”というのがよく分かりません。何故平方根まで割り算しないとならないのでしょうか????
- みんなの回答 (3)
- 専門家の回答
関連するQ&A
- ユークリッドの互除法で最大公約数を求める
<問題> n^2+2n+1とn+3の最大公約数になりうる値をすべて求めよ <解答> 整数a,bに対してa,bの最大公約数をg(a,b)とあらわす。 g(n^2+2n+1,n+3)=g(n+3,4) 4の正の約数は1,2,4であるから、g(n+3,4)として考えうるのも1,2,4である。 例えば、 n+3=5 すなわちn=2のとき、g(5,4)=1 n+3=6 ・・・ g(6,4)=2 n+3=8 ・・・ g(8,4)=4 となり、最大公約数として可能な数は1,2,4の3つの自然数である。 <質問> 「g(n+3,4)として考えうるのも1,2,4である。」 が必要条件であることはわかります。 その後、解答でなにがしたいのかよくわかりません。 なぜ例示しただけで「最大公約数として可能な数は1,2,4の3つの自然数である。」といえるのでしょうか? よろしくお願いします。 <思ったこと> 必要十分条件なら「g(n+3,4)として考えうるのも1,2,4である」場合、「4の正の約数は1,2,4である」であることを示すことになると思います。
- ベストアンサー
- 数学・算数
- 最大公約数について教えてください!
二つの整数m、n(m>n)の最大公約数をgとすると、mをnで割ったあまりとnとの最大公約数もgであることを証明せよ ただしm、nが互いに素であるとき、nとm-nも互いに素であることを使ってもよい 解説お願いします!
- 締切済み
- 数学・算数
- RSA暗号解読の素因数分解による方法について。
下記の通りで正しいでしょうか。: Microsoft Bing AI (= Bing Chat)生成人工知能の回答を、まとめ、且つ、補足しますと、次の通りです。 自然数 N を、√N (= Nの平方根)未満の自然数であって末位の数字が1,3,7,9のもので以て、割ってゆき、N を素因数分解する、という計算の、時間計算量は、O(Nの4乗根)です。 実際には、RSA暗号による暗号文の暗号は、巨大素数を2つ掛け合わせて作りますので、Nの平方根未満の自然数で、末位が1,3,7,9のもので、しかも、大きいもの順に取ったもので順に割っていけば、N の素因数分解は、時間計算量を、それよりも遥かに小さくして済ませらせます。 上記の様に、問題サイズ N に対する、N の4乗根のオーダーの時間を上界(この場合は、自然数の計算ですので上限)とする、普通の割り算の単純作業だけで、つまり、ごくごく短時間に、N の素因数分解が出来てしまいますので、RSA暗号も、いとも簡単に解けてしまう、ということです。
- ベストアンサー
- セキュリティ対策
- 高校数学 最大公約数,最小公倍数
問題. 3つの自然数45,63,n の最大公約数が9,最小公倍数が3150であるとき,nを求めよ なんですが,いろいろ素因数分解とかやってみて考えてみたのですが解けません. どなたか,解説してほしいです. よろしくお願いします..
- ベストアンサー
- 数学・算数
- 最大公約数について!
二つの整数m、n(m>n)の最大公約数をgとすると、mをnで割ったあまりとnとの最大公約数もgであることを証明せよ ただしm、nが互いに素であるとき、nとm-nも互いに素であることを使ってもよい はじめから解説をお願いします!
- ベストアンサー
- 数学・算数
- 最大公約数を見つけたい
C++初心者です。Visual studio 2005を用いてvisual C++の計算フォームアプリケーションを作りたいのです。 2ヶ所のテキストボックスに整数を入力させ、「実行」ボタンを押すとその2つの整数の最大公約数を出力させたいのですが、どうも上手くいきません。 できるだけ簡素なコードで最大公約数を見つけるにはどうすればいいでしょうか? どうかよろしくお願いいたします。
- ベストアンサー
- C・C++・C#
- 素因数分解で最大公約数、最小公倍数を求める方法
例えば 24と18を使って素因数分解すると 2 |24 18 3 |12 9 4 3 となって共通の素因数をかけて6が最大公約数 共通の素因数と、共通の素因数を抜いた数を掛けて 72が最小公倍数 というふうに求めますが これは素数である必要はあるのですか? 別に 6| 24 18 4 3 として求めても同じではないのですか? 下の方法で何か困ることはあるのでしょうか?
- ベストアンサー
- 数学・算数