March 07, 2003

And they say Mathematics is boring...
While reading about Euclid's Algorithm* today I found these two poems

Euclidean Algoryhme
You're given two numbers, and now you desire
a method for finding their common divisor.
(The greatest, of course, is the one you must name.)
To do it, you'll keep shared divisors the same
while repeatedly shrinking each number in turn
'til one of them's zero, and then you discern
that the other's the greatest divisor they share.
So how do you manage to lessen the pair?
You divide large by small, then large is ejected,
small becomes large, as remainder's injected.


Multiplicative inVerse
Now if clever you are can take this lots farther,
by some bookkeeping work which is not much a bother.
Each number you deal with, depict as duple
to dot-product with the original couple.
You start with one-zero, then zero-one,
then each new remainder's the combination
of the smaller one's duple times minus the quotient
plus one times the larger one's duple. The notion?
If the numbers you're given are relative primes,
the gcd's duple holds inverses (times).


--Mike Speciner [taken from Network Security: Private Communication in a Public World]


*Euclid's Algorithm is a method of finding the greatest common divisior (gcd) of two numbers x and y. The idea is to repeatedly replace the original numbers with smaller numbers that have the same gcd until on of the numbers is zero. The remaining mumber is the gcd. The algorithm is also used to find multiplicative inverses mod n

0 Comments:

Post a Comment

<< Home