Program for U Groups
MA375, Spring 2009, Prof. Walther
This is a program that will list all the cycles of U(x). An example would be:
Input: x = 20 (Finding the cycles of U(20))
Output: U(20) = {1,3,7,9,11,13,17,19}
<1> = {1}
<3> = {1,3,7,9}
<7> = {1,3,7,9}
<9> = {1,9}
<11> = {1,11}
<13> = {1,9,13,17}
<17> = {1,9,13,17}
<19> = {1,19}
Here's the program:
#include <iostream> #include <cmath> #include <map> #include <list> using namespace std; int gcd(int a, int b); int main(int argc, char **argv) { map<int, list<int> > gens; map<int, list<int> >::iterator iter; list<int>::iterator l_iter; int u, p = -1; while(1) { cout << "Enter an integer x (for U(x)): "; cin >> u; if(u > 1) break; cout << "Error: x must be greater than 1\n"; } for(int i = 1; i < u; i++) { if(gcd(i, u) == 1) { while(p != i) { gens[i].push_back(p = (p == -1 ? (i*i)%u : (i*p)%u)); } p = -1; } } iter = gens.begin(); cout << "U(" << u << ") = {" << (*iter).first; iter++; for(; iter != gens.end(); iter++) cout << "," << (*iter).first; cout << "}" << endl; for(iter = gens.begin(); iter != gens.end(); iter++) { (*iter).second.sort(); l_iter = (*iter).second.begin(); cout << "<" << (*iter).first << "> = {" << *l_iter; l_iter++; for(; l_iter != (*iter).second.end(); l_iter++) { cout << "," << *l_iter; } cout << "}" << endl; } system("PAUSE"); } int gcd(int a, int b) { if(a > b) gcd(b, a); if(b%a == 0) return a; else return gcd(b%a, a); }
I can also send you the program if you want to e-mail me at jniederh@purdue.edu
--Jniederh 17:31, 15 February 2009 (UTC)