- ベストアンサー
mod p の計算
- みんなの回答 (5)
- 専門家の回答
質問者が選んだベストアンサー
p ≠ 1 のときに「2 が原始根」とは限らないからね. 例えば p=7 だと 2^3 ≡ 1 だから 2 は原始根にならない. 原始根を r とおいて, 任意の n (1, 2, ..., p-1) が r^t (t = 0, 1, ..., p-2) と書ける (そして n と t が 1対1 に対応する) ことを使う.
その他の回答 (4)
- Tacosan
- ベストアンサー率23% (3656/15482)
本当に原始根の意味を理解できているのかなぁ.... 例えば「pが素数なら1,2,3,・・・,p-1が原始根になる」ってどういう意味? 1 が原始根になりえないことは分かるよね? 「原始根が存在する」ことを認めれば, 元の式で 1, 2, ..., p-1 を原始根のべきで表せばいい. そうすると結局等比数列の和の形になって, 和の公式を使えば値が求まる.
お礼
有難うございます。 pが2でないときは、2が原始根の1つなので、それを用いて、もう一度自分なりに考えてみたいと思います。
- Tacosan
- ベストアンサー率23% (3656/15482)
書くこと自体はかまわないけど, その前に何がどう分らない?
お礼
何度も大変丁寧にご返事を頂き有り難うございます。 原始根の意味はわかり、Z/pZにおいては、pが素数なら1,2,3,・・・,p-1が原始根になることはわかります。 そのあと、具体的にどのように計算したらよいですか? 最初の具体的な式変形と、主要なアイデアがあれば、残りは自力でできると思います。
- Tacosan
- ベストアンサー率23% (3656/15482)
あ, ごめん. #1 は大嘘. というわけでやり直し. p は奇素数じゃないと式の意味がないのでそれを仮定する. と, 原始根を考えることができてごにょごにょすると左辺は 0.
お礼
ご返事を頂き、有り難うございます。 大変恐縮ですが、あまり知識がなく、あと少しだけ、子細をお教え頂けないでしょうか?
- Tacosan
- ベストアンサー率23% (3656/15482)
p が奇素数なら左辺は 1, 2, ..., p-1 の置換の和だから 0.
関連するQ&A
- √5≡y (mod p )が解を持つための条件は?
素数p に対し、√5≡y (mod p ) を 5≡y^2 (mod p )と定義したとき、√5≡y (mod p )が解を持つための必要十分な条件は p≡±1(mod 5)らしいのですが本当でしょうか?(必要あるいは十分だけ?)正しいときはどのように(あるいはどのような方針で)証明したらいいのでしょうか。また、参考文献があれば教えてください。
- ベストアンサー
- 数学・算数
- 数学、mod pのk乗
xの2乗≡a(mod pのk乗)が整数解を持てばxの2乗≡a(mod pのk+1乗)も整数解を持つ pは素数、kは0以上の整数、aは整数 この証明についての質問です。 xの2乗≡a(mod pのk乗)の整数解をx1とすると x1の2乗-a=(pのk乗)s sは整数 x2=x1+(pのk乗)tとおくと x2の2乗-a=(x1+(pのk乗)t)の2乗-a =x1の2乗+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗)-a =(x1の2乗-a)+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗) =(pのk乗)s+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗) =(pのk乗)(s+2(x1)t+(pのk乗)(tの2乗)) ここまではいいのですが s+2(x1)t≡0(mod p)となるようにtを選ぶことができるというのがわかりません。 ここを通過すればpのk+1乗を約数にもつことになって証明が終わります。
- ベストアンサー
- 数学・算数
- mod255の計算
こんにちは。 今日はmod255の計算について困ったことがあり、質問しました。 私は今、mod255の計算をする回路を作っています。 mod255とはある値を255で割ったときの余りを求めることですよね。 しかし、回路ではあまり除算(回路の性質上、逆数を取って乗算する)を使いません。 理由は、計算に時間がかかることと、回路規模がが大きくなるため。 ある値が255以上か判定してから順次255を引くことも考えましたが、動作が不規則なため使っていません。 そこで、私はmod255を除算を使わず、減算で実現しようと次のような計算法を考えました。 例、239+157をmod255する場合。 239+157=396を2進数に変換すると 11101111 +10011101 ------------ 110001100 ここで、計算結果の右から9番目の1を一番右に移動して加算すると 10001101になります。 これを10進に変換すると141になります。 よって、396-255=141となり396をmod255ができていますよね。 これで、問題解決だと思ったのですが、 ある値が511でこの計算をすると結果が10000000となり 256になってしまいます。 このことから考えて、この計算法は万能ではないみたいです。 この計算法のどこを改善するとmod255を計算できるようになるのでしょうか? また、皆さんなら、どんな方法でmod255を実現しますか? よろしく、お願いします。
- ベストアンサー
- 数学・算数
- modの計算方法について
下記ホームページで紹介されているmodの計算方法について教えてください。 http://c4t.jp/introduction/cryptography/cryptography04.html (1)「素数」を法とする世界では、Xn mod 素数=X という、元の数字と答え(X)が共に同じとなる「n」の値を「素数」から計算することができます。というのがありますが、例をあげて説明していただけないでしょうか? (2)RSA暗号の概要で暗号分456はどのように計算するのでしょうか? よろしくお願いします。
- 締切済み
- 数学・算数
- modの計算について
例えば、 11239*d = 1 (mod40872)においてdを求めるにはどうしたらいいのでしょうか? 計算サイトなどの紹介でもかまいません。 これって普通の電卓と手計算だけでも計算できるものなのでしょうか?
- ベストアンサー
- 数学・算数
- 18783^3323 (mod20227)の計算
暗号化の計算を必要としています。 18783^3323 (mod20227) のような大きい桁数を計算できる サイト、またはフリーのアプリケーションを教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- modの計算について
modの計算式ax≡b (mod c)の時xを求めよのような問題は 解く上で何か良い方法というか手順みたいなものはあるのですか?いつも運で解いています。検算の仕方も知っているのですが、解くときはいつも試行錯誤状態で困ってしまっています。 何か計算する上でこれを頭の片隅においておいたらすらすら解けるみたいな物があればご教授してください。 お願いします。 例えば80x≡339 (mod 583)はx≡201となり何とか とけました。問題を見た瞬間に解ける方法とかないんですかねぇ。
- 締切済み
- 数学・算数
- 2^10≡1 mod pを満たす素数p
「2^10≡1 mod pを満たす素数pをすべて求めよ」という問題ですが、 2^10-1=1023=3・11・31より pは3, 11, 31で正しいでしょうか?他にもあるでしょうか? 少し自信がないので質問しました。
- 締切済み
- 数学・算数
お礼
p=7のときは、3が原始根の一つであり、それを用いると、(項の順序を並びかえて、) 与式=(3^(-1))^k+(3^(-2))^k+・・・+(3^(-2))^k =(3^(6k)-1) / (3^(6k)(3^k-1)) ≡ 0 となることがわかり、他のpに対しても、原始根の存在を認めれば、同じような計算で題意の成立を確かめることができました。 いろいろとたくさんのご助言を頂き、とても感謝しています。 有り難うございました。
補足
すみません。上のお礼の欄の2行目は、与式=(3^(-1))^k+(3^(-2))^k+・・・+(3^(-6))^kの間違いです。