mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-09-16, 03:25   #23
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

173216 Posts
Default

I'm not sure what there is to understand. You posted a test which looked like a probable prime test. On examination, it seems like primes pass it, most composites fail, and some composites pass. This is exactly what we'd expect of a probable prime test. Are we missing something?
CRGreathouse is offline   Reply With Quote
Old 2020-09-16, 07:09   #24
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2×17 Posts
Default

Yes it is. There is my fault. If we look what exactly the last test doing - do the analytical result of powering matrix and computing spur, the result is polynomial of u with integer, positive and negative coefficients, that depend only on testing value of p.
In case p is prime, everyone of this coefficient is divided by p - > have p as factor, i.e.
the result is in form G(u)=p*g(u) (1)
so G(u)==0 (mod p) (2)
Ok? This is true ONLY for prime numbers, and certainly is is profitable!!! I have the marvelous proof) and i'm sure most of mathematicians can write the proof.
In (1) notation, test will be 100% accurate. No pseudoprimes pass the test in this form, do You understand this?

But here, we in the not good situation. We use notation (2).
Let me explain a bit further. When p is not prime, we can be in the situation, when for some not prime p, G(u) do not have p as factor, but instead the value G(u) for some u is divided by p so G(u) ==0 (mod p) and we stuck with our beloved f@cked pseodoprimes forever))) Time to time, test to test, nothing changes

Last fiddled with by RMLabrador on 2020-09-16 at 07:09 Reason: u
RMLabrador is offline   Reply With Quote
Old 2020-09-16, 12:57   #25
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

3410 Posts
Default

Until now!
Do You Listen to the wind of changes?))

As i can see, this is u-independent test, u do not needed at least in theory, and can be =0.
At this place, i can easy do the wrong statement,
mainly because i see other way to final step.

In spite of that, this lookalike to be final or final-1 iteration))))

Click image for larger version

Name:	CodeCogsEqn (5).gif
Views:	33
Size:	10.5 KB
ID:	23337

P/S/ u is needed for be honest(and correct). I'm talk about oscillation for small u, when we compute modulo AFTER power.

Last fiddled with by RMLabrador on 2020-09-16 at 13:04
RMLabrador is offline   Reply With Quote
Old 2020-09-16, 13:42   #26
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·19·23 Posts
Default

Once again it is meaningless to talk about "u>log(p)^2" when working with modular arithmetic. Also it makes absolutely no difference where you apply modulo operations. It is a "multiplicative operation" -- powering is repeated multiplication.

Composite example:

Code:
{forstep(n=7,1000000000,2,if(!ispseudoprime(n),
for(u=0,n,A=Mod(Mod([i+1,1;1,u],n),i^2+1)^(n);
Tr=lift(lift(trace(A)))%i;Ti=lift(lift(trace(A*i)))%i;F=Mod(u,n)^n+1;
if(Tr==F&&(Ti==1||Ti==n-1),
print([n,u,lift(lift(A))]);break(2)))))}
[861, 783, [493*i + 616, 492*i + 1; 492*i + 1, 369*i + 168]]

Last fiddled with by paulunderwood on 2020-09-16 at 13:44
paulunderwood is offline   Reply With Quote
Old 2020-09-16, 13:56   #27
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3,793 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
Yes it is. There is my fault. If we look what exactly the last test doing - do the analytical result of powering matrix and computing spur, the result is polynomial of u with integer, positive and negative coefficients, that depend only on testing value of p.
In case p is prime, everyone of this coefficient is divided by p - > have p as factor, i.e.
the result is in form G(u)=p*g(u) (1)
so G(u)==0 (mod p) (2)
Ok?
No. This isn't what your paper says (it does give a result about the off-diagonal entry of Ap however). The trace polynomials are monic, with constant terms given by Lucas numbers. For prime index, the other coefficients appear to be divisible by p for p prime. I'm too lazy to check.

Code:
? A=[1,1;1,u];P=[1,0;0,1];for(i=1,13,P*=A;if(isprime(i),print(i" "trace(P))))
2 u^2 + 3
3 u^3 + 3*u + 4
5 u^5 + 5*u^3 + 5*u^2 + 10*u + 11
7 u^7 + 7*u^5 + 7*u^4 + 21*u^3 + 28*u^2 + 35*u + 29
11 u^11 + 11*u^9 + 11*u^8 + 55*u^7 + 88*u^6 + 187*u^5 + 286*u^4 + 396*u^3 + 440*u^2 + 374*u + 199
13 u^13 + 13*u^11 + 13*u^10 + 78*u^9 + 130*u^8 + 325*u^7 + 559*u^6 + 936*u^5 + 1313*u^4 + 1586*u^3 + 1560*u^2 + 1157*u + 521
Quote:
This is true ONLY for prime numbers, and certainly is is profitable!!!
Just out of curiosity, how does the amount of computation required to produce these polynomials compare to the amount required to test p by Wilson's Theorem?
Dr Sardonicus is offline   Reply With Quote
Old 2020-09-16, 14:04   #28
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2×17 Posts
Default

