« Adobe Reader脆弱性を修正 | トップページ | 情報収集はブログだが »

2007/10/24

拡張ユークリッドと一次合同式

拡張ユークリッドというのは正整数(a, b)があるとして、不定方程式 ax + by = gcd(a, b) の(x, y)を求めるアルゴリズムであったと思います。

今私が考えている問題は、「gcd(a, b) = 1であるならば、ax ≡ 1 mod b の解x を返す」というものです。この一次合同式は「ax - 1 が b で割り切れる」というものです。単にこの解xを求めること自体は難しくもないのですが、正直なところ、よく分からないわけです。

解xは負の整数でもいいのか、不定方程式の解xとは違うものなのか(場合によっては同じ値になる)など疑問が湧いてきます。

うまく説明できる人がいたら教えてもらいたいものです。

|

« Adobe Reader脆弱性を修正 | トップページ | 情報収集はブログだが »

Algorithm」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/222903/16863668

この記事へのトラックバック一覧です: 拡張ユークリッドと一次合同式:

« Adobe Reader脆弱性を修正 | トップページ | 情報収集はブログだが »