20161227, 17:47  #1 
Sep 2002
Database er0rr
3449_{10} 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?

20161227, 18:03  #2  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:
if x*(x+1) = 2*(2^(p1)1) and p=2 then 2*(2^11) = 2*1 is of the appropriate form. as for a general mersenne number I'm not sure. realized this also is equivalent to 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 20161227 at 18:46 

20161227, 20:36  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
21650_{8} Posts 

20161227, 23:31  #4  
"Robert Gerbicz"
Oct 2005
Hungary
17·83 Posts 
Quote:
x1==(Mod(3,2^p1)^(2^(p2))1)/2 and x2==(Mod(3,2^p1)^(2^(p2))1)/2 (for p=2: x1==x2). Last fiddled with by R. Gerbicz on 20161227 at 23:35 Reason: typo 

20161228, 01:00  #5 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}×7×163 Posts 
Or, simply, as if solving a normal quadratic equation..
D = b^24ac = 3 Nice! __ __ __ __ __ Can't we also solve it as the ? 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^p1;\ 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 
20161228, 02:08  #6 
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^p1;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)) So same number of iterations as LL. All square operations like LL  but no pesky subtractions by 2! Last fiddled with by paulunderwood on 20161228 at 02:48 
20161228, 02:59  #7  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:
Last fiddled with by science_man_88 on 20161228 at 03:18 Reason: typo 

20161230, 02:29  #8 
Sep 2002
Database er0rr
110101111001_{2} Posts 
I have coded up the test 3==Mod(81, 2^p1)^2^(p3) 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); 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++ (Oh, don't test M3 ) Last fiddled with by paulunderwood on 20161230 at 02:40 
20161230, 03:06  #9 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}×7×163 Posts 

20161230, 03:11  #10 
Sep 2002
Database er0rr
110101111001_{2} Posts 
Maybe, iff it does only squaring operations
Last fiddled with by paulunderwood on 20161230 at 03:12 
20161231, 08:57  #11  
Sep 2002
Database er0rr
3,449 Posts 
Quote:
PRP does Mod(3,mp)^(2^p2) == 1, which is at best Mod(3,mp)^2^p == 9, whereas what I propose is Mod(3,mp)^2^(p1) == 3. 

Thread Tools  
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  20171104 16:53 
Solving systems of equations modulo n  carpetpool  carpetpool  2  20170205 20:40 
Solving x^2==1 (mod n)  paulunderwood  Miscellaneous Math  2  20161230 07:34 
New Method for Solving Linear Systems  Dubslow  Miscellaneous Math  24  20120824 10:46 
solving modular constraints  Joshua2  Homework Help  12  20100219 22:59 