mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2016-12-27, 17:47   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

344910 Posts
Default 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?
paulunderwood is offline   Reply With Quote
Old 2016-12-27, 18:03   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.

Last fiddled with by science_man_88 on 2016-12-27 at 18:46
science_man_88 is offline   Reply With Quote
Old 2016-12-27, 20:36   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

216508 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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?
Batalov is offline   Reply With Quote
Old 2016-12-27, 23:31   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17·83 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2016-12-28, 01:00   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts
Default

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!
Batalov is offline   Reply With Quote
Old 2016-12-28, 02:08   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,449 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2016-12-28, 02:59   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-12-30, 02:29   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101011110012 Posts
Default

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 )

Last fiddled with by paulunderwood on 2016-12-30 at 02:40
paulunderwood is offline   Reply With Quote
Old 2016-12-30, 03:06   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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?
Batalov is offline   Reply With Quote
Old 2016-12-30, 03:11   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101011110012 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
paulunderwood is offline   Reply With Quote
Old 2016-12-31, 08:57   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,449 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
paulunderwood is offline   Reply With Quote
Reply

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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.