# Math Help - Wilson's Primality Test ... what ?

1. ## Wilson's Primality Test ... what ?

Hello,
I've just stumbled upon this paper :

Computational Reduction of Wilson's Primality Test for Modern Cryptosystems

Interested, I've read it through, used the final formula (eqn. 21) for a small prime and it failed. Is it me or is this paper heavily flawed, if not at the edge in terms of actual relevance ? By relevance, I mean, just look at the example : they proved the primality of 29 in 14 rather heavy steps. How many steps would've taken a trial check ? It seems a bit too optimistic ... and it's quite hard to read too.

What do you think ?

2. Originally Posted by Bacterius
Hello,
I've just stumbled upon this paper :

Computational Reduction of Wilson's Primality Test for Modern Cryptosystems

Interested, I've read it through, used the final formula (eqn. 21) for a small prime and it failed. Is it me or is this paper heavily flawed, if not at the edge in terms of actual relevance ? By relevance, I mean, just look at the example : they proved the primality of 29 in 14 rather heavy steps. How many steps would've taken a trial check ? It seems a bit too optimistic ... and it's quite hard to read too.

What do you think ?
To be honest all I see is a factor of two improvement on the obvious way of economising the computation of $(n-1)! \text{ mod }n$, and I suspect that factor of two is well known to those working in the field (at least if they correct the mistake that becomes obvious if they take a test value of 23 rather than 29 (and assuming my arithmetic is correct), I think they have lost a factor of $(-1)^{\frac{n-1}{2}}$ in equation 11).

Also given the sloppy type setting wonder about the status of Informatica.

CB

3. I don't know if you have seen the latest edit with what I believe is an error in the method.

On the whole this just supports my belief that 70% or more of the published literature is worthless crap (with the notable exception of the MHF-zine obviously).

CB

4. Originally Posted by Bacterius
Hello,
I've just stumbled upon this paper :

Computational Reduction of Wilson's Primality Test for Modern Cryptosystems

Interested, I've read it through, used the final formula (eqn. 21) for a small prime and it failed. Is it me or is this paper heavily flawed, if not at the edge in terms of actual relevance ? By relevance, I mean, just look at the example : they proved the primality of 29 in 14 rather heavy steps. How many steps would've taken a trial check ? It seems a bit too optimistic ... and it's quite hard to read too.

What do you think ?
Also its efficiency is not too good when the candidate prime has say 10 digits, specially when compared to the statistical tests.

CB