[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: peasant_multiply question*From*: [email protected] (FutureNerd Steve Witham)*Date*: Tue, 8 Dec 1992 13:26:56 -0800*Sender*: [email protected]

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 [email protected] (FutureNerd Steve Witham)

- Prev by Date:
**Captain Midnight returns?** - Next by Date:
**Re: PGP questions** - Prev by thread:
**No more PGP keys without signatures, please!** - Next by thread:
**PGP key generation** - Index(es):