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

sufficent proof for primes

Expand Messages
  • Bernhard Helmes
    A beautifull evening, I tried to find another sufficent proof for primes especially of the form p:=x^2+x+1. I found a test similar to Pocklington which runs as
    Message 1 of 1 , Apr 21, 2006
    • 0 Attachment
      A beautifull evening,

      I tried to find another sufficent proof for primes especially of the
      form p:=x^2+x+1. I found a test similar to Pocklington which runs as
      follow:

      p:=x^2+x+1, the factorisation of x+1 with x+1:=f1*f2*...*fn is known.
      I choose a base b which has jacobi (b, fi)=-1
      calculate erg_0:=b^x mod p and
      erg_1:=erg_0^f1 mod p, gcd (erg_1, erg_0)=1 is checked and
      erg_2:=erg_1^f2 mod p, gcd (erg_2, erg_1)=1 is checked until
      erg_n:=erg_n-1^fn mod p must be equal 1 and gcd (erg_n, erg_n-1)=1 is
      checked.

      I suppose that that is a sufficent proof for p because all roots of fi
      exist. But it might be that i am not sure.

      The test needs the same conditions as the test from pocklington and i
      think it is as fast as the test from pocklington.

      Please send me a note, if i have reinvent the wheel.
      Please let me know if the test is right or not.

      Best regards from the primes
      Bernhard

      The test written in MuPad:

      x:=2;
      while TRUE do
      p:=x^2+x+1;
      f:=ifactor (x+1);
      base:=3;

      while TRUE do
      change_base:=FALSE;
      for i from 1 to (nops (f))/2 do
      if numlib::jacobi (f[2*i], base)=1 then
      change_base:=TRUE;
      break;
      end_if;
      end_for;
      if change_base=FALSE then
      break;
      else
      base:=nextprime (base+1);
      end_if
      end_while;

      erg:=powermod (base, x, p);

      prim:=TRUE;
      for i from 1 to (nops (f))/2 do
      for j from 1 to f[2*i+1] do
      res:=powermod (erg, f[2*i], p);
      if res=erg or gcd (res, erg)>1 then
      prim:=FALSE;
      break;
      end_if;
      erg:=res;
      end_for;
      end_for;
      if prim=TRUE and erg=1 then
      print ("Prim", p, f);
      if isprime (p)=FALSE then
      print ("Falsch", ifactor (p));
      return ();
      end_if;
      end_if;
      x:=x+1;
      end_while;

      I checked all p up to 5733048401263 and did not find any
      counterexample.
    Your message has been successfully submitted and would be delivered to recipients shortly.