mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-04-18, 02:51   #1
LarsNet
 
Mar 2021

110002 Posts
Minus I noticed that only prime mersennes are quad_residue's of 9, has this been noticed before?

I noticed that only prime mersennes are quad_residue's of 9, (as opposed to non mersenne primes) has this been noticed before?
I didn't find it on a google search so wanted to ask here.

Code:
In [396]: for x in (2**p-1 for p in range(3,608)): 
     ...:    xx = quad_residue(9, x) 
     ...:    if xx == 1: print(x.bit_length()) 
     ...:                                                                                                                                                      

3
5
7
13
17
19
31
61
89
107
127
521
607

Last fiddled with by LarsNet on 2021-04-18 at 03:05
LarsNet is offline   Reply With Quote
Old 2021-04-18, 04:08   #2
srow7
 
Jul 2014

3·17 Posts
Default

what is quad_residue ?
(the math and the subroutine)
srow7 is offline   Reply With Quote
Old 2021-04-18, 04:23   #3
LarsNet
 
Mar 2021

23×3 Posts
Default

srow7, Note this only works for mersenne numbers and can be increased in speed by 10-16x by using gmpy2. The code is in python as i haven't written a c version yet ( it is the math from https://en.wikipedia.org/wiki/Quadratic_residue ):

Code:
def quad_residue_mersenne(a,n):

    mask = n

    def mer_rem(x, bits): 
      # Below is same as:   return x % mask 
      while True: 
          r = 0
          while x != 0: 
              r += x & mask 
              x >>= bits 
          if r == mask: 
              r = 0
          if r < mask: 
              return r 
          x = r 

    #checks if a is quad residue of n
    l=1
    q=(n-1)//2
    x = q**l
    if x==0:
        return 1
        
    a =a%n
    z=1
    while x!= 0:
        if x%2==0:
            a=mer_rem((a **2), n.bit_length())
            x//= 2
        else:
            x-=1
            z=mer_rem((z*a), n.bit_length())

    return z
Here is version that uses gmpy2, but isn't the quad residue version, it just produces the same result, an answer of 9 always for mersenne primes as opposed to non mersenne primes:

Code:
import gmpy2

def makersmark(n):
  z = 9
  mask = gmpy2.mpz((1<<n)-1)
  
  def mer_rem(x, bits): 
      # Below is same as:   return x % mask 
      while True: 
          r = gmpy2.mpz(0) 
          while x != 0: 
              r += x & mask 
              x >>= bits 
          if r == mask: 
              r = gmpy2.mpz(0) 
          if r < mask: 
              return r 
          x = r 
        
  z = gmpy2.mpz(z)
  n = gmpy2.mpz(n)       
  for x in range(n-1):
     z = mer_rem(z * z, n)
     print(z)
  return z == 9
makersmark is as fast as lucas lehmer, and much faster than quad_residue, i just noticed that they are corollary.

Last fiddled with by LarsNet on 2021-04-18 at 04:36
LarsNet is offline   Reply With Quote
Old 2021-04-18, 04:43   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,009 Posts
Default

A PARI-GP version.

I find it quite interesting. Well done, LarsNet!


Code:

\\DXT-100-A

forprime (p=2,19^4,{
    primeFlag=1;
    iferr(qr = qfbprimeform(9, (2^p-1)), E,primeFlag=0;next(););
    print ("M",p);
})


Code:
M2
M3
M5
M7
M13
M17
M19
M31
M61
M89
M107
M127
M521
M607
M1279
M2203
M2281
M3217
M4253
M4423
M9689
M9941
M11213
M19937
M21701
M23209
ETA It works for M2 as well.

ETA II You don't happen to be a Baháʼí now, do you?

ETA III It seems to work perfectly with other values than 9 such as 49, 81. 121.

Last fiddled with by a1call on 2021-04-18 at 05:42
a1call is offline   Reply With Quote
Old 2021-04-18, 05:47   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,009 Posts
Default

ETA IV, Please ignore ETA III, M11 passes with 121, but not with 9.
a1call is offline   Reply With Quote
Old 2021-04-18, 06:29   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24E516 Posts
Default

That's a red herring, kind of. For any prime m, there are only two solutions of the x^2=1 (mod m), which are 1 and -1, regardless of the fact that m is mersenne or not. If m is not prime, there are more solutions, and the determinant does not exist. If you make m=2^p-1 for some prime p, yeah, the determinant still exists only when m is prime.

For example for p=11, you have four solutions, +/-1 and +/-622, when you square them you get 1 (mod 2047). It is all about the roots of 1.
LaurV is offline   Reply With Quote
Old 2021-04-18, 06:29   #7
axn
 
axn's Avatar
 
