Results 1 to 4 of 4

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

  1. #1
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    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 ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Bacterius View Post
    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
    Last edited by CaptainBlack; June 9th 2010 at 10:59 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Bacterius View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The fastest way to test primality ?
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 9th 2011, 09:00 AM
  2. Ironing out the Lucas Primality Test proof
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: April 24th 2010, 06:31 PM
  3. program problem about primality test
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 11th 2010, 11:02 PM
  4. The Miller-Rabin test for primality...
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 11th 2008, 02:24 PM
  5. primality testing - ugh - HELP
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 16th 2007, 08:26 PM

Search Tags


/mathhelpforum @mathhelpforum