Prime numbers and primality testing is a Restricted Group with 1112 members.
 Prime numbers and primality testing

 Restricted Group,
 1112 members
Primary Navigation
Re: Proposition for a better p1 and p+1 test
 0 Attachment
<bhelmes@> wrote:
> I propose the following unproven prime test
As remarked, no prime p = 1 mod 4 passes the test.
Here I show that the composite number
p = 2953*5167 = 15258151 = 7 mod 16
passes the test, using its minimal strong base, a = 3:
{p=15258151;x=13785839;y=8920588;xr=1472312;yr=6337563;
if(Mod(p,16)==7&&kronecker(2,p)==1&&kronecker(3,p)==1&&
Mod(3,p)^((p1)/2)==1&&x^23*y^2==Mod(1,p)&&
Mod(Mod(1,p)*(x+y*A),A^23)^p==xy*A&&
Mod(Mod(1,p)*(x+y*A),A^23)^((p+1)/8)==xr+yr*A&&
gcd(p,yr)==1&&!isprime(p),print(" fooled with minimal base"));}
fooled with minimal base
The gremlins will entertain no further wriggle from Bernhard.
David (their keeper) 0 Attachment
Dear David,
thank you for your efforts to find a counterexample.
I noticed that you did not used a solution of pell for a=3 with x^2ay^2=1
but the solution for x^2ay^2=1 mod p
I am not sure wether this makes a difference for the test.
I wish you a pleasant and peaceful weekend
Bernhard
 In primenumbers@yahoogroups.com, <david.broadhurst@...> wrote:
<bhelmes@> wrote:
> I propose the following unproven prime test
As remarked, no prime p = 1 mod 4 passes the test.
Here I show that the composite number
p = 2953*5167 = 15258151 = 7 mod 16
passes the test, using its minimal strong base, a = 3:
{p=15258151;x=13785839;y=8920588;xr=1472312;yr=6337563;
if(Mod(p,16)==7&&kronecker(2,p)==1&&kronecker(3,p)==1&&
Mod(3,p)^((p1)/2)==1&&x^23*y^2==Mod(1,p)&&
Mod(Mod(1,p)*(x+y*A),A^23)^p==xy*A&&
Mod(Mod(1,p)*(x+y*A),A^23)^((p+1)/8)==xr+yr*A&&
gcd(p,yr)==1&&!isprime(p),print(" fooled with minimal base"));}
fooled with minimal base
The gremlins will entertain no further wriggle from Bernhard.
David (their keeper) 0 Attachment
Bernhard Helmes wrote:
> you did not used a solution of pell for a=3 with x^2ay^2=1
There is an infinity of solutions to x^23*y^2 = 1,
with integers x and y.
Here are a few:
q=quadunit(12);r=1;for(k=1,20,r*=q;print([k,real(r),imag(r)]));
[1, 2, 1]
[2, 7, 4]
[3, 26, 15]
[4, 97, 56]
[5, 362, 209]
[6, 1351, 780]
[7, 5042, 2911]
[8, 18817, 10864]
[9, 70226, 40545]
[10, 262087, 151316]
[11, 978122, 564719]
[12, 3650401, 2107560]
[13, 13623482, 7865521]
[14, 50843527, 29354524]
[15, 189750626, 109552575]
[16, 708158977, 408855776]
[17, 2642885282, 1525870529]
[18, 9863382151, 5694626340]
[19, 36810643322, 21252634831]
[20, 137379191137, 79315912984]
How do you intend to prove that one pair of Pell's /infinite/
series does not correspond to my choice, modulo p?
That might take you some time :?
David 0 Attachment
 In primenumbers@yahoogroups.com, "djbroadhurst" wrote:
> How do you intend to prove that one pair of Pell's /infinite/
But it will not take for ever. It would be sufficient for
> series does not correspond to my choice, modulo p?
>
> That might take you some time :?
Bernhard to study less than 960,000 integers from
http://oeis.org/A001075> a(n) solves for x in x^2  3*y^2 = 1
Of these, the largest has less than 550,000 digits:
{stop=ceil(15258151/16);digs=#Str(real(quadunit(12)^stop));
print(stop"th Pell number has "digs" decimal digits");}
953635th Pell number has 545429 decimal digits
Happy hunting :)
David 0 Attachment
Dear David,>As remarked, no prime p = 1 mod 4 passes the test.
I would like to add that only the point 5. causes the trouble.
and that all primes passes the points 1.  4.>Here I show that the composite number
I feel that it was not easy for you and a lot of work for you to find one counterexample.
>p = 2953*5167 = 15258151 = 7 mod 16
>passes the test, using its minimal strong base, a = 3:
Besides i noticed that your selected x and y is kind of (x+yA)^4=1 mod p
which is very special and shows that the proposed test is not sufficient.
>The gremlins will entertain no further wriggle from Bernhard.
David, i have a huge respect for your mathematical skills,
nevertheless the description to entertain me is not what i expect from you.
This primenumber group is the only place for me to discuss some mathematical
ideas and to get some mathematical feedback.
As far as i can see a proven sufficient primetest with 4 Selfridge would be a mathematical progress
and the development of choosing the right parameters in order to build a proof is not a kind of "wriggle" but
mathematical work.
I appreciate deeply a fair mathematical discussion.
David, prime numbers are something for the eternity and there is no reason to get angry about some humble
mathematicians like me who try to learn some more details of number theory.
I wish you a pleasant and friendly weekend.
Bernhard
David (their keeper) 0 Attachment
Bernhard Helmes wrote:
> > As remarked, no prime p = 1 mod 4 passes the test.
So remove point (5) to allow primes p = 1 mod 4.
> I would like to add that only the point 5. causes the trouble.
Then it's /very/ easy to find a pseudoprime:
{p=3281;x=1062;y=1600;
if(kronecker(3,p)==1&&
Mod(3,p)^((p1)/2)==1&&
x^23*y^2==Mod(1,p)&&
Mod(Mod(1,p)*(x+y*A),A^23)^p==xy*A&&
!isprime(p),print(" fooled"));}
fooled
David 0 Attachment
 In primenumbers@yahoogroups.com,
