mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-04-18, 11:43   #12
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,009 Posts
Default

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
a1call is offline   Reply With Quote
Old 2021-04-18, 13:14   #13
charybdis
 
charybdis's Avatar
 
Apr 2020

26310 Posts
Default



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.
charybdis is offline   Reply With Quote
Old 2021-04-18, 13:31   #14
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×17×89 Posts
Default

Quote:
Originally Posted by axn View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-04-19, 03:10   #15
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

37428 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2021-04-19, 05:58   #16
axn
 
axn's Avatar
 
Jun 2003

2·3·827 Posts
Default

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.
axn is offline   Reply With Quote
Old 2021-04-19, 12:23   #17
charybdis
 
charybdis's Avatar
 
Apr 2020

263 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
charybdis is offline   Reply With Quote
Old 2021-04-19, 20:11   #18
LarsNet
 
Mar 2021

110002 Posts
Default

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
LarsNet is offline   Reply With Quote
Old 2021-04-19, 20:25   #19
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·1,571 Posts
Talking

Quote:
Originally Posted by LarsNet View Post
... 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.
Batalov is offline   Reply With Quote
Old 2021-04-19, 20:26   #20
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

367310 Posts
Default

Quote:
Originally Posted by LarsNet View Post
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.
paulunderwood is offline   Reply With Quote
Old 2021-04-19, 20:32   #21
LarsNet
 
Mar 2021

23·3 Posts
Default

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
LarsNet is offline   Reply With Quote
Old 2021-04-19, 20:43   #22
charybdis
 
charybdis's Avatar
 
Apr 2020

26310 Posts
Default

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

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

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.