Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
- From: David Thompson <dave.thompson2@xxxxxxxxxxx>
- Date: Tue, 10 Jun 2008 04:36:36 GMT
On Fri, 30 May 2008 02:36:56 -0700 (PDT), Christian Siebert
On 29 Mai, 20:09, Le Chaud Lapin <jaibudu...@xxxxxxxxx> wrote:<snip choosing factors to give exactly n-bit N>
On May 29, 3:14 am, Christian Siebert <iB...@xxxxxx> wrote:
Though I wonder how tedious it would be to deal with floating-pointsYou never have to deal with floating-point numbers here. The above
in ceil/floor/sqrt and gurantee that code is correct. <snip>
code is just pseudocode <snip>
Let's start easy: the C-standard says "When integers are divided, the
result of the / operator is the algebraic quotient with any fractional
To be pedantic, only in C99 (the 1999 version of the standard) is this
required. Earlier, in C89, for negative operands the implementation
was allowed to choose direction of rounding. But FORTRAN already
required toward-zero for all cases, and that's what all hardware did.
And here we don't care about negative operands anyway:
For positive integers a and b this means that the C
expression "a / b" is in reality logically equivalent with the
pseudocode "floor(a / b)"
(BTW the other C integer operators like +/-/
* represent in reality modular arithmetic ops).
Not necessarily. For _unsigned_ integer types, they are. For signed
integers, the standard makes overflow Undefined Behavior and up to the
implementation. In practice all hardware nowadays uses 2's complement
which shares (most) logic with unsigned, and usually overflow just
keeps the low bits, which are a modular result (though not the
canonical one). But the C standard doesn't require this.
Big integer divisionYes.
(as well as most processor division instructions) typically provides
the quotient AND the remainder. Using this remainder it is easy to
apply a "floor" or "ceil" function directly after the division
What about the square root? One possible way to imlement an "integer
sqrt(x)" is to do binary search: <snip>
Or somewhat more efficient esp. in binary, the long-division-analog
method: for highest nonzero pair of bits the result has a 1 bit and
subtract the square of that; for each remaining pair going downward,
determine one output bit by trial subtracting (sofar*2+trial)*trial.
- formerly david.thompson1 || achar(64) || worldnet.att.net
- Prev by Date: Re: Kareem Abdel al-Hazwani will range Israel
- Next by Date: generating keys by using only part of longer random number
- Previous by thread: Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
- Next by thread: EC Curve Naming Convention