- ベストアンサー
拡張ユークリッド互助法
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
そのものの解説をWEB照会できるものを上げます。本当の学習テーマは暗号理論との関係かな、アルゴリズムかな。 http://www.rkmath.rikkyo.ac.jp/~kida/euclid.htm http://www.ss.u-tokai.ac.jp/~kikyo/calg/gcd.html http://kako.ics.nara-wu.ac.jp/book/reduce/node67.html http://www.ss.u-tokai.ac.jp/~kikyo/frsemi/frsemi.html http://www.mew.org/~kazu/sut/2001-2nd/8.html http://pgp.iijlab.net/crypt/rsa.html http://www002.upp.so-net.ne.jp/mamewo/crypt.html 合同式における逆数 http://wwwmi.cias.osakafu-u.ac.jp/~takahasi/souken/rsa3.html http://kako.ics.nara-wu.ac.jp/book/reduce/node66.html
その他の回答 (1)
- MovingWalk
- ベストアンサー率43% (2233/5098)
「ユークリッド互助法」じゃなくて「ユークリッド互除法」ですよね。 こちらは参考になりませんか？ http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/index.html
関連するQ&A
- ユークリッドの互助法
ユークリッドの互助法を最初に知ったのはいつのことですか？ なぜこんなことを聞くかというと、高校までに授業で習った記憶がないからです。 重要なので中学校くらいで習っててもおかしくないかなと。 学校によりけりなんでしょうか？
- ベストアンサー
- 数学・算数
- ユークリッドの互助法って何でしょか？
学校の問題で、その方法を再帰呼び出しを持って実践するプログラムを作りなさい、と言うのが出て、そのまずユークリッドが分からないで八方塞がりｉｎｇです。 余り知識が無いんで簡潔に説明して戴けたら、これ、幸いであります。
- ベストアンサー
- Visual Basic
- 未知数があるとき ユークリッド互助法 適用 方法
問題 8n+4と7n+1の最大公約数が5になるような100以下の自然数nはいくつあるか？ 解答 ユークリッドの互助法を使う 8n+4と7n+1の最大公約数＝7n+1とn+3の最大公約数＝n+3と20の最大公約数 さらに……… という問題と解答なのですが、疑問があります （以下 自然数～ を 自～ と表記します） ユークリッドの互助法とは 自aと自bの最大公約数＝ (自a＝自b×自c＋自d ∧ 0≦自d＜自b ⇔ 自b＝～ ∧ 自d＝～)で定まる自dの値 と 自b の最大公約数 が成り立つという事実を使って2数の最大公約数を、より簡単な2数の最大公約数に還元し もとめる方法ですよね？ そうなるとこの場合にどのように適用していいのかわかりません。 8n+4と7n+1の最大公約数＝7n+1とn+3の最大公約数 の部分は 8n+4＝(7n+1)×自c＋自d ∧ 0≦自d＜7n+1 ⇔ 自ｃ＝1 ∧ 自ｄ＝n+3 で自dが一通りに定まるのがわかるのですが 7n+1とn+3の最大公約数＝n+3と20の最大公約数 の部分は 7n＋1＝(n+3)×自d+自d ∧ 0≦自d＜n+3 ⇔ 自c＝ ∧ 自d＝ となるので 自ｃが7以下であることはわかりますが、自cは1.2.3.4.5.6のどれでもokですよね そうすると自ｄが一通りに定まらず、どうやっていいのかわかりません
- ベストアンサー
- 数学・算数
- ユークリッドの互徐法
p と q は素数とします。 1=gcd(e,(p-1)(q-1)) を満たす最小のe(e>1)はどうやって出せばいいですか。 まだユークリッドの互徐法の使い方に慣れていないので、どうやればいいかわかりません＾＾； たとえば、p=5 q=7のときどうすればいいでしょう。
- ベストアンサー
- 数学・算数
- 互助掛金と互助控除について教えてください。
互助掛金と互助控除について教えてください。 私の夫は水道局で働いてますが、給与明細の「互助掛金」と「互助控除」について、夫はよくわからないと言っているので、教えてください。
- ベストアンサー
- その他（社会）
- ユークリッドの除去法アルゴリズム
最大公約数を求める際ユークリッドの除去法を使ったアルゴリズムを考える場合、計算量はO(log max{x,y})となる理由を教えて下さい。 簡単な擬似コードも教えてもらえるとありがたいです。
- ベストアンサー
- C・C++・C#
- ユークリッド幾何学とは？
ユークリッド幾何学とは何なのでしょうか？ わかりやすく教えてください。 また、非ユークリッド幾何学とは ユークリッド幾何学と何が違うのでしょうか？
- ベストアンサー
- 数学・算数
