Prev: Scalar methods in the XY plane.
Next: sphlib-2.1
From: jeff on 23 Jun 2010 18:55
I looked at Garner's. No argument that the algorithm is what i
referred to as the "2nd" method. I called it 2nd because that's how
it's mentioned in the PKCS1 spec.
My question was more on the mathematics of it. How did Garner come up
with this? Obviously there must have been some mathematical reasoning
behind it.
I have to look at KG's post more carefully because I still don't get
it.
thanks all
jeff
From: Bryan on 23 Jun 2010 20:44
jeff wrote:
> I looked at Garner's. No argument that the algorithm is what i
> referred to as the "2nd" method. I called it 2nd because that's how
> it's mentioned in the PKCS1 spec.
> My question was more on the mathematics of it. How did Garner come up
> with this? Obviously there must have been some mathematical reasoning
> behind it.
> I have to look at KG's post more carefully because I still don't get
> it.

Break it down. First we need:

m mod p = c**dp mod p
m mod q = c**dq mod q

So substitute those into the expression to get:

m' = (m mod q) + ( ( mod p - m mod q) * qInv mod p).q

Now see if you can convince yourself:

m' is congruent to m mod p
m' is congruent to m mod q
0 <= m' < p*q

Then the CRT gives you m' = m. So that's the mathematical reasoning on
why it works. As to how Garner came up with it, I can't really say.
Hard work? Cleverness?

--
--Bryan
From: Wolfgang Ehrhardt on 24 Jun 2010 12:31
On Wed, 23 Jun 2010 15:55:41 -0700 (PDT), jeff <dude000(a)gmail.com>
wrote:

>I looked at Garner's. No argument that the algorithm is what i
>referred to as the "2nd" method. I called it 2nd because that's how
>it's mentioned in the PKCS1 spec.
>My question was more on the mathematics of it. How did Garner come up
>with this? Obviously there must have been some mathematical reasoning
>behind it.
>I have to look at KG's post more carefully because I still don't get
>it.
>thanks all
>jeff
Knuth, Seminumerical Algorithms, 3rd ed, Ch. 4.3.2 Modular Arithmetic,
(together with exercises 7..9) gives a rather detailed description.

First  |  Prev  | 
Pages: 1 2
Prev: Scalar methods in the XY plane.
Next: sphlib-2.1