Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA

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:
On May 29, 3:14 am, Christian Siebert <iB...@xxxxxx> wrote:
<snip choosing factors to give exactly n-bit N>
Though I wonder how tedious it would be to deal with floating-points
in ceil/floor/sqrt and gurantee that code is correct. <snip>
You never have to deal with floating-point numbers here. The above
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
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 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)"

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 division
(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.

Yes.

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
.

Relevant Pages

  • Re: AES trickery ;-)
    ... >> some implementations of the C standard, ... using it in pseudocode seems bizarre unless you are writing a compiler ... perhaps you should have said "don't critique this". ... The intention was not going to be to ...
    (sci.crypt)
  • Re: Modul (%) in python not like in C?
    ... the algebraic quotient with any fractional part discarded. ... If the quotient a/b is representable, ... Turbo C is against the standard, ...
    (comp.lang.python)
  • Re: Modul (%) in python not like in C?
    ... it defines the result for positive over positive, and constrains the ... the algebraic quotient with any fractional part discarded. ... Multiplicative operators, ... But C was around for a long time before the 1999 standard. ...
    (comp.lang.python)
  • Re: How often do you read the C standard?
    ... The confusion here is that you may be treating ... as pseudocode whereas others are treating it as a C expression. ... As pseudocode, you are correct. ... As a C expression, the Standard ...
    (comp.lang.c)
  • Re: If you were inventing CoBOL...
    ... >> The standard provides pseudocode for REM that's exactly the same as my ... >would be produced by the pseudocode. ... >don't see it in the code our compilers generate for these constructs. ... I didn't know REM() existed until you pointed it out. ...
    (comp.lang.cobol)