"djbroadhurst" <david.broadhurst@...> wrote:
> {p=3281;x=1062;y=1600;
The gremlins now have more than 23,000 pseudoprimes
> if(kronecker(3,p)==1&&
> Mod(3,p)^((p1)/2)==1&&
> x^23*y^2==Mod(1,p)&&
> Mod(Mod(1,p)*(x+y*A),A^23)^p==xy*A&&
> !isprime(p),print(" fooled"));}
>
> fooled
that fool Bernhard's test. But before revealing them,
they await a response to the very simple case, above.
David 0 Attachment
Dear David,
the amount of counterexamples sounds impressively.
I suppose that there are a lot of p=1 mod 4.
I think that i will publish soon a test which separates between p=1 mod 4 and p=3 mod 4,
but i would like to check first some list by myself in order to save some time for you and to get
some more informations.
How does it feel to be a "keeper" of such a lot of interesting gremlins :)
A new and better proposition:
A. Let p an element of N with p=3 mod 4,
m the greatest power of 2 with 2^m*r=p+1
and 2^m < r
1. choose a prime a with jacobi (a, p)=1
2. Verify a^(p1)/2=1 mod p
3. Depending on the a choose the pell solution of x, y with
x^2ay^2=1 mod p
http://mathworld.wolfram.com/PellEquation.html
4. Verify that (x+yA)^(2^m)<>1 mod p with A=sqrt (a)
because gcd (p1, p+1) = 2
5. Calculate and verify (x+yA)^p=xyA mod p
6. Calculate (x+yA)^r=x(r)+y(r)A mod p and
verify that gcd (y(r), p)=1
(The point 6. derives of a factorisation test, is cheap and powerful
because gcd (y(n), p) > 1 results gcd (y(m), p) > 1 with m=n*t)
if 1.6. is ok. then p is a prime.
David, you will realize that i abstain form the choose of the smallest a
and that i add the point 4. for good reasons
I wish you a peaceful and pleasant weekend
Bernhard 0 Attachment
Bernhard Helmes wrote:
> A new and better proposition
The gremlins refuse to consider a
test that is not true for primes.
Consider, for example, the prime
p = 1037*2^81 = 265471
and set a = 3, x = 2, y = 1.
Then this prime fails your latest wriggle:
> (x+yA)^(2^m)<>1 mod p with A=sqrt(a)
print(Mod(Mod(1,265471)*(2+A),A^23)^(2^8));
Mod(Mod(1, 265471), A^2  3)
Please do not post probable primality "tests"
that are failed by primes.
David (trying to control the grumpy gremlins:) 0 Attachment
A peaceful day for all group members,
dear David,
I changed only the point 3.
Is this changement a sharper condition or is this mathematically seen the same ?
I. For p=3 mod 41. choose the smallest prime a with jacobi (a, p)=1
2. Verify a^(p1)/2=1 mod p
[This is the p1 test which proves that a is a non quadric residuum]
3. Depending on the a choose the pell solution of x, y with
x^2ay^2=1 mod p (the minus is the change :)
4. Calculate and verify (x+yA)^p=xyA mod p with A=sqrt (a)
5. m the greatest power of 2 with 2^m*r=p+1 and 2^m < rCalculate (x+yA)^r=x(r)+y(r)A mod p and
verify that gcd (y(r), p)=1
[This is a strong p+1 test with a solution of the according pell equation]
if 1.  5. is true then p should be a prime
I think that this "wriggle" will include that there exist a cycle group with order t > 2 and t  r
There is no need to hurry up for the gremlins,
the prime numbers will exist a little longer. ;)
Friendly greetings from the primes
Bernhard 0 Attachment
Bernhard Helmes wrote:
> the pell solution of x, y with x^2ay^2=1
For a=3 mod 4 there is no such thing.
Please do not post "tests" that refer
to nonexistent entities.David