a=b*b(mod p)の式におけるbの求め方

表題のとおり、
a=b^2(mod p)
p = m * n
の式において、m,n,p,aが既知の場合に、
bの計算方法を教えていただけないでしょうか？

よろしくお願いいたします。

No.1 ベストアンサー 回答者： guuman 回答日時： 2007/04/21 07:44

0からp-1

を自乗してmodpして表にする
解が存在しない場合もある

この回答への補足

確かに答えは計算できますね。
ただ、この方法だとpの値が何十桁になるような数だと、
計算することは困難になります。
http://pgp.iijlab.net/crypt/rsa.html
上記ページの「鍵の生成」の項のような別の解答方法を
誰かご存じないでしょうか？

最後に、guumanさん解答ありがとうございました。

補足日時：2007/04/21 12:01

No.2 回答者： guuman 回答日時： 2007/04/21 13:32

RSA暗号の鍵を見つけることが困難な理由は

素数の積ｐ・ｑが与えられたときにその桁数が大きいとｐを求める計算が膨大になるから
それに比べて今回の場合には表を作るのはPCで即座にできる
１０００００桁であろうが私が持っている家庭用のPCでも30分もかからないと思われる
ａを与えてｂを返すCプログラミングを補足せよ

この回答へのお礼

ありがとうございました。
説明していただいた方法で計算したいと思います。

お礼日時：2007/04/26 02:49