Re: Rabin

[Karl Lui Barrus <klbarrus@owlnet.rice.edu>]

-----BEGIN PGP SIGNED MESSAGE-----

About Rabin (and you're welcome, Mr. Anonymous!)

Well, I looked at Schneier on p. 290 and I have to confess I'm
puzzled.  I'm sure these formulas weren't invented out of this air,
but I'm not sure why one of them must equal M.  (In the example worked
none are equal to M).  I would bet that this is a typo in the book;
check the errata sheet

I think the formulas are trying to say the following facts:

For the kinds of problems we are considering, 
If m1 = CRT(n,p,q,x1,x2)
   m2 = CRT(n,p,q,x1,q-x2)
   m3 = CRT(n,p,q,p-x1,x2)
   m4 = CRT(n,p,q,p-x1,q-x2)

then m4 = n - m1, m3 = n - m2

So you really don't need to do CRT four times; twice is good enough.

(In the example, m1 = 71, so m4 = 77 - 71 = 6
                 m2 = 50, so m3 = 77 - 50 = 27)

Karl Barrus
klbarrus@owlnet.rice.edu

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLdhB04OA7OpLWtYzAQEV3wQAjgcz1AI1ufFfzUpQmh35E0xbeD+PB4FV
mc72TL0v7lvjeK4aiGwEK8j/1vtzvw+1QCkSRTY6ATElx4HnskdV0yp4CT8WycPC
X/QmeYkqOr+Q4ed0dXgvjYOO++4FOBaqQUqRaTLLgB/BKndfDVbM683MGxtbLOSe
gCi3SP86CuU=
=REkP
-----END PGP SIGNATURE-----