| Re .0:
Gee, do you suppose "e" and "d" stand for "encode" and "decode"?
Modular multiplicative inverses are easily found with an extension of
Euclid's algorithm for finding the greatest common divisor.
Let a = (n, 0) and let b = (e, 1). These are vectors of two elements,
and the arithmetic we do with them will be element-by-element. Thus,
multiplying the vector (j, k) by (m, n) results in (j*m, k*n). Also, I
will use a[0] and a[1] to indicate the individual elements in a.
Do
Let q = a[0] / b[0]. (Take the integer part of the quotient;
discard any fraction.)
Let c = a - q*b. (Multiply each element in b by q and
subtract them from a's elements.)
Let a = b.
Let b = c.
while b[0] != 0.
When this loop is done, a[0] will contain the greatest common divisor
of n and e, and a[1] will contain the multiplicative inverse of e
modulo n. To see this, observe that for the initial vectors put into a
and b, the following property is true:
a[0] is congruent to a[1]*e, modulo n.
With some algebra, you can show that whenever this property is true for
a and b, it is true for the c calculated in the loop, so it is true for
all vectors the loop calculates. So at the end, where a[0] is 1 if n
and e are relatively prime, a[1]*e is congruent to 1. Note that a[1]
may be negative.
You can find source code for this algorithm in the PGP kit.
-- edp
Public key fingerprint: 8e ad 63 61 ba 0c 26 86 32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.
|
| Like edp, my first reaction was to suggest using Euclid to simultaneously
find the gcd and solve the problem if the gcd is 1.
But then I wondered if this was the "brute force" approach that you already
discounted; all those divides and multiplies. If so, then have you looked at
Knuth(Motto: there's always a quicker way)'s "Seminumerical Methods", half of
which seems to be devoted to the performance etc of Euclid?
Dick
With apologies to Dave Barry
|
| > Gee, do you suppose "e" and "d" stand for "encode" and "decode"?
A lucky guess :-)
Well, I typed in the algorithm and it worked for one set of numbers
but for the next 3 sets, a1 came out negative.... until I added it to
the orginal a0 and everyone was happy again.
Thank you, edp. May your monkey sleep peacefully forevermore.
BTW: Does Euclid charge royalties? :-)
And, Dick, when I referred to brute force I meant raising n
by one and finding some number d such that d*e > n and then
check the remainder to see if it was 1. If not, raise n again
and repeat. For large numbers that would be a *lot* of calculations.
The algorithm edp typed in was exactly what I was looking for.
Thank you,
Tom
|