

Thread Tools 
20210418, 11:43  #12 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×1,009 Posts 
You will get the same results from Wolfram Alpha:
https://www.wolframalpha.com/input/?...2+%3D+19+mod+9 https://www.wolframalpha.com/input/?...2+%3D+35+mod+9 
20210418, 13:14  #13  
Apr 2020
263_{10} Posts 
Quote:
The discussion in this thread is about when 9 is a quadratic residue mod n, not when n is a quadratic residue mod 9. OP, you seem to have assumed we can use Euler's criterion to check whether a is a quadratic residue mod n, even when n is composite. This isn't the case: if n is composite then a^((n1)/2) will usually not be equal to 1 or 1 mod n. Furthermore, even if Euler's criterion did hold, that wouldn't be enough: the Jacobi symbol can be 1 even for a quadratic nonresidue. 

20210418, 13:31  #14  
Feb 2017
Nowhere
3×17×89 Posts 
Quote:
The usage of "quadratic residue" in the thread title is completely wrong. The residue a (mod n) is a quadratic residue if x^2 == a (mod n) has a solution; it is usually assumed that gcd(a,n) = 1. The quadratic residues (mod 9) are 1,4, and 7 (mod 9). Since every number 2^n  1 for odd n is congruent to 1 (mod 3), it is trivially a quadratic residue (mod 9) as per the thread title. Quote:
A wellknown Euler pseudoprime test for Mp for p > 2, disussed in a number of threads in years gone by, is 3^((Mp  1)/2) == 1 (mod Mp) which is true if Mp is prime. Multiplying through by 3, becomes (*) 3^((Mp +1)/2) == 3 (mod Mp) which is "nicer" in the sense that the exponent is a power of two. This congruence states not only that 3 is a quadratic residue (mod Mp), but also that the specific residue 3^((Mp +1)/4) (mod Mp) is a square root of 3 (mod Mp). This is significant, because there are composite Mp which have 3 as a quadratic residue (e.g. p = 37), but for which the above congruence does not hold. Squaring both sides of (*) gives (**) 3^(Mp + 1) or 9^(Mp + 1)/2 == 9 (mod Mp) which is, if my understanding is correct, actually used as a PRP test in the existing software, along with a feature that allows the result to be checked with small fraction of the effort required to run the test. 

20210419, 03:10  #15  
"Rashid Naimi"
Oct 2015
Remote to Here/There
3742_{8} Posts 
Here is an update to the output in Post number 4:
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 M44497 The code has not passed a single pseudoprime so far. https://www.mersenne.org/primes/ I did point this out before but it seems that a refresher is in order. The reason qfbprimeform() works here is because of he following quote from the PariGP manpages: Quote:
https://pari.math.ubordeaux.fr/dochtml/htmlstable/ Clicking on Q in the lower left And then clicking on qfbprimeform on top. FWIW, here is a computation time comparison between qfbprimeform and ispseudoprime for M44497 with 13,395 dd. Code:
qfbprimeform(9, 2^444971); (23:07) gp > ## *** last result computed in 16,423 ms. (23:07) gp > ispseudoprime(2^444971) %4 = 1 (23:07) gp > ## *** last result computed in 30,640 ms. 

20210419, 05:58  #16 
Jun 2003
2·3·827 Posts 
If you don't make ispseudoprime do a BPSW test, the timings are comparable.
Code:
? # timer = 1 (on) ? qfbprimeform(9, 2^444971); time = 8,043 ms. ? ispseudoprime(2^444971, 1); time = 8,645 ms. ? ispseudoprime(2^444971); time = 14,827 ms. 
20210419, 12:23  #17  
Apr 2020
263 Posts 
Quote:
Quote:
...or at least that's how the function is supposed to work. Quote:
Code:
gp > qfbprimeform(121,2047) %1 = Qfb(2047, 11, 0, 0.E38) Code:
gp > qfbprimeform(1,15) %25 = Qfb(15, 1, 0, 0.E38) gp > qfbprimeform(1,33) *** at toplevel: qfbprimeform(1,33) *** ^ *** qfbprimeform: not a prime number in Fl_sqrt [modulus]: 33. 

20210419, 20:11  #18 
Mar 2021
11000_{2} Posts 
makersmark at its core is just a modified lucas lehmer test ( and just as fast), instead of starting with 4, it uses 9, and it doesn't subtract 2 at each iteration. The mer_rem (which i got from stackoverflow) greatly speeds the increase of modding with a mersenne.
psuedocode: Code:
m=2**444971 n=gmpy2.bit_length(m) s=9 for x in range(n1): s = (s*s) % m print (s == 9) Code:
z=44497 start = time.time() xx=makersmark(z) end = time.time() print(xx == True) True print(endstart) 1.6440508365631104 For those interested i found another way to get to an answer for mersenne primes, it is simply m=2**444971 answer = powmod(3, m//gmpy2.bit_length(m), m) checkforpowersof2number(answer) and the answer for mersenne primes is always a powers of 2 number, and not a powers of 2 number for non mersenne primes. the functions can be greatly speeded up using mer_rem and and lr_k_ary pow methods. I haven't' tried PARI yet, but i will soon. Last fiddled with by LarsNet on 20210419 at 20:25 
20210419, 20:25  #19  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·3·1,571 Posts 
Quote:
It is the Fermat PRP test! It is the screwdriver. Not a modified hammer. 

20210419, 20:26  #20  
Sep 2002
Database er0rr
3673_{10} Posts 
Quote:
There are many tricks to speed up computation for Mersenne numbers. 

20210419, 20:32  #21 
Mar 2021
2^{3}·3 Posts 
Im glad they've already been found, i really did come across them by myself, and was pretty excited about it, and i think it's cool they've already been found. It's exciting when you study primes on your own and find something others have come across. I really find prime study amazingly fun, and will read this board and learn as much as i can about what tests have already been found, i'm constantly looking for a faster method than what's out there :)
Last fiddled with by LarsNet on 20210419 at 20:38 
20210419, 20:43  #22  
Apr 2020
263_{10} Posts 
Quote:
But this is a pth root of \(3^{2^p2} \pmod {2^p1}\). If 2^p1 is prime then this is 1 by Fermat's little theorem, and furthermore 1 has exactly p pth roots mod 2^p1, namely the powers of 2. So this is just another Fermattype pseudoprimality test. I think it's slightly stronger than a simple Fermat test because of the division by p, analogous to division by powers of 2 in MillerRabin, but there's no practical advantage to this because it's overwhelmingly likely that every 2^p1 that passes the Fermat test is in fact prime. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Possible obfuscation for Mersennes  paulunderwood  Miscellaneous Math  3  20190124 03:14 
Composite integers n satisfying prime exponents of Mersennes  carpetpool  carpetpool  7  20170105 04:36 
DC completion not noticed  MiniGeek  GPU to 72  3  20111220 16:12 
Looks like PrimeGrid's noticed us....  mdettweiler  Conjectures 'R Us  7  20080306 17:33 
Noticed something on wiki  moo  Hardware  4  20060414 03:36 