/* IMPSTEP version 0.1 - Core War imp step calculator by John Metcalf * Usage: impstep coresize * impstep = points ^ -1 (mod coresize) if gcd(points, coresize) = 1 */ #include #include #define MAXCORESIZE 65535 #define FIRSTX 20 /* GCD - greatest common divisor * returns the gcd of a and b. 1 if a and b are relatively prime */ unsigned gcd( unsigned a, unsigned b ) { unsigned temp; while ( b != 0 ) { temp = a % b; a = b; b = temp; } return a; } /* PHI - Euler's totient function * returns the number of integers less than n which are coprime to n */ unsigned phi( unsigned n ) { unsigned i, totient = n; for ( i = 2; i * i <= n; i++ ) { if ( n % i == 0 ) { do n /= i; while ( n % i == 0 ); totient -= totient / i; } } if ( n > 1 ) totient -= totient / n; return totient; } /* MODEXP - modular exponentiation * returns b^e mod m */ unsigned modexp(unsigned b,unsigned e,unsigned m) { unsigned c = 1; while ( e ) { if ( e & 1 ) c = c * b % m; e >>= 1; b = b * b % m; } return c; } int main( int argc, char *argv[] ) { unsigned cimp=1, i=0, coresize, power; if ( argc == 1 ) { printf( "IMPSTEP - Core War imp step calculator\n" "Usage: impstep coresize\n" ); return 0; } coresize = atoi( argv[1] ); if ( coresize == 0 || coresize > MAXCORESIZE ) { printf( "ERROR: coresize out of range\n" ); return 1; } power = phi( coresize ) - 1; printf( " Points Step\n" ); while ( i < FIRSTX && cimp++ < coresize/2 ) { if ( gcd(cimp, coresize) == 1 ) { printf( "%7u %7u\n", cimp, modexp( cimp, power, coresize ) ); i++; } } }