I think your algorithm is correct, but could be sped up a lot by doing a little more math and less computing. On Sun, May 1, 2016 at 6:21 PM, Keith F. Lynch <kfl@keithlynch.net> wrote:
For every N (modulus), 1 through 1000, I try every I, 1 through N-1, to see if it equals its own square (mod N). If it does, it's an identity element for at least one multiplicative group mod N. For instance for mod 10 the identity elements are 0, 1, 5, and 6.
In general, there will be 2^n of these, where n is the number of distinct primes dividing N. Once you've determined, one way or another, the groups for I = 1, you don't need to do the computation for the other 2^n -1 identities, because you've already counted these! The groups with identity I are in 1-1 correspondence with the groups mod N/I with identity 1, so you can just look up how many of these there are, since you've already counted them. For counting the groups with identity 1, I suspect that a much faster algorithm could be devised, starting by factoring N, which lets you express the meximal group of all elements relatively prime to N as a product of cyclic groups; for each prime p that divides N, if p^k is the largest power of p that divides N, then this gives you a cyclic group of order p^k - p^(k-1). The overall group that you're looking for the subgroups of is the direct product of these groups, one for each prime that divides N. I think there should be some faster way to find the subgroups once you have the group in this form, though I haven't found it yet. Andy