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

paulunderwood · 2016-12-27, 17:47

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?

science_man_88 · 2016-12-27, 18:03

Quote:

Originally Posted by paulunderwood

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?

you are stating:
$x^2+x+1\equiv 0 \pmod {2^p-1}<br /> ;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}$
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 $(x+1)^2\equiv x \pmod {2^p-1}$ 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.

Batalov · 2016-12-27, 20:36

Quote:

Originally Posted by paulunderwood

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?

If x exists then it is a cubic root of 1.
Is 1 a cubic residue mod mp?

R. Gerbicz · 2016-12-27, 23:31

Quote:

Originally Posted by paulunderwood

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?

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).

Batalov · 2016-12-28, 01:00

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

Can't we also solve it as the $\sqrt[\small 3] 1$ ?

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

Robert's solution is faster!

paulunderwood · 2016-12-28, 02:08

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))

It might be wrong!

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

science_man_88 · 2016-12-28, 02:59

Quote:

Originally Posted by paulunderwood

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))

It might be wrong!

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

you can speed this code up on some machines with alterations also I'm guessing you've seen the thread that comes along with: http://mersenneforum.org/showthread....mer#post420677 ? 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.

paulunderwood · 2016-12-30, 02:29

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);

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++

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

)

Batalov · 2016-12-30, 03:06

Quote:

Originally Posted by paulunderwood

I have coded up the test -3==Mod(81, 2^p-1)^2^(p-3) using George's gwnum library ...

But using a vanilla P95 binary, a workunit

Code:

::::worktodo.txt::::
PRP=1,2,p,-1

is doing _exactly_ the same, no?

paulunderwood · 2016-12-30, 03:11

Quote:

Originally Posted by Batalov

But using a vanilla P95 binary, a workunit

Code:

::::worktodo.txt::::
PRP=1,2,p,-1

is doing _exactly_ the same, no?

Maybe, iff it does only squaring operations

paulunderwood · 2016-12-31, 08:57

Quote:

Originally Posted by Batalov

But using a vanilla P95 binary, a workunit

Code:

::::worktodo.txt::::
PRP=1,2,p,-1

is doing _exactly_ the same, no?

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.

2016-12-27, 17:47	#1
paulunderwood Sep 2002 Database er0rr 111010011011₂ Posts	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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Solving for x in Phi(n, x) = 0 (mod p)	carpetpool	Abstract Algebra & Algebraic Number Theory	1	2017-11-04 16:53
Solving systems of equations modulo n	carpetpool	carpetpool	2	2017-02-05 20:40
Solving x^2==1 (mod n)	paulunderwood	Miscellaneous Math	2	2016-12-30 07:34
New Method for Solving Linear Systems	Dubslow	Miscellaneous Math	24	2012-08-24 10:46
solving modular constraints	Joshua2	Homework Help	12	2010-02-19 22:59