Frobenius Probable Prime Test

[Rick Lavoie]

Thanks for the input!

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

I looked at the standards, but I couldn't find anything applicable to the
above for loop.

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

mpz_congruent_ui_p takes an unsigned int as both the second and third
parameters, and N is too big to be held in an unsigned int.

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

I don't see off-hand if N is a perfect square will affect anything. However,
it's a useful thing to test before going thru the main test, so I've added
it in.

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

I've modified the program so it reads it's parameters thru the command line.

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

Added (reasonible) error checking too.

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

If the proper parameters aren't inputted, a brief explanation of usage is
now printed.

Rick Lavoie
coldfury@bu.edu