// Shor's factoring algorithm
//
// factor n by finding period of y**a for 0 <= a < q
// using random y with q = 2**l, n*n <= q < 2*n*n
//
#include <stdio.h>
#include <stdlib.h>

int main( int argc, char *argv[])
{
  unsigned n, n2, q, a, y, z;

  if( argc != 3) { fprintf( stderr, "Usage: %s n y\n", argv[0]); return 1; }

  n = atoi( argv[1]); y = atoi( argv[2]);

  n2 = n*n; q = 1;  while( q < n2) q <<= 1;

  // printf( "n = %u, y = %u, n2 = %u, q = %u\n", n, y, n2, q);

  printf( "%d\n", q); // number of points

  z = 1;  printf( "1\n"); // the points, y^a ...

  for( a = 1; a < q; ++a)
  {
    z = (y*z) % n;
    printf( "%u\n", z);
  }

  return 0;
}