mersenneforum.org I noticed that only prime mersennes are quad_residue's of 9, has this been noticed before?
 Register FAQ Search Today's Posts Mark Forums Read

 2021-04-18, 11:43 #12 a1call     "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
2021-04-18, 13:14   #13
charybdis

Apr 2020

26310 Posts

Quote:
 Originally Posted by a1call

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^((n-1)/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 non-residue.

2021-04-18, 13:31   #14
Dr Sardonicus

Feb 2017
Nowhere

3×17×89 Posts

Quote:
 Originally Posted by axn Your check is 9^((Mp-1)/2) == 1 (mod Mp) or alternately, 9^((Mp+1)/2)==9 (mod Mp).
Thank you for explaining what the program actually does.

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:
 Since 9 is a perfect square, it is a quadratic residue to every number.
Yes. The usage got turned around to "9 is a quadratic residue" which is not what the thread title says.

A well-known 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.

2021-04-19, 03:10   #15
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

37428 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
It includes 100% of the Mersenne-Primes between M2 and 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 Pari-GP manpages:

Quote:
 Returns an error if x is not a quadratic residue mod p
You can verify this by going to the link below:

https://pari.math.u-bordeaux.fr/dochtml/html-stable/

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^44497-1);
(23:07) gp > ##
***   last result computed in 16,423 ms.
(23:07) gp > ispseudoprime(2^44497-1)
%4 = 1
(23:07) gp > ##
***   last result computed in 30,640 ms.

 2021-04-19, 05:58 #16 axn     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^44497-1); time = 8,043 ms. ? ispseudoprime(2^44497-1, 1); time = 8,645 ms. ? ispseudoprime(2^44497-1); time = 14,827 ms.
2021-04-19, 12:23   #17
charybdis

Apr 2020

263 Posts

Quote:
Originally Posted by a1call
The reason qfbprimeform() works here is because of he following quote from the Pari-GP manpages:

Quote:
 Returns an error if x is not a quadratic residue mod p
You can verify this by going to the link below:

https://pari.math.u-bordeaux.fr/dochtml/html-stable/

Clicking on Q in the lower left
And then clicking on qfbprimeform on top.
If you tried reading the full description for qfbprimeform, you would see this:
Quote:
 qfbprimeform(x, p) Prime binary quadratic form of discriminant x whose first coefficient is p, where |p| is a prime number.
So if your input has a composite value of p, you should expect an error, whether x is a quadratic residue mod p or not. This is why your script only outputs Mersenne primes. It has nothing to do with whether 9 is a quadratic residue mod Mp - qfbprimeform gives an error when Mp is composite.

...or at least that's how the function is supposed to work.
Quote:
 ETA IV, Please ignore ETA III, M11 passes with 121, but not with 9.
Indeed:
Code:
gp > qfbprimeform(121,2047)
%1 = Qfb(2047, 11, 0, 0.E-38)
This ought to give an error, because 2047 is composite. I notice that 2047 is an Euler pseudoprime to base 121, since 121^1023 = 1 mod 2047; perhaps instead of separately testing p for primality and checking whether x is a quadratic residue, qfbprimeform does an Euler pseudoprimality test by calculating x^((p-1)/2) mod p, which if p is prime will give the Legendre symbol of x mod p. This would trick qfbprimeform into thinking 2047 is prime. But this can't be the whole story, because
Code:
gp > qfbprimeform(1,15)
%25 = Qfb(15, 1, 0, 0.E-38)
gp > qfbprimeform(1,33)
***   at top-level: qfbprimeform(1,33)
***                 ^------------------
*** qfbprimeform: not a prime number in Fl_sqrt [modulus]: 33.
In short: qfbprimeform was intended only to be used for prime p, and it does not behave reliably if p is not prime.

 2021-04-19, 20:11 #18 LarsNet   Mar 2021 110002 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**44497-1 n=gmpy2.bit_length(m) s=9 for x in range(n-1): s = (s*s) % m print (s == 9) Here is a speed example from an i7 core processor: Code: z=44497 start = time.time() xx=makersmark(z) end = time.time() print(xx == True) True print(end-start) 1.6440508365631104 I posted this because i thought it was interesting and was looking at quadratic residue and other methods to see if there was a faster way to get to the result. For those interested i found another way to get to an answer for mersenne primes, it is simply m=2**44497-1 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 2021-04-19 at 20:25
2021-04-19, 20:25   #19
Batalov

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

2·3·1,571 Posts

Quote:
 Originally Posted by LarsNet ... 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.
That's just like saying that a screwdriver is "just like a hammer", - "only instead of" hammerhead it has a screwdriver bit added.

It is the Fermat PRP test! It is the screwdriver. Not a modified hammer.

2021-04-19, 20:26   #20
paulunderwood

Sep 2002
Database er0rr

367310 Posts

Quote:
 Originally Posted by LarsNet 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.
You have described the LL test and a Fermat base 3 PRP test.

There are many tricks to speed up computation for Mersenne numbers.

 2021-04-19, 20:32 #21 LarsNet   Mar 2021 23·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 2021-04-19 at 20:38
2021-04-19, 20:43   #22
charybdis

Apr 2020

26310 Posts

Quote:
 Originally Posted by LarsNet For those interested i found another way to get to an answer for mersenne primes, it is simply m=2**44497-1 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.
This test calculates $$3^{\left\lfloor \frac{2^p-1}{p}\right\rfloor} \pmod {2^p-1}$$. Fermat's little theorem tells us that p divides 2^p-2, so we are in fact calculating $$3^{\frac{2^p-2}{p}} \pmod {2^p-1}$$.
But this is a p-th root of $$3^{2^p-2} \pmod {2^p-1}$$. If 2^p-1 is prime then this is 1 by Fermat's little theorem, and furthermore 1 has exactly p p-th roots mod 2^p-1, namely the powers of 2.

So this is just another Fermat-type 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 Miller-Rabin, but there's no practical advantage to this because it's overwhelmingly likely that every 2^p-1 that passes the Fermat test is in fact prime.

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 3 2019-01-24 03:14 carpetpool carpetpool 7 2017-01-05 04:36 Mini-Geek GPU to 72 3 2011-12-20 16:12 mdettweiler Conjectures 'R Us 7 2008-03-06 17:33 moo Hardware 4 2006-04-14 03:36

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

Wed May 12 01:26:47 UTC 2021 up 33 days, 20:07, 0 users, load averages: 2.40, 2.99, 3.09