mersenneforum.org Solving x^2 + x + 1 == 0 (mod mp)
 Register FAQ Search Today's Posts Mark Forums Read

 2016-12-27, 17:47 #1 paulunderwood     Sep 2002 Database er0rr 344910 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?
2016-12-27, 18:03   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

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}
;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.

Last fiddled with by science_man_88 on 2016-12-27 at 18:46

2016-12-27, 20:36   #3
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

216508 Posts

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?

2016-12-27, 23:31   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

17·83 Posts

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

Last fiddled with by R. Gerbicz on 2016-12-27 at 23:35 Reason: typo

 2016-12-28, 01:00 #5 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23×7×163 Posts 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!
 2016-12-28, 02:08 #6 paulunderwood     Sep 2002 Database er0rr 3,449 Posts 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! Last fiddled with by paulunderwood on 2016-12-28 at 02:48
2016-12-28, 02:59   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

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.

Last fiddled with by science_man_88 on 2016-12-28 at 03:18 Reason: typo

 2016-12-30, 02:29 #8 paulunderwood     Sep 2002 Database er0rr 1101011110012 Posts 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 #include #include #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 ) Last fiddled with by paulunderwood on 2016-12-30 at 02:40
2016-12-30, 03:06   #9
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts

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?

2016-12-30, 03:11   #10
paulunderwood

Sep 2002
Database er0rr

1101011110012 Posts

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

Last fiddled with by paulunderwood on 2016-12-30 at 03:12

2016-12-31, 08:57   #11
paulunderwood

Sep 2002
Database er0rr

3,449 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 1 2017-11-04 16:53 carpetpool carpetpool 2 2017-02-05 20:40 paulunderwood Miscellaneous Math 2 2016-12-30 07:34 Dubslow Miscellaneous Math 24 2012-08-24 10:46 Joshua2 Homework Help 12 2010-02-19 22:59

All times are UTC. The time now is 10:34.

Sat Oct 31 10:34:05 UTC 2020 up 51 days, 7:45, 2 users, load averages: 2.38, 2.00, 1.93