Jun 2003

2×3×827 Posts
Default

Your check is 9^((Mp-1)/2) == 1 (mod Mp) or alternately, 9^((Mp+1)/2)==9 (mod Mp).

This is nothing but a Euler pseudoprimality test

Since 9 is a perfect square, it is a quadratic residue to every number.
axn is offline   Reply With Quote
Old 2021-04-18, 06:41   #8
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

201810 Posts
Default

Quote:
Originally Posted by axn View Post

Since 9 is a perfect square, it is a quadratic residue to every number.
Do you mean every Prime-Number?
Code:
qfbprimeform(9, 19)
%3 = Qfb(19, 3, 0, 0.E-38)
(02:38) gp >
(02:38) gp >
(02:38) gp > qfbprimeform(9, 15)
  ***   at top-level: qfbprimeform(9,15)
  ***                 ^------------------
  *** qfbprimeform: not an n-th power residue in primeform: Mod(9, 15).
Quote:
Returns an error if x is not a quadratic residue mod p
https://pari.math.u-bordeaux.fr/dochtml/html-stable/

ETA: 121 is a perfect square and is a quadratic-residue for M11, while 9 is not.

ETA II: 9 as quadratic-residue-test passes all the Mersenne-primes from M2 to M23209 and none of the Mersenne-composites (not a single "pseudoprime").

ETA III As LarsNet has pointed out, the test is valid only for Mersenne-Numbers:

Code:
qfbprimeform(9, 91)
%7 = Qfb(91, 81, 18, 0.E-38)

Last fiddled with by a1call on 2021-04-18 at 07:05
a1call is offline   Reply With Quote
Old 2021-04-18, 07:14   #9
axn
 
axn's Avatar
 
Jun 2003

115428 Posts
Default

Quote:
Originally Posted by a1call View Post
Do you mean every Prime-Number?
No. Composite numbers as well. However, it must be relatively prime.

Code:
? kronecker(9,14)
%1 = 1
? kronecker(9,15)
%2 = 0
? kronecker(9,16)
%3 = 1
? kronecker(9,17)
%4 = 1
? kronecker(9,18)
%5 = 0

Quote:
Originally Posted by a1call View Post
ETA III As LarsNet has pointed out, the test is valid only for Mersenne-Numbers:
Test is valid for all numbers relatively prime to 9. It is merely a base-9 Euler pseudoprimality test. He stumbled upon it while checking out QR; but that's what it is.

Last fiddled with by axn on 2021-04-18 at 07:15
axn is offline   Reply With Quote
Old 2021-04-18, 07:21   #10
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,009 Posts
Default

Quote:
Originally Posted by axn View Post
No. Composite numbers as well. However, it must be relatively prime.
25 is coprime to 9 but it does not pass the test:

Code:
qfbprimeform(9, 25)
  ***   at top-level: qfbprimeform(9,25)
  ***                 ^------------------
  *** qfbprimeform: not a prime number in Fl_sqrt [modulus]: 25.

ETA: 35 is coprime to 9 but it does not pass the test:
Code:
qfbprimeform(9, 35)
  ***   at top-level: qfbprimeform(9,35)
  ***                 ^------------------
  *** qfbprimeform: not an n-th power residue in primeform: Mod(9, 35).

Last fiddled with by a1call on 2021-04-18 at 07:24
a1call is offline   Reply With Quote
Old 2021-04-18, 07:39   #11
axn
 
axn's Avatar
 
Jun 2003

2×3×827 Posts
Default

Quote:
Originally Posted by a1call View Post
25 is coprime to 9 but it does not pass the test:
I don't know what "the test" is but:
Code:
? kronecker(9, 25)
%1 = 1
Do you even know what qfbprimeform is supposed to do?
Code:
? ?qfbprimeform 
qfbprimeform(x,p): returns the prime form of discriminant x, whose first coefficient is p.
OP's algorithm has nothing to do with qfbprimeform, so stop bringing it up.

Last fiddled with by axn on 2021-04-18 at 07:40
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Possible obfuscation for Mersennes paulunderwood Miscellaneous Math 3 2019-01-24 03:14
Composite integers n satisfying prime exponents of Mersennes carpetpool carpetpool 7 2017-01-05 04:36
DC completion not noticed Mini-Geek GPU to 72 3 2011-12-20 16:12
Looks like PrimeGrid's noticed us.... mdettweiler Conjectures 'R Us 7 2008-03-06 17:33
Noticed something on wiki moo Hardware 4 2006-04-14 03:36

All times are UTC. The time now is 01:43.

Wed May 12 01:43:04 UTC 2021 up 33 days, 20:23, 0 users, load averages: 2.17, 2.38, 2.58

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.