No need to compute them all. Answer in the symmetry of this polynoms/
Just try compare their value modulo p for u and then for p-u+2 when p is prime
Here http:\\romanvm-prime.com this is theorem 2
in this form, there only Charmicael numbers look like the one, that pass the test. and even for them this is coincedence
they do not have a factor

Last fiddled with by RMLabrador on 2020-09-16 at 14:06
RMLabrador is offline   Reply With Quote
Old 2020-09-16, 19:18   #29
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by RMLabrador View Post
in this form, there only Charmicael numbers look like the one, that pass the test. and even for them this is coincedence
they do not have a factor
This sounds very much like a pseudoprime test, if I understand your English.
CRGreathouse is offline   Reply With Quote
Old 2020-09-17, 03:33   #30
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×53 Posts
Post

I agree with CRGreathouse. Seems like a pseudoprime (PRP) test. The test can be generalized to higher level matrices. With 2 x 2 matrix test:

For any integer n, if we have (gp):

Code:
lift(trace(Mod([a,b; c,d],n)^n)) == (a^n + d^n)
then n is prime. The binomial theorem provides a proof of this

\((a + d)^{n} \equiv a^{n} + d^{n} \pmod n\)

Then

\((a + d)^{n} = \sum_{i = 0}^{n} \binom{n}{i} a^{n-i}d^{i}\)

The expansion of this shows all coefficients except the last two are divisible by n, so the congruence will hold. They form Pascal's triangle:

\(1\)
\(1, 1\)
\(1, 2, 1\)
\(1, 3, 3, 1\)
\(1, 4, 6, 4, 1\)
\(1, 5, 10, 10, 5 1\)
\(1, 6, 15, 20, 15, 6, 1\)
\(1, 7, 21, 35, 35, 21, 7, 1\)
\(...\)

These coefficients appear in the expansion of

Code:
lift(trace([a,b; c,d])^n)
So it is clear that the only terms on the n-th row not divisible by n are the first and last terms.

The sequences for polynomial functions of integers in the k-th column are given by:

\(c_0 = 1\)
\(c_1 = n\)
\(c_2 = \frac{n^{2} - n}{2}\)
\(c_3 = \frac{n^{3} - 3n^{2} + 2n}{6}\)
\(c_4 = \frac{n^{4} - 6n^{3} + 11n^{2} - 6n}{24}\)
\(c_5 = \frac{n^{5} - 10n^{4} + 35n^{3} - 50n^{2} + 24n}{120}\)
...
\[c_n = \frac{\prod_{i=0}^{k-1}{n-i}}{k!}\]

Here are a few such generalizations I had in mind involving a 4 x 4 matrix:

Code:
(20:11) gp > for(n=j,16, print(lift(trace(([0,1,1,1; 1,1,1,1; 1,1,1,1; 1,1,1,x])^n))))
x + 2
x^2 + 14
x^3 + 9*x + 44
x^4 + 12*x^2 + 32*x + 162
x^5 + 15*x^3 + 40*x^2 + 155*x + 572
x^6 + 18*x^4 + 48*x^3 + 213*x^2 + 648*x + 2042
x^7 + 21*x^5 + 56*x^4 + 280*x^3 + 924*x^2 + 2709*x + 7268
x^8 + 24*x^6 + 64*x^5 + 356*x^4 + 1248*x^3 + 4096*x^2 + 11008*x + 25890
x^9 + 27*x^7 + 72*x^6 + 441*x^5 + 1620*x^4 + 5814*x^3 + 17532*x^2 + 44127*x + 92204
x^10 + 30*x^8 + 80*x^7 + 535*x^6 + 2040*x^5 + 7890*x^4 + 25920*x^3 + 74085*x^2 + 174600*x + 328394
x^11 + 33*x^9 + 88*x^8 + 638*x^7 + 2508*x^6 + 10351*x^5 + 36388*x^4 + 114235*x^3 + 308352*x^2 + 684057*x + 1169588
x^12 + 36*x^10 + 96*x^9 + 750*x^8 + 3024*x^7 + 13224*x^6 + 49152*x^5 + 166233*x^4 + 494816*x^3 + 1268796*x^2 + 2657760*x + 4165554
x^13 + 39*x^11 + 104*x^10 + 871*x^9 + 3588*x^8 + 16536*x^7 + 64428*x^6 + 231816*x^5 + 744692*x^4 + 2116569*x^3 + 5167968*x^2 + 10254595*x + 14835836
x^14 + 42*x^12 + 112*x^11 + 1001*x^10 + 4200*x^9 + 20314*x^8 + 82432*x^7 + 312802*x^6 + 1069544*x^5 + 3291792*x^4 + 8949360*x^3 + 20867581*x^2 + 39331656*x + 52838618
x^15 + 45*x^13 + 120*x^12 + 1140*x^11 + 4860*x^10 + 24585*x^9 + 103380*x^8 + 411090*x^7 + 1481800*x^6 + 4866414*x^5 + 14366100*x^4 + 37465250*x^3 + 83619540*x^2 + 150087645*x + 188187524
x^16 + 48*x^14 + 128*x^13 + 1288*x^12 + 5568*x^11 + 29376*x^10 + 127488*x^9 + 528660*x^8 + 1994752*x^7 + 6920160*x^6 + 21837312*x^5 + 62013936*x^4 + 155458880*x^3 + 332828064*x^2 + 570181376*x + 670239810
....

