Testing the Usefulness of Prime Number Test

[ramsey2879]

Does anyone have any comment on the usefulness of the following test?
Input P
Prime = true
Triangular = 0
n = 0
Do until Triangular > P
n = n + 1
Triangular = Triangular + n
loop
X = Triangular Mod P
Do
Y = Int(Sqr(2*X))
' Comment if X is triangular then (Y*Y+Y)/2 = X
If (Y*Y+Y)/2 = X then
Prime = False
Exit Do
End If
n = n + 1
X = (X+ n) mod P
loop until n = (P+1)/2
Print "P is prime is " & Prime

Edit: I forgot to mention that this test does not work for primes less than 11 since then the sum of all numbers from 1 to (P-1)/2 is not greater than P but I checked it as an Excel macro for all odd numbers between 8 and 90,000 and the test worked perfectly.

 

[ramsey2879]

I should post the following modification to more quickly complete the test in the case that P is an odd triangular number. Change the statement "Do until Triangular > P" to --Do until Triangular > P-1 --.

 

[CRGreathouse]

Here's my test code (Pari/GP):

test(p)={
  my(tri=0,n=0,x,y);
  while(tri<=p,tri+=n++);
  x=tri%p;
  while(n!=(p+1)/2,
    y=sqrtint(x+x);
    if(x==y*(y+1)/2,return(0));
    x=(x+n++)%p
  );
  1
};

It seems to be an extremely slow test compared to trial division. I have attempted to repeat your verification to 90,000 but it has not completed in ten minutes. (I did not uncover any mistakes in that time, though.)

 

[ramsey2879]

Here's my test code (Pari/GP):

test(p)={
  my(tri=0,n=0,x,y);
  while(tri<=p,tri+=n++);
  x=tri%p;
  while(n!=(p+1)/2,
    y=sqrtint(x+x);
    if(x==y*(y+1)/2,return(0));
    x=(x+n++)%p
  );
  1
};

It seems to be an extremely slow test compared to trial division. I have attempted to repeat your verification to 90,000 but it has not completed in ten minutes. (I did not uncover any mistakes in that time, though.)

once the test is verified/proven then improvements/unnecessary steps such as recalculating the triangular number can be considered.

 

[CRGreathouse]

once the test is verified/proven then improvements/unnecessary steps such as recalculating the triangular number can be considered.

I moved to a faster computer and was able to verify that your test works on all odd numbers n with 3 < n < 90,000. Here's a slightly (18%) faster version of the test:

test(p)={
  my(n=sqrtint(2*p),x=n*(n+1)/2,y,target=(p+1)/2);
  while(x<=p,x+=n++);
  x=x%p;
  while(n!=target,
    y=sqrtint(x+x);
    if(x==y*(y+1)/2,return(0));
    x=(x+n++)%p
  );
  1
};

It's clearly far slower than trial division if p is prime -- it takes about p/2 steps instead of about 2sqrt(p)/log(p) steps. It seems to take longer for composites as well.

 

[willem2]

This is closely related to Fermat's method
if n isn't divisible by 2.

(all calculations mod n).
Since n isn't divisible by 2, multiplying the equation by 2 is OK

(1/2)x(x+1) = (1/2)y(y+1) <=>
x(x+1) = y(y+1) <=>
(x+1/2)^2 + (1/4) = (y+1/2)^2 + (1/4) <=>
(2x+1)^2 = (2y+1)^2

so the difference of 2 squares is a multiple of n, and gcd(x-y, n) or gcd(x+y, n)
will give a factor.


\pi