Quote:
Originally Posted by sascha77
Thanks !!!
Yes it could be that there exist a counterexample.
But nobody knows this until it is found. ;)
A hint: You only need to test a and b to the size of p.
this means: test a for a<=p and b for b<=p
Because of the modulooperation these values of 2^a repeat after psteps.

You are looking at the intersection of two sparse sets (false witnesses
to 2^p1 and integers with Hamming weight 2) and hoping that the
intersection isn't empty.
There are no analytic tools available to approach the problem because
[AFAIK] there is almost nothing known about how false witnesses
are distributed mod P. It is easy to get a sharp counting function for
weight2 integers up to B , but their distribution is clearly not uniform.
Heuristics based on probabilistic methods are likely to fail, because
the sets involved are not uniformly distributed.
Even
if the result is true, it has almost no applicability anyway. LL will
be faster.