Efficiently compute a complete set of representatives of cyclotomic cosets of $2$ modulo $2^n-1$ Let $n &gt; 1$. For an integer $k$ with $0 \leq k \leq 2^n-2$ the cyclotomic class $C_k$ of $2$ modulo $2^n-1$ is the set given by 
$$C_k = \{k, k\cdot 2, k \cdot 2^2 , \ldots, k\cdot 2^{n-1} \pmod {2^n-1}\},$$
where the entries are reduced modulo $2^n-1$. Note that either $C_k = C_i$ or their intersection is empty. A set $\{a_1, \ldots, a_m\}$ of integers in $[0, 2^n-1]$ is called a complete set of representatives of the classes if $C_{a_j} \neq C_{a_i}$ whenever $i \neq j$ and 
$$
\bigcup_{i=1}^m C_{a_i} = \{0, 1, \ldots, 2^n-1\}. 
$$

I am interested in, given $n$, efficiently computing the corresponding complete set of representatives of the cyclotomic classes. Any ideas? I'm hoping to be able to compute this for large enough $n$. Thanks!
You can use simple enumeration.  This will be about as fast as you can achieve, for a modulus of the form $2^n-1$.

Namely, for each possible $k$, you check whether $C_k$ is a new set (distinct from the ones you already know about).  If it is, you add it to the set; if it isn't; you skip it and move onto the next $k$.

This gives an algorithm like the following:


Set $S := \emptyset$ and $A := \emptyset$.  ($A$ holds the set of representatives; $S$ holds the set of elements covered by one of the corresponding cyclotomic classes.)
For each $k=1,2,\dots,2^n-1$:


If $k \notin S$, add $k$ to $A$ and set $S := S \cup C_k$.



The running time of this algorithm will be $\Theta(2^n)$.

This is also within a $\Theta(n)$ factor of optimal.  In particular, any algorithm must have running time at least $\Theta(2^n/n)$.  The reason is that, for a modulus of the form $2^n-1$, the output size of any correct algorithm must be $\Theta(2^n/n)$: there are $\Theta(2^n/n)$ distinct cyclotomic classes.  Therefore, no algorithm can run faster than $\Theta(2^n/n)$ time, since it will take at least $\Theta(2^n/n)$ time to print/construct the desired output.

Why is the output size $\Theta(2^n/n)$.  Well, for the specific modulus $2^n-1$, it is guaranteed that each cyclotomic class has size $n$.  (Proof: $2^n \equiv 1 \pmod{2^n-1}$, so no cyclotomic class can have size larger than $n$.  Also $2^j &lt; 2^n-1$ when $j&lt;n$, so $2^j \not\equiv 1 \pmod{2^n-1}$ when $j&lt;n$.  Therefore each cyclotomic class has size exactly $n$.)  This result is specific to the particular kind of modulus you are focusing on.