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

質問

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

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

回答No.1

guuman · ベストアンサー

0からp-1
を自乗してmodpして表にする
解が存在しない場合もある

補足

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

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

回答No.2

guuman

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

お礼

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