/* Author: Pate Williams (c) 1997 "Exercise 5.4. Factor search a ^ n +- b ^ n. Carry out the adaptation hinted at above of the computer program for trial division from Exercise 5.1 on p. 145. Decide on a reasonable value for the search limit G, depending on n. Check your program by applying it to some of the integers given in Tables 7-10. Use the program for factors of 11 ^ n +- 4 ^ n, for as high values of n as your program can handle." -Hans Riesel- See "Prime Numbers and Computer Methods for Factorization" by Hans Riesel second edition page 170. */ #include #include struct factor {long expon, prime;}; void reduce(long p, long *N, struct factor *f, long *count) { long e = 0; if (*N % p == 0) { do { e++; *N /= p; } while (*N % p == 0); f[*count].expon = e; f[*count].prime = p; *count = *count + 1; } } int m_factor(long n, long N, struct factor *f, long *count) { long A = N, G = sqrt(N), e, k = 1, p; *count = 0; reduce(2, &A, f, count); reduce(3, &A, f, count); reduce(5, &A, f, count); reduce(7, &A, f, count); if (A == 1) return 1; for (;;) { p = k * n + 1; if (p > G) { f[*count].expon = 1; f[*count].prime = A; *count = *count + 1; return 0; } if (A % p == 0) { e = 0; do { e++; A /= p; } while (A % p == 0); f[*count].expon = e; f[*count].prime = p; *count = *count + 1; if (A == 1) return 1; } k++; } } int p_factor(long n, long N, struct factor *f, long *count) { long A = N, G = sqrt(N), e, k = 1, p; *count = 0; reduce(2, &A, f, count); reduce(3, &A, f, count); reduce(5, &A, f, count); reduce(7, &A, f, count); if (A == 1) return 1; for (;;) { p = 2 * k * n + 1; if (p > G) { f[*count].expon = 1; f[*count].prime = A; *count = *count + 1; return 0; } if (A % p == 0) { e = 0; do { e++; A /= p; } while (A % p == 0); f[*count].expon = e; f[*count].prime = p; *count = *count + 1; if (A == 1) return 1; } k++; } } int main(void) { long N, a, b, count, i, n; struct factor f[32]; for (n = 2; n < 9; n++) { a = pow(11, n); b = pow(4, n); N = a - b; m_factor(n, N, f, &count); if (count > 1) { printf("%ld is composite\nfactors:\n", N); for (i = 0; i < count; i++) { printf("%ld ", f[i].prime); if (f[i].expon > 1) printf(" ^ %ld\n", f[i].expon); else printf("\n"); } } else printf("%ld is prime\n", N); N = a + b; p_factor(n, N, f, &count); if (count > 1) { printf("%ld is composite\nfactors:\n", N); for (i = 0; i < count; i++) { printf("%ld ", f[i].prime); if (f[i].expon > 1) printf(" ^ %ld\n", f[i].expon); else printf("\n"); } } else printf("%ld is prime\n", N); } return 0; }