# Frobenius Probable Prime Test

**Kevin Ryde
**
user42@zip.com.au

*Fri, 30 May 2003 09:52:47 +1000*

"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.