Mersenne primes 2^31-1

generators.c

#include <stdio.h>
#include <stdint.h>
#include <string.h>

#define PRIME ((1ull << 31) - 1)

uint32_t
cycle(uint32_t seed, uint32_t prev)
{
	uint64_t x = prev;
	x *= (uint64_t) seed;
	return x % PRIME;
}

uint32_t
is_generator(uint32_t n)
{
	uint32_t ctr = 1;
	uint64_t x = n;
	if (n <= 1) return 0;
	while (x != 1) {
		x *= (uint64_t) n;
		x = x % PRIME;
		ctr++;
	}
	fprintf(stderr, "%d\t%lld\t(%d)\n", n, (unsigned long long) ctr, (PRIME - 1) / ctr);
	return ctr == PRIME - 1;
}

int
main(void)
{
	int n;
	for (n = 2; n < 31; ++n) {
		if (is_generator((1ull << n) - 1)) {
			printf("Generator: 2^%d-1\n", n);
			fflush(stdout);
		}
	}
	return 0;
}

/* Generators of the form 2^k-1 of Z/(2^31-1)Z are
2^3 -1 = 7         (Mersenne)
2^5 -1 = 31        (Mersenne)
2^11-1 = 2047
2^14-1 = 16383
2^18-1 = 262143
2^19-1 = 524287    (Mersenne)
2^23-1 = 8388607
2^27-1 = 134217727
*/