Re: squaring
- From: "¬a\\/b" <al@xxx>
- Date: Wed, 28 Sep 2005 08:52:58 GMT
On 19 Jul 2005 23:13:54 -0700, asetofsymbols@xxxxxxxxx wrote:
>in the book "Handbook of Applied Cryptography by A. Menezes, P. van
>Oorschot and S. Vanstone" i have find this algorithm
>-------------------------------------------------
>14.16 Algorithm Multiple-precision squaring
>INPUT: positive integer x = ( x_(t-1), x_(t-2), ... ,x1, x0)b.
>OUTPUT: x * x = x^2 in radix b representation.
>1. For i from 0 to (2t - 1) do: w_i=0.
>2. For i from 0 to (t - 1) do the following:
> 2.1 (uv)b=w_(2i) + x_i * x_i, w_(2i)=v, c=u.
> 2.2 For j from (i + 1) to (t - 1) do the following:
> (uv)b=w_(i+j) + 2*x_j * x_i + c, w_(i+j)=v, c=u.
> 2.3 w_(i+t)=u.
>3. Return((w_(2t-1), w_(2t-2), ... w_1, w_0)b).
>
>14.17 Note (computational efficiency of Algorithm 14.16)
>(i) (overflow) In step 2.2, u can be larger than a single-precision
>integer. Since w_(i+j)is always set to v, w_(i+j) <= b - 1.
>If c <= 2(b - 1), then w_(i+j) + 2*x_j*x_i + c =
>(b-1)+2(b-1)^2 +2(b-1) = (b-1)(2b+1), implying 0 <= u <= 2(b-1). This
>value of u may exceed single-precision, and must be accommodated.
>----------------------------------------------
Is it possible that book can have an error in "14.16 Algorithm
Multiple-precision squaring"? ... yes
The error was in the book (and so in my implementation of it)
but i have correct it
>Do you think I have make something illegal in write this in a ng?
>If i implement this algorithm in assembly do you think i have to write
>a copyright note for say where i have find it?
.
- Prev by Date: architectures which satisfy Popek and Goldberg virtualization requirements?
- Next by Date: Re: Release of RosAsm V.2.025a
- Previous by thread: architectures which satisfy Popek and Goldberg virtualization requirements?
- Next by thread: x86 Hardware Trivia Question
- Index(es):
Relevant Pages
|
