17 Dec
2003
17 Dec
'03
11:17 p.m.
At 22:09 5/15/94 -0500, nobody@rebma.rebma.mn.org wrote:
How do you do Rabin decryption? ... Anybody know the right way to do square roots mod a Blum integer?
Page 545 of Knuth's "Seminumerical Algorithms" gives a method of finding the square root modulo a prime. It is efficient but non-trivial to program. Incidently its worst case running time is as big as the number (actually bigger) but its expected time is something like (nog n)^2. My most recent errata list for Applied Cryptography does not amend page 289. I will mail you that list if you don't have it.