Loading ...
Sorry, an error occurred while loading the content.

Re: Unified test for Sophie Germain primes

Expand Messages
  • djbroadhurst
    ... Looks good. But you can speed it up by a factor of 2 by working with Mod(3/4,2*p+1) JL(p)=Mod(3/4,2*p+1)^p==1;
    Message 1 of 5 , Jan 19, 2010
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "j_chrtn" <j_chrtn@...> wrote:

      > Mike should appreciate this particular
      > use of our favourite (n+1)^p-n^p numbers ;-)

      Looks good. But you can speed it up by a factor
      of 2 by working with Mod(3/4,2*p+1)

      JL(p)=Mod(3/4,2*p+1)^p==1;
      forprime(p=5,10^7,if(JL(p)!=isprime(2*p+1),print([p,fail])));

      David
    • j_chrtn
      ... Right. 3/4 appears in the proof. Do you know if this test is something well known? I ask this because I ve never seen it before. J-L
      Message 2 of 5 , Jan 19, 2010
      • 0 Attachment
        > --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
        >
        > Looks good. But you can speed it up by a factor
        > of 2 by working with Mod(3/4,2*p+1)
        >

        Right. 3/4 appears in the proof.

        Do you know if this test is something well known?
        I ask this because I've never seen it before.

        J-L
      • djbroadhurst
        ... It s not well known because it s quite unnecessary. The foolproof unified Sophie test that works in *all* cases is much simpler. If p is prime, then q =
        Message 3 of 5 , Jan 20, 2010
        • 0 Attachment
          --- In primenumbers@yahoogroups.com,
          "j_chrtn" <j_chrtn@...> wrote:

          > Do you know if this test is something well known?

          It's not well known because it's quite unnecessary.
          The foolproof "unified Sophie" test that works in
          *all* cases is much simpler.

          If p is prime, then q = 2*p+1 is prime iff 4^p = 1 mod q.

          Proof: Simply use base 2 in Pocklington's theorem and
          observe that 2^2-1 is coprime to 2*p+1 for every prime p.

          Note that this test detects *every* Sophie pair,
          including [2,5] and [3,7]. Here is a sanity check:

          Pock(p)=Mod(4,2*p+1)^p==1;
          forprime(p=2,10^6,if(Pock(p)!=isprime(2*p+1),print(fail)));
          \\ The rest is silence, signifying consent

          Entia non sunt multiplicanda praeter necessitatem :-)
          http://en.wikisource.org/wiki/The_Myth_of_Occam's_Razor

          David [second attempt at a reply; apologies if it appears twice]
        • j_chrtn
          ... Unnecessary but at least correct. ... This is closed to Henri Lifchitz s test 3^p = 1 (mod q) but your s also handles p=2 and p=3. ... There Is More Than
          Message 4 of 5 , Jan 20, 2010
          • 0 Attachment
            >--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
            >
            >
            > It's not well known because it's quite unnecessary.
            >
            Unnecessary but at least correct.

            >
            > If p is prime, then q = 2*p+1 is prime iff 4^p = 1 mod q.
            >
            This is closed to Henri Lifchitz's test 3^p = 1 (mod q) but your's also handles p=2 and p=3.

            >
            > Entia non sunt multiplicanda praeter necessitatem :-)
            >

            "There Is More Than One Way To Do It."
            http://en.wikipedia.org/wiki/There's_more_than_one_way_to_do_it

            However, some ways are more efficient than others ;-)

            Regards,
            J-L
          Your message has been successfully submitted and would be delivered to recipients shortly.