From: fnerd@smds.com (FutureNerd Steve Witham)
Date: Tue, 8 Dec 92 09:53:58 PST
To: cypherpunks@toad.com
Subject: peasant_multiply question
Message-ID: <9212081715.AA26885@smds.com>
MIME-Version: 1.0
Content-Type: text/plain


Folks--

I got out my copy of the original RSA paper, and I'm comparing it to the
PGP 2.0 code.  I have a question about the peasant_modmult routine (the
simplest modmult in PGP).  Here's pseudocode of what I think it's doing:

    /* Inputs: modulus, multiplier, multiplicand */
    /* Output: prod */

    prod = 0;
    set sniffer to most significant bit of multiplier;
    nbits = number of significant bits in multiplier;

    while( nbits-- )
        {
        shift prod left 1;
        prod = prod - modulus;
        if( the bit of the multiplier being sniffed = 1 )
            {
            prod = prod + multiplicand;
            prod = prod - modulus;
            }
        move the sniffer to the next bit of the multiplier;
        }

My question is (assuming I'm understanding the code right), how can it
work subtracting modulus unconditionally all the time?  Won't it make
prod negative sometimes, and then keep multiplying the negative number
by two until it overflows?   Isn't that a problem??

-fnerd
quote me
fnerd@smds.com (FutureNerd Steve Witham)