The coefficients are

c0 = 1
c1 = 0
c2 = 3*n
c3 = 8*n+24
c4 = (9*n^2+17*n)/2
c5 = 24*n^2 - 36*n
...

However, degree(cn) ≠ n. This appears to be significantly weaker than the original 2 x 2 matrix test (Fermat's Little Theorem). I suppose there could be a way to construct a series of coefficients with degree(cn) = n which Carmichael Numbers could potentially fail. If I had more time, I would probably search for a better example, but at least you get the point now.


My second idea involves using coefficents of the form

\[c_n = \frac{\prod_{i=0}^{k-1}{n-P(i)}}{P_{k}}\]

where

\[P_{k} = \prod_{i=0}^{k-1}{P(i)}\]

Last fiddled with by carpetpool on 2020-09-17 at 03:40 Reason: I'm still not used to TeX format here, so I apologize if things don't look as neat.
carpetpool is offline   Reply With Quote
Old 2020-09-17, 06:24   #31
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2·17 Posts
Default

The symmetry is the key to build test.I'm the only one here who sees symmetry???
check this.Click image for larger version

Name:	CodeCogsEqn (7).gif
Views:	38
Size:	11.9 KB
ID:	23343
in this form, no counterexamples, no one pseudoprime will pass this test. Problem in computation of this numerical.
You can do this analytically and see the difference with numerical computation - Carmichael numbers pass the test if we use modulo form
i/e/ b(u)-b(p-u+2) == 0 (mod p) but in reality, they do not have the p as factor.

And next step is to show or proof that is we have "exception" for some u in form [u,-1;-1,1]
(see the very beginning of this tread)
this "exception" do not break the symmetry if we (unavoidable) using modulo computation.
i'm relay on the Google-crutch, and even for myself, hard to understand some point after Google-translate)
We need the test!
RMLabrador is offline   Reply With Quote
Old 2020-09-17, 07:04   #32
RMLabrador
 
RMLabrador's Avatar
 
"Roman V. Makarchuk"
Aug 2020
Ukraine

2216 Posts
Default

Ще один спосіб - вивести формулу для коеффіцієнтів поліному b(u). Звичайно, перевіряти подільність кожного з них на число p буде досить маразматично, однак цілком можливо, що така формула дасть можливість винести p за дужки, без виконання занадто громіздких за об'ємом обчислень, тобто аналітично. А можливо і навпаки - отримаємо аналог теореми Вільсона, тільки з купою факторіалів та біноміальних коєффіцієнтів.
Імовірно, для суми коеффіцієнтів така формула буде точно існувати, однак тест у такій формі все ж буде імовірнісним (PRP).

Another way is to derive a formula for the coefficients of the polynomial b (u). Of course, to check the divisibility of each of them by the number p will be quite marasmic, but it is possible that such a formula will make it possible to make p in parentheses, without performing too cumbersome calculations, ie analytically. And perhaps vice versa - we get an analogue of Wilson's theorem, only with a bunch of factorials and binomial coefficients.
It is likely that such a formula will exist for the sum of the coefficients, but the test in this form will still be probabilistic (PRP).
RMLabrador is offline   Reply With Quote
Old 2020-09-17, 12:47   #33
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

1110110100012 Posts
Default

Regarding the use of polynomial coefficients to prove primality, there is already a well-known deterministic test, the AKS primality test. See the following 2004 paper for more details.

Last fiddled with by Dr Sardonicus on 2020-09-17 at 12:48 Reason: Omit unnecessary words!
Dr Sardonicus 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 01:05.

Thu Nov 26 01:05:55 UTC 2020 up 76 days, 22:16, 3 users, load averages: 1.44, 1.84, 1.72

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.