Solving x^2 + x + 1 == 0 (mod mp)
 

Is there a quick way to solve x^2 + x + 1 == 0 (mod mp), where mp is a Mersenne number, or just show that solutions exist? :smile:

[QUOTE=paulunderwood;449999]Is there a quick way to solve x^2 + x + 1 == 0 (mod mp), where mp is a Mersenne number, or just show that solutions exist? :smile:[/QUOTE]

you are stating:
[TEX]x^2+x+1\equiv 0 \pmod {2^p-1}
;x^2+x \equiv -1 \pmod {2^p-1} \equiv 2^p-2 \pmod {2^p-1} \equiv 2*(2^{p-1}-1) \pmod {2^p-1}[/TEX]
if x*(x+1) = 2*(2^(p-1)-1) and p=2 then 2*(2^1-1) = 2*1 is of the appropriate form. as for a general mersenne number I'm not sure.

realized this also is equivalent to [TEX](x+1)^2\equiv x \pmod {2^p-1}[/TEX] by adding x to both sides so really that transforms it into a quadratic residue question. of course then you get that the solution (x=2,p=3) exists.

[QUOTE=paulunderwood;449999]Is there a quick way to solve x^2 + x + 1 == 0 (mod mp), where mp is a Mersenne number, or just show that solutions exist? :smile:[/QUOTE]
[SPOILER]If x exists then it is a cubic root of 1.
Is 1 a cubic residue mod mp?[/SPOILER]

[QUOTE=paulunderwood;449999]Is there a quick way to solve x^2 + x + 1 == 0 (mod mp), where mp is a Mersenne number, or just show that solutions exist? :smile:[/QUOTE]

The solution exists in every case:
x1==(Mod(-3,2^p-1)^(2^(p-2))-1)/2 and
x2==(-Mod(-3,2^p-1)^(2^(p-2))-1)/2 (for p=2: x1==x2).

Or, simply, as if solving a normal quadratic equation..
D = b^2-4ac = -3
[TEX]x_{1,2} = {{-1 \pm sqrt D} \over 2}[/TEX]
Nice!
__ __ __ __ __

Can't we also solve it as the [TEX]\sqrt[\small 3] 1[/TEX]?
[CODE]L=[3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281];
for(i=1,#L,p=L[i];mp=2^p-1;\
forprime(g=3,99,r=Mod(g,mp)^(mp\3);if(r==1,next);print(p" "g" "lift(r));break) )
\\ the second root is r^2
\\ note: for p=2, g=2
[/CODE]
Robert's solution is faster!

Thanks guys.

Here is my code, building on others' codes:

[CODE]L=[3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281];
for(i=1,#L,p=L[i];mp=2^p-1;b=-3;for(k=2,p,b=b*b;hi=shift(b,-p);lo=bitand(b,mp);b=lo+hi;if(b>=mp,b-=mp));b=(b+3)==mp;print(p" "b))
[/CODE]

It might be wrong!

So same number of iterations as LL. All square operations like LL - but no pesky subtractions by 2!

[QUOTE=paulunderwood;450023]Thanks guys.

Here is my code, building on others' codes:

[CODE]L=[3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281];
for(i=1,#L,p=L[i];mp=2^p-1;b=-3;for(k=2,p,b=b*b;hi=shift(b,-p);lo=bitand(b,mp);b=lo+hi;if(b>=mp,b-=mp));b=(b+3)==mp;print(p" "b))
[/CODE]

It might be wrong!

So same number of iterations as LL. All square operations like LL - but no pesky subtractions by 2![/QUOTE]

you can speed this code up on some machines with alterations also I'm guessing you've seen the thread that comes along with: [url]http://mersenneforum.org/showthread.php?p=420677&highlight=lucaslehmer#post420677[/url] ? that may give you ideas putting in the b<0 clause from that thread sped it up a bit for me as did not having to calculate -p each time ( just calling p not saving -p's value) as did replacing b*b with norm(b). sometimes more operations simplifies the operations needed even but it all comes down to computation time in some respects. if one part didn't affect it there would be a way to incorporate norml2 for example.

I have coded up the test -3==Mod(81, 2^p-1)^2^(p-3) using George's gwnum library making good use of the function:

[CODE]/* If you know the result of a multiplication will be the input to another */
/* multiplication (but not gwsquare_carefully), then a small performance */
/* gain can be had in larger FFTs by doing some of the next forward FFT at */
/* the end of the multiplication. Call this macro to tell the */
/* multiplication code whether or not it can start the forward FFT on */
/* the result. */

void gwstartnextfft (gwhandle *gwdata, int state);[/CODE]

It runs as quick as Prime95/mprime (if not quicker?!)

myMersenne.c :

[CODE]#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "gwnum/giants.h"
#include "gwnum/gwnum.h"
#include "gwnum/gwcommon.h"

int i, n;
unsigned init_b[1] = { 81 };
giant gb;
gwnum wb;
gwhandle *gwdata;

int main ( int argc, char *argv[] ) {
if( argc != 2 ) {
printf( "Usage: myMersenne exponent\n" );
return;
}
n = atoi ( argv[1] );
printf ( "Mersenne testing M%d ...\n", n );

gb = newgiant ( ( n >> 2) + 8 );
gwdata = (gwhandle*) malloc ( sizeof ( gwhandle ) );
gwinit ( gwdata );
gwset_num_threads ( gwdata, 4 );
gwsetup ( gwdata, 1, 2, n, -1 );
wb = gwalloc ( gwdata );

binarytogw ( gwdata, init_b, 1, wb );
gwstartnextfft ( gwdata, 1 );
for ( i = n; i > 4; i-- ) gwsquare ( gwdata, wb );
gwstartnextfft ( gwdata, 0 );
gwsquare ( gwdata, wb );
gwsmalladd ( gwdata, 3.0, wb);

gwtogiant ( gwdata, wb, gb );
if ( isZero ( gb ) )
printf ( "Is Mersenne Prime!\n" );
else
printf ( "Not prime :(\n" );
}
//gwtogiant( gwdata, wb, gb );
//char string[100];
//gtoc( gb, string, 100 );
//printf( "s%s\n", string );
//gcc -o myMersenne myMersenne.c gwnum/gwnum.a gwnum/gwnum.ld -lm -lpthread -lstdc++

[/CODE]

Of course it is only to be used for fun and not for real testing, as Prime95/mprime interacts with the database server.

(Oh, don't test M3 :smile:)

[QUOTE=paulunderwood;450131]I have coded up the test -3==Mod(81, 2^p-1)^2^(p-3) using George's gwnum library ...[/QUOTE]
But using a vanilla P95 binary, a workunit
[CODE]::::worktodo.txt::::
PRP=1,2,p,-1[/CODE]is doing _[I]exactly[/I]_ the same, no?

[QUOTE=Batalov;450133]But using a vanilla P95 binary, a workunit
[CODE]::::worktodo.txt::::
PRP=1,2,p,-1[/CODE]is doing _[I]exactly[/I]_ the same, no?[/QUOTE]

Maybe, iff it does only squaring operations :unsure:

[QUOTE=Batalov;450133]But using a vanilla P95 binary, a workunit
[CODE]::::worktodo.txt::::
PRP=1,2,p,-1[/CODE]is doing _[I]exactly[/I]_ the same, no?[/QUOTE]

I given this some more thought.

PRP does Mod(3,mp)^(2^p-2) == 1,
which is at best Mod(3,mp)^2^p == 9,
whereas what I propose is Mod(3,mp)^2^(p-1) == -3. :smile: