- --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>

Well, I found a counterexample:

>

>

>

>

> --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:

>

> > > I have stream-lined the definition:

> > > gcd(n,30)==1

> > > gcd(x*y,n)==1

> > > gcd(x^2-y^2,n)==1

> > > kronecker(x^2-4,n)==-1

> > > kronecker(y^2-4,n)==-1

>

> > Mod(Mod(1,n)*(x*l-3),l^2-x*l+1)^(n+1)+2*x^2-9==0

> > Mod(Mod(1,n)*(y*l-3),l^2-y*l+1)^(n+1)+2*y^2-9==0

> >

>

n=143989

x=2479

y=6796

> When calculating the left to right binary ladder, for each bit a square is performed and if the bit is "1" then a multiplication by the base is done. The results also need to be reduced modulo "n".

The single minimal x test -- 2 selfridges -- has reached 10^9 without a counterexample.

>

> For squaring of an intermediate value a*l+b and noting l^2=x*l-1:

> (a*l+b)^2==a^2*l^2+2*a*b*l+b^2

> ==a^2*(x*l-1)+2*a*b*l+b^2

> ==a*(a*x+2*b)*l-(a^2-b^2)

> ==a*(a*x-2*b)*l-(a-b)*(a+b)

> Since "x" is small there are:

> 2 small multiplications

> 3 small additions

> 3 small modular reductions

> 2 multiplications

> 2 modular reductions

>

> If there is a bit set multiplication by the base is performed:

> (a*l+b)(x*l-3)==a*x*l^2-3*a*l+b*x*l-3*b

> ==a*x*(x*l-1)-(3*a-b*x)*l-3*b

> ==(a*x^2-3*a+b*x)*l-a*x-3*b

> The operations are:

> 5 small multiplications

> 3 small additions

> 2 small modular reductions

>

> So for a random bit:

> 4.5 small multiplications

> 4.5 small additions

> 3.5 small modular reductions

> 2 multiplications

> 2 modular reductions

>

> By choosing just a minimal "x>0", this (single) test (on "x") is faster than Baillie-PSW, which requires at least 3 full multiplications and modular reductions for each bit,

>

> I have just checked the algorithm to 10^8...

>

In a way BPSW is better because of it does a base 2 fermat test first.

Paul - --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>

Combining fails with the composite counterexample n=256999 and x=32768, However, I have tested the 1+1+1+2 conjecture up to n<10^7,

>

>

> --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:

> >

> > Hi,

> >

> > I have added a Fermat test to make a 1+1+1+2 selfridge test:

> >

> > For N>5, with gcd(6,N)==1, find an integer x:

> > gcd(x^3-x,N)==1

> > kronecker(x^2-4,N)==-1

> >

> > and check:

> > (x+2)^((N-1)/2)==kronecker(x+2,N) (mod N) (Euler)

> > (x-2)^((N-1)/2)==kronecker(x-2,N) (mod N) (Euler)

> > x^(N-1)==1 (mod N) (Fermat)

> > L^(N+1) == 1 (mod N, L^2-x*L+1) (Lucas)

> >

>

> Note: I should say gcd(30,N)==1 because gcd(x^3-x,N)==1 and kronecker(x^2-4,n)==-1.

>

> Re: http://tech.groups.yahoo.com/group/primenumbers/message/24090?l=1

>

> Now consider combining the 2 Euler tests with the Lucas test:

>

> (L*D)^((n+1)/2)==D (mod N, L^2-x*L+1) (D=x^2-4.)

>

> with the restriction kronecker(x+2,N)==-1.

>

> These together with the Fermat test makes for a 1+2-selfridge test.

>

> Can you find a counterexample?

>

> So far the near-refutation from Pinch's carmichael list is:

> N,x,gcd(x^2-1)

> ------------------

> 1909001 884658 1909001

>

> Paul

>

Paul -- restoring symmetry