[13801] in Cypherpunks
Re: Rabin decryption
daemon@ATHENA.MIT.EDU (Norman Hardy)
Tue May 17 02:13:02 1994
Date: Mon, 16 May 1994 23:09:24 -0800
To: nobody@rebma.rebma.mn.org, cypherpunks@toad.com
From: norm@netcom.com (Norman Hardy)
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.
