primality test

[Sisyphus]

----- Original Message ----- 
From: "Jonathan A. Zylstra" <jon at jzylstra.com>


> >
> There is nothing in the documentation that suggests that the bases
> chosen are random.

That's true - but given that it's usual to select bases at random, I think
the documentation should detail the method being used if it's deviating from
the "norm".

> It's much more useful to preform
>
> mpz_probab_prime_p(c, 3000)
>
> than 3000 iterations of mpz_probab_prime_p(c, 1)
>

Well .... yes ..... *if* the bases are not being chosen at random -
otherwise there's negligible difference.

> To use the Miller-Rabin test to prove that a number is conclusively prime,
> you need to test using all bases up to sqrt(n)
> If you want to assume a conjecture [namely the Extended Riemann
hypothesis]
> you need to test using all bases up to 2 * (ln^2  n)
> Otherwise, there is still a chance for a number to pass dozens of
> iterations of the test, and still be composite.
>

That's amusing - if one is so sceptical as to require that 2 * (ln^2 n)
tests be carried out, then one is surely (or ought to be) too sceptical to
assume the erh. (I have the book, and it's a very good one btw.)

> Try these numbers on for size: (use the algorithm in the footnote
> provided by Rob ... starting with 1 iteration, and working your way up)
>
> 1502401849747176241 (passes bases 2 -11, recognized composite by base
> 12) ( ?? requires 8+ iterations to pass -my guess, haven't tried it
> using gmp)
> 341550071728321 (passes bases 2-22, recognized composite by base 23) (
> ?? requires 13+ iterations to pass -my guess, haven't tried it using gmp)
>

This is a good reason to choose random bases - so that specially engineered
numbers like the above are still quickly found to be composite. Choose a
base at random in the range 2..1502401849747176240. What chance does the
number have of being reported "prime" by that one Miller-Rabin test ? Just
how lucky are you feeling ? (Significantly luckier than Dirty Harry, one
suspects :-)

By my reckoning, mpz_probab_prime_p() reports both of these smaller numbers
as composite, irrespective of the number of iterations. Not sure why that is
(perhaps on the basis of trial division rather than mr tests) ..... I can
feel a delve into the source code pending .....

Cheers,
Rob