The code below is somewhat boringly similar to other stuff I've archived here before, about finding all the totatives (defined below) of some N, then multiplying all possible pairs (a Cartesian product) modulo N to show how you've got closure i.e. you never get outside the group. The totatives of N are the numbers 1...(N-1) with no factors in common with N. If N is prime, every integer 1...(N-1) is a totative. The totient of N is *how many* totatives it has. Think how it'd only take you a few lessons to have your students impressing their guardians with stuff Euler talked about (make sure they pronounce "Euler" right). Hey, did you know Ellipsis is a new primitive object in Python 3, denoted ... ?
... Ellipsis
What's a little bit different in this pass is I'm applying some stuff I learned from Steve Holden @ Pycon re iterators, other subsequent trainings. Iterators are "one way streets" that become exhausted (dead end in StopIteration) so you might need to clone them ahead of time. The itertools tee is good for that e.g. lazyA, lazyB = itertools.tee( iteratorX ) will give you two for the price of one, then don't use iteratorX anymore (it's exhausted). Below, I want the totient (== number of totatives), so consume a whole iterator going totient = len(list(theiterator)) -- but fortunately I tee first. Hey, I was just learning from David Beazley on Safari that __repr__ is generally supposed to emit a string that'll eval right back to the object represented. So if I have Modulo type and go k = Modulo(10) then my __repr__ should maybe just emit 'Modulo(10)'. __str__ is for something prettier maybe (adding makeup). itertools.product will pair each with every, given two iterators (actually, takes any number, proceeds odometer style), but again, if you were to use the same iterator twice, you'd end up consuming all the rows so nothing left for columns or vice versa. That's where the repeat keyword argument comes in, which I use as an alternative to tee for a check (see multiply_a vs. multiply_b). Other little known features of Python 3.x, the ability to write:
def f(x:int) -> int: return x * x
f.__annotations__ {'x': <class 'int'>, 'return': <class 'int'>}
The new __prepare__ method allowing processing in the classdict you're about to hand off to __new__, bolstering metaclass definitions. Set and dictionary comprehensions, cool. I play with a set comprehension below, limiting the output of the Cayley table to unique terms only (note curly braces in output) -- what takes the most room are the powering tables, where I take each totative t and go pow( t, e, N) with e ranging from 0 to totient-1 (a list comprehension). This relates to RSA. Also this is kinda weird (newly legal syntax):
alpha, *junk, omega = "This is sorta cool syntax eh?".split() alpha 'This' junk ['is', 'sorta', 'cool', 'syntax'] omega 'eh?'
OK, the rest is source code, with output listed at the end... """ product does a cartesian product of two iterables tee replicates iterables 'repeat' times (default repeat=2) More of what this is actually about: http://www.4dsolutions.net/ocn/flash/group.html (yikes, evil noise! turn down those headphones!) """ from itertools import product, tee def gcd(a,b): """ EA per Guido """ while b: a, b = b, a % b return a def tots(n): """ returns iterator of no factors in common (totatives) """ return (i for i in range(n) if gcd(i, n) == 1) def multiply_a(ts,n): """ Cayley Table of ts x ts modulo n """ ps = product(ts, repeat=2) return (i*j % n for i,j in ps) def multiply_b(ts,n): """ Cayley Table of ts x ts modulo n (alternate implementation) """ row, col = tee(ts) ps = product(row, col) return (i*j % n for i,j in ps) def powers(ts,n): a,b = tee(ts) totient = len(list(b)) for t in a: print([pow(t,exp,n) for exp in range(totient)]) def test(n): print({i for i in multiply_a(tots(n),n)}) # print({i for i in multiply_b(tots(n),n)}) powers(tots(n),n) if __name__ == '__main__': test(12) test(15) test(21) test(24) So what's the printout if you run it?....
================================ RESTART ================================
{1, 11, 5, 7} [1, 1, 1, 1] [1, 5, 1, 5] [1, 7, 1, 7] [1, 11, 1, 11] {1, 2, 4, 7, 8, 11, 13, 14} [1, 1, 1, 1, 1, 1, 1, 1] [1, 2, 4, 8, 1, 2, 4, 8] [1, 4, 1, 4, 1, 4, 1, 4] [1, 7, 4, 13, 1, 7, 4, 13] [1, 8, 4, 2, 1, 8, 4, 2] [1, 11, 1, 11, 1, 11, 1, 11] [1, 13, 4, 7, 1, 13, 4, 7] [1, 14, 1, 14, 1, 14, 1, 14] {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20} [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11] [1, 4, 16, 1, 4, 16, 1, 4, 16, 1, 4, 16] [1, 5, 4, 20, 16, 17, 1, 5, 4, 20, 16, 17] [1, 8, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8] [1, 10, 16, 13, 4, 19, 1, 10, 16, 13, 4, 19] [1, 11, 16, 8, 4, 2, 1, 11, 16, 8, 4, 2] [1, 13, 1, 13, 1, 13, 1, 13, 1, 13, 1, 13] [1, 16, 4, 1, 16, 4, 1, 16, 4, 1, 16, 4] [1, 17, 16, 20, 4, 5, 1, 17, 16, 20, 4, 5] [1, 19, 4, 13, 16, 10, 1, 19, 4, 13, 16, 10] [1, 20, 1, 20, 1, 20, 1, 20, 1, 20, 1, 20] {1, 5, 7, 11, 13, 17, 19, 23} [1, 1, 1, 1, 1, 1, 1, 1] [1, 5, 1, 5, 1, 5, 1, 5] [1, 7, 1, 7, 1, 7, 1, 7] [1, 11, 1, 11, 1, 11, 1, 11] [1, 13, 1, 13, 1, 13, 1, 13] [1, 17, 1, 17, 1, 17, 1, 17] [1, 19, 1, 19, 1, 19, 1, 19] [1, 23, 1, 23, 1, 23, 1, 23]
As I said, kinda boring maybe.... Kirby