Frobenius Probable Prime Test

[Kevin Ryde]

"Rick Lavoie" <coldfury@bu.edu> writes:
>
>  http://cs-people.bu.edu/coldfury/frobenius.c
>
> 	for (i = m_bitsize-1; i >= 0; i--) { /* We loop over the bits of m, analogous to powering */

If you want to work something up as a demo for inclusion the gmp
distribution you'll need it in GNU coding style.

	http://www.gnu.org/prep/standards.html

> 			mpz_pow_ui(tempv, v, 2);

Squaring should be done with mpz_mul.

> 		mpz_divexact_ui(m, m, 2); /* m = (n - Jacobi(discriminant/N))/2 */
>		mpz_mul_ui(temp2, v, 2);

Multiplications and divisions by powers of two should be done with
mpz_mul_2exp and mpz_fdiv_q_2exp (and friends).

> 			mpz_mod(temp1, temp1, N);
> 			if (mpz_cmp_ui(temp1, 2) != 0) /* B*u != 2 mod N implies composite */

Perhaps mpz_congruent_ui_p here, unless you want that reduced temp1
for later use.

> 		} while (mpz_perfect_square_p(discriminant) || mpz_jacobi(discriminant, N) != -1 || mpz_jacobi(b, N) != 1);

Will this be an infinite loop if N is a perfect square?  Or perhaps
that's checked early on.

> 	gmp_printf("Test Number: ");
> 	gmp_scanf("%Zd", N);
> 	gmp_printf("Iterations: ");
> 	gmp_scanf("%u", &iterations);

Probably cleaner to take these from the command line, or have it only
as an option to read stdin.

A check that input conversion is successful (ie. it's a number) will
be good too, to keep users out of trouble.

A usage message will be wanted too.  Perhaps as a printf when run, or
in some comments at the top of the file.