 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   A Universally derided "primality test". (https://www.mersenneforum.org/showthread.php?t=25944)

A Universally derided "primality test".

Hi,
Information here.

[url]http://romanvm-prime.com/[/url]

Regards,
Roman V. Makarchuk

 paulunderwood 2020-09-11 14:47

[CODE][n,u]=[231, 65];Mod([1,1;1,u],n)^n==[u,-1;-1,1]
1
[/CODE]

Theorem 1 also works for composites. Testing (n-1)/2 times with different u is infeasible for large n.

Theorem 2 is ill-defined. What are a(u) and c(u). Can you give a numerical example how this works?

Theorem 1 also works for composites.
Yes.There is a lot of exeption. For some values u. Carmichael numbers do it even for many of u, but there is not a problem.
Not exist such exeption that have BOTH type of resudials for some different u, if so, this numbers is prime.

Theorem 2 is ill-defined. What are a(u) and c(u). Can you give a numerical example how this works?[/QUOTE]

a(u), c(u), b(u) - polynomial of u, result of analytical powering of matrix.
p=5
u^4+u^3+4u^2+5u+5 (1)
5-u+2=7-u, substitute
u^4-29u^3+319u^2-1580u+2980 (2)

(1)-(2)=5(2u-7)(3u^2-21u+85)
(2u-7)(3u^2-21u+85) = g(u)

5=p
That true ONLY if p is prime.

 paulunderwood 2020-09-11 16:15

[QUOTE=RMLabrador;556735]Theorem 1 also works for composites.
Yes.There is a lot of exeption. For some values u. Carmichael numbers do it even for many of u, but there is not a problem.
Not exist such exeption that have BOTH type of resudials for some different u, if so, this numbers is prime.
[/quote]

[CODE][n,u,w]=[1247, 601, 638];Mod([1,1;1,u],n)^(n)==[u,-1;-1,1]&&Mod([1,1;1,w],n)^(n)==[1,1;1,w]
1
[/CODE]

[quote][quote]
Theorem 2 is ill-defined. What are a(u) and c(u). Can you give a numerical example how this works?[/QUOTE]

a(u), c(u), b(u) - polynomial of u, result of analytical powering of matrix.
p=5
u^4+u^3+4u^2+5u+5 (1)
5-u+2=7-u, substitute
u^4-29u^3+319u^2-1580u+2980 (2)

(1)-(2)=5(2u-7)(3u^2-21u+85)
(2u-7)(3u^2-21u+85) = g(u)

5=p
That true ONLY if p is prime.[/QUOTE]

I will have to think more about what you are writing.

Thank You for advice! You are right! And I'm right too when talk about symmetry of resudials, ok 1247 - 601 and 638? try 1247-601+2 and 1247-638+2. For prime numbers, such symmetry exist; Sorry for take Your time, I'm just not search for ordinary exeptions, I'm find out such of them that break the symmetry.

 paulunderwood 2020-09-11 16:56

The characteristic equations of the matrices are:

x^2 - (1+u)*x + u-1 == 0 and
x^2 - (1+w)*x + w-1 == 0

The "residuals" depend on the jacobi symbol of the discriminants of these equations:

Jacobi((1+u)^2-4(u-1), n)
jacobi((1+w)^2-4(w-1), n)

If the Jacobi symbol is 1 then the matrical test is a glorified Fermat PRP test. If the symbol is -1 then it is a lucas-based test.

Recieved wisdom says that any Fermat+Lucas test has counterexamples for freely varying parameters (unless maybe the choice of u and w are more restricted -- which is what I am currently studying).

I'm refined condition of my Theorem 2)) If we write this in modulo form, we got Carmichael numbers as exception for some u, in strict form there in no exeption. Modulo form have a flaw...
I guess, You see my point? First, about symmetry and modulo flaw?

[url]http://romanvm-prime.com/?page_id=145[/url]

See the real test on the page, Theorem 4 below on page. United Magic of Symmetry and Complex Numbers)

romanvm-prime

 paulunderwood 2020-09-12 15:01

[QUOTE=RMLabrador;556799]See the real test on the page, Theorem 4 below on page. United Magic of Symmetry and Complex Numbers)

[URL="http://romanvm-prime.com"]romanvm-prime.com[/URL][/QUOTE]

[CODE]n=3225601;A=Mod(Mod([1+x,1;1,0],n),x^2+1);B=Mod(Mod([1,1;1,x],n),x^2+1);R=lift(lift(A^n-B^n));print(R)
[x, 0; 0, 3225600*x]
[/CODE]

 Dr Sardonicus 2020-09-12 20:05

I did notice one unusual situation:

The characteristic polynomial is x^2 - (u + 1)*x + (u - 1); the discriminant is u^2 - 2*u + 5. As long as this is nonzero (mod p), there are two eigenvalues, and it is at least not insane to think about diagonalizing the matrix, which might be probative.

If p == 1 (mod 4) however, i[sup]2[/sup] == -1 (mod p) has two solutions. Taking u = 1 + 2*i makes the discriminant of the characteristic polynomial 0, so it has a repeated factor:

x^2 - (2 + 2*i)*x + 2*i = (x - (1 + i))^2.

In this case, there is only one eigenvalue, 1 + i, of multiplicity 2. The matrix A - (1+i)I (I = 2x2 identity matrix) is (using Pari-GP syntax) N = [-i,1;1,i] which is nilpotent of index 2. Either column [-i;1] or [1;i] of N serves as an eigenvector of A.

Thus A = (1 + i)*I + N. Also, I and N commute, so A^p == (1+i)^p*I + N^p (mod p), and N^p is the 2x2 zero matrix.

Thus, A^p == (1+i)^p*I == (1 + i)*I (mod p) in this case.

Examples:

p = 5, i = 2, u = 1 + 2*2 = 0, 1 + i = 3; or i = 3, u = 1 + 2*3 = 2, 1 + i = 4
p = 13, i = 5, u = 1 = 2*5 = 11, 1 + i = 6; or i = 8, u = 1 + 2*8 = 4, 1 + i = 9

Very nice! I love this place.
I talk that using modulo computation lead to false "exception" and once again do it by themselves))
We must do something with to avoid error like this P*B == 0 mod P situation where part P must be an outcome of the test and give 0. Most of false "exception" arise from this, when B is some polynomial, and B give zero to us for some test condition for non-prime P instead of expected P

Can not emphasize this more clearly in my poor English
Do You understand me?

We can build such test. Symmetry is one of the game changer.
The [B]second[/B] way exist too.
We can not deal with modulo and we can not (at lest now) do the test without modulo))
Once again, go to the bottom of my page

All times are UTC. The time now is 08:24.