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

sufficient test for primes with certificate

Expand Messages
  • bhelmes_1
    1. A criteria to distinguish primes from composite numbers: a) If and only if an odd number p 5 has two solutions in the field of adjoined square root A with
    Message 1 of 33 , May 7, 2012
    • 0 Attachment
      1. A criteria to distinguish primes from composite numbers:

      a) If and only if an odd number p > 5 has two solutions
      in the field of adjoined square root A
      with A quadratic residuum and element of N
      where the solutions consist the form f+g*sqrt (A) with f=0 and g=/=0
      for the equation x^2 = 1 mod p
      then p is a prime.

      (For the primes 2, 3, 5 there does not exist a suitable A)

      b) An odd number which is composite does not have any solution
      in the field of adjoined square root A
      with A a quadratic residuum and element of N
      where the solution should consist
      of the form f+g*sqrt (A) with f=0 and g=/=0
      for the equation x^2= 1 mod p

      i made an implementation of the algorithm:

      http://109.90.3.58/devalco/sufficient_test_for_primes_with_certificate.html

      the old version can be find under:
      http://109.90.3.58/devalco/sufficient_test_for_primes_with_certificat.html

      Description of the new algorithm:

      1. I make a strong probablistic test:
      http://primes.utm.edu/prove/prove2_3.html

      2. I make a similiar rabin-miller test for (1+sqrt(A))^[(p-1)]/2^r
      if p is prime there is a chance of 50% for one test to find a certificate
      with [g*sqrt (A)]^2=1 using the first criteria for primes where x^2=1

      If p is not prime then one test with (1+sqrt(A))^(p-1)=/=1
      will prove that p is not prime.

      2. mathematical proof by Kermit Rose

      Let p be prime.

      Let A be a square residue mod p.
      Then there exist an integer x mod p such that x^2 = A mod p.

      Does there exist
      (f + g sqrt(A)) such that (f + g sqrt(A))^2 = 1 mod p and g is not equal
      to zero mod p.

      (f = g sqrt(A))^2 = ( f^2 + A g^2) + (2 f g) sqrt(A) = 1

      2 f g = 0 mod p

      Since g is not zero mod p,
      and 2 f g = 0 mod p, and p is prime, it must be that

      f = 0 mod p.

      (g sqrt(A) )^2 = A g^2 = 1

      has exactly the two solutions

      g = 1/x and g = -1/x, where x^2 = A mod p.


      Now, let P be composite = p1^k1 * p2^k2 * ....

      Let A be a square residue mod P.
      Then A is a square residue mod p1, p2, ...

      let x1^2 = A mod p1,
      x2^2 = A mod p2,
      etc

      (f + g sqrt(A))^2 = (f^2 + A g^2) + (2 f g) sqrt(A) = 1 mod P.

      2 f g = 0 mod P.

      Since P is composite, there exist non-zero values of f which satisfy 2 f
      g = 0 mod P.

      Let g be a divisor of P.
      since P is odd, g is odd, and P/g is odd.

      set f = (P + P/g)/2

      Then 2 f g = 2 [ (P + P/g)/2] [g] = [P + P/g][g] = gP + P = 0 mod P

      f^2 + A g^2 = [ (P + P/g)/2]^2 + A g^2 = (P/g)^2 + A g^2 mod P

      Since A is a square residue mod P, there exist x such that x^2 = A mod P.

      (P/g)^2 + (x g)^2 = 1 mod P, where g divides P.

      (xg)^2 = 1 - (P/g)^2.

      That is, we will find counter example if we can find a composite
      such that
      1 - (P/g)^2 is a square residue mod P, where g is a divisor of P.
    • paulunderwooduk
      ... I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings { 17.505s pfgw (3-prp) 1m1.986s
      Message 33 of 33 , Sep 21, 2012
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
        :
        > http://tech.groups.yahoo.com/group/primenumbers/files/Articles/

        > I ran various "minimal \lambda+2" tests on Gilbert Mozzo's 20,000 digit PRP, 5890*10^19996+2^66422-3 (x=1), using a 2.4GHz core:
        > {
        > 0m32.374s pfgw64 (3-prp)
        > 1m9.876s pfgw64 -t
        > 1m53.535s pfgw64 -tp
        > 3m0.483s pfgw64 -tc
        > 5m12.972s pfgw64 scriptify
        > 4m4.811s gmp (-O3/no pgo)
        > 4m9.148 pari-gp
        > 1m15s theoretical Woltman implementation
        > }
        >

        I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings
        {
        17.505s pfgw (3-prp)
        1m1.986s pfgw -tp
        1m13.789s gmp (-O3/no pgo)
        }

        Paul
      Your message has been successfully submitted and would be delivered to recipients shortly.