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
<iBBiS@xxxxxx> wrote:
On 29 Mai, 20:09, Le Chaud Lapin <jaibudu...@xxxxxxxxx> wrote:<snip choosing factors to give exactly nbit N>
On May 29, 3:14 am, Christian Siebert <iB...@xxxxxx> wrote:
Though I wonder how tedious it would be to deal with floatingpointsYou never have to deal with floatingpoint 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 Cstandard says "When integers are divided, the
result of the / operator is the algebraic quotient with any fractional
part discarded.".
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 towardzero 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)"
Right.
(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
operation.
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 longdivisionanalog
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 alHazwani 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
 Index(es):
Relevant Pages
