mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-09-11, 12:35   #1
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

1000102 Posts
Default A Universally derided "primality test".

Hi,
Information here.

http://romanvm-prime.com/

Regards,
Roman V. Makarchuk

Last fiddled with by Uncwilly on 2020-09-22 at 17:50
RMLabrador is offline   Reply With Quote
Old 2020-09-11, 14:47   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,723 Posts
Default

Code:
[n,u]=[231, 65];Mod([1,1;1,u],n)^n==[u,-1;-1,1]
1
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?

Last fiddled with by paulunderwood on 2020-09-11 at 14:57
paulunderwood is offline   Reply With Quote
Old 2020-09-11, 15:40   #3
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2×17 Posts
Default

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.

Last fiddled with by RMLabrador on 2020-09-11 at 15:44
RMLabrador is offline   Reply With Quote
Old 2020-09-11, 16:15   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D7616 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
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.
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
Quote:
Quote:
Theorem 2 is ill-defined. What are a(u) and c(u). Can you give a numerical example how this works?
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.
I will have to think more about what you are writing.

Last fiddled with by paulunderwood on 2020-09-11 at 16:15
paulunderwood is offline   Reply With Quote
Old 2020-09-11, 16:42   #5
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2×17 Posts
Default

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.
RMLabrador is offline   Reply With Quote
Old 2020-09-11, 16:56   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D7616 Posts
Default

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).

Last fiddled with by paulunderwood on 2020-09-11 at 16:57
paulunderwood is offline   Reply With Quote
Old 2020-09-11, 19:51   #7
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2×17 Posts
Default

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?

And please check this too

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

Last fiddled with by RMLabrador on 2020-09-11 at 20:25
RMLabrador is offline   Reply With Quote
Old 2020-09-12, 12:47   #8
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

428 Posts
Default

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

romanvm-prime

Last fiddled with by Uncwilly on 2020-09-12 at 17:02 Reason: You have already posted your URL twice. No need to spam.
RMLabrador is offline   Reply With Quote
Old 2020-09-12, 15:01   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101011101102 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
See the real test on the page, Theorem 4 below on page. United Magic of Symmetry and Complex Numbers)

romanvm-prime.com
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]
Your "theorem" is wrong.
paulunderwood is offline   Reply With Quote
Old 2020-09-12, 20:05   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·1,787 Posts
Default

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, i2 == -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

Last fiddled with by Dr Sardonicus on 2020-09-12 at 20:08 Reason: xingif ostpy
Dr Sardonicus is offline   Reply With Quote
Old 2020-09-13, 15:31   #11
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2·17 Posts
Default

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 second 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
RMLabrador is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I found the primality test, there seems to be no composite numbers that pass the test sweety439 sweety439 7 2020-02-11 19:49
+/- 6 Primality Test a1call Miscellaneous Math 29 2018-12-24 01:42
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
there is another way to test the primality of a no shawn Miscellaneous Math 5 2007-07-17 17:55
A primality test for Fermat numbers faster than P├ępin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 16:14.

Mon Oct 26 16:14:32 UTC 2020 up 46 days, 13:25, 0 users, load averages: 1.42, 1.83, 1.81

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.