> In a first pass, we provide the code below as scaffolding, explaining > as we go, *not* requiring students to write it all from scratch > (though some might -- plus there's room for improvement (see > comments)).
Just a small refinement, slightly more advanced: """ Special to edu-sig by K. Urner: see previous post for M class on which Mx is based. Just adding a better way for finding multiplicative inverses modulo M using Euclid's Extended Algorithm (ee). See also: Algorithms: A Bit of Math by Andrew Kuchling http://pythonjournal.cognizor.com/pyj1/AMKuchling_algorithms-V1.html Copyright (c) 1998 Andrew Kuchling """ from chicago2 import M def ee(a, b): """Euclid extended by Alexandru Scvortov http://snippets.dzone.com/posts/show/4192 """ if b == 0: return a, 1, 0 dd, xx, yy = ee(b, a % b) d, x, y = dd, yy, xx - (a // b) * yy return d, x, y class Mx(M): """ Adds extended Euclidean (ee) for finding multiplicative inverses """ def __init__(self, val): self.val = val % M.modulus self.recip = ee(self.val, M.modulus)[1] % M.modulus # everything else the same as M-type _______________________________________________ Edu-sig mailing list [email protected] http://mail.python.org/mailman/listinfo/edu-sig
