mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2014-11-05, 00:29   #12
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

593310 Posts
Default

Quote:
Originally Posted by ewmayer View Post
Anyone who's ever implemented the IBDWT knows it's not trivial, and to do it efficiently even less so. But yes, once you've got an efficient implementation the implicit-mod is nearly free (say < 10% of runtime, and costing O(n) vs the FFT's O(n lg n)).
It wouldn't surprise me if (with a horrendous amount of effort) one could code a LL-like test which worked mod M_p + 1 instead of M_p and ran, say, 5% faster by cutting out the rest of the reduction cost. There's just the little issue by which the result would tell you nothing about the primality of the number...!
CRGreathouse is offline   Reply With Quote
Old 2014-11-06, 00:17   #13
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

5×19 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
It wouldn't surprise me if (with a horrendous amount of effort) one could code a LL-like test which worked mod M_p + 1 instead of M_p and ran, say, 5% faster by cutting out the rest of the reduction cost. There's just the little issue by which the result would tell you nothing about the primality of the number...!
Diving a little more into my question I have noticed a pattern between n mod Mn and n mod Mn+1

Consider the moduli and divisions (with decimal truncated) after each iteration of the Lucas-Lehmer test of 210-1, where x is the x-th iteration through the test:


Sx (mod Mn)------Mn/Sx
---------------------------------------
  1. 14------------0
  2. 194----------0
  3. 806----------36
  4. 29------------635
  5. 839----------0
  6. 95------------688
  7. 839----------8
  8. 95------------688

Now consider Sx (mod Mn+1). Note that the x-th iteration was performed using x-1 iterations of the Lucas Lehmer test and the final iteration was performed with a Sx (mod Mn+ 1) rather than Sx (mod Mn).


Sx (mod Mn+1)---(Mn+1)/Sx
------------------------------------------
  1. 14------------0
  2. 194----------0
  3. 770----------36
  4. 418----------634
  5. 839----------0
  6. 431----------687
  7. 831----------8
  8. 431----------687

Looking at this raw data, one can make a few observations. lets define

d0 = Mn/Sx,
d1 = (Mn+1)/Sx
m0 = Sx (mod Mn)
m1= Sx (mod Mn+1)

One may notice that when d0=d1= 0, m0= m1. This is obvious. Additionally, notice that either d0= d1 or d0= d1+1. Upon further inspection, one finds

d0= d1 + 1 if m0 - d0 < 0 and
d0= d1 if m0 - d0 >= 0

one may also notice

m1= m0+ d0 if d0= d1 and
m1= (m0+ d0 - 1) - Mn if d0= d1 + 1

From the previous observation, one may substitute the if conditions to obtain

m1= m0+ d0 if m0 - d0 >= 0 and
m1= (m0+ d0 - 1) - Mn if m0 - d0 < 0

Like mentioned in a previous post, calculating moduli and division by powers of 2 is extremely trivial to do on a computer (along with addition and subtraction), so this is a very simple way of calculating n (mod) Mn. The question now is will this be a faster implementation of modulus than the previous algorithm, and can my observations be proven? I may prove them later; I suspect most of the observations can be proven by induction, so it should be a fairly trivial proof.

Apologies if I got any of the math formatting wrong, I am in high school, and I still have a lot of practicing to do to get good at writing my observations in mathematical terms! If my hypothesis is wrong, I suspect the issue may lie in writing it mathematically rather than an issue with the hypothesis itself. I also tested this out on many more (and larger) Lucas Lehmer tests than just 210-1 but I posted this small one as an example so you could follow my hypothesis with me. Just 8 iterations is not enough data to draw any conclusions upon indeed.
Trilo is offline   Reply With Quote
Old 2014-11-06, 00:35   #14
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

26·7·13 Posts
Default

Quote:
Originally Posted by Trilo View Post
Like mentioned in a previous post, calculating moduli and division by powers of 2 is extremely trivial to do on a computer ...
Yup, it is. And like you have already been told by LaurV, doing mod Mn is also trivial so you are not gaining anything here.
retina is offline   Reply With Quote
Old 2014-11-06, 00:38   #15
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

5·19 Posts
Default

Quote:
Originally Posted by retina View Post
Yup, it is. And like you have already been told by LaurV, doing mod Mn is also trivial so you are not gaining anything here.
Quote:
Originally Posted by ewmayer View Post
Anyone who's ever implemented the IBDWT knows it's not trivial, and to do it efficiently even less so. But yes, once you've got an efficient implementation the implicit-mod is nearly free (say < 10% of runtime, and costing O(n) vs the FFT's O(n lg n)).
.

Last fiddled with by Trilo on 2014-11-06 at 00:39
Trilo is offline   Reply With Quote
Old 2014-11-06, 00:48   #16
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by Trilo View Post

Looking at this raw data, one can make a few observations. lets define

d0 = Mn/Sx,
d1 = (Mn+1)/Sx
m0 = Sx (mod Mn)
m1= Sx (mod Mn+1)

One may notice that when d0=d1= 0, m0= m1. This is obvious. Additionally, notice that either d0= d1 or d0= d1+1. Upon further inspection, one finds

d0= d1 + 1 if m0 - d0 < 0 and
d0= d1 if m0 - d0 >= 0

one may also notice

m1= m0+ d0 if d0= d1 and
m1= (m0+ d0 - 1) - Mn if d0= d1 + 1

From the previous observation, one may substitute the if conditions to obtain

m1= m0+ d0 if m0 - d0 >= 0 and
m1= (m0+ d0 - 1) - Mn if m0 - d0 < 0

Like mentioned in a previous post, calculating moduli and division by powers of 2 is extremely trivial to do on a computer (along with addition and subtraction), so this is a very simple way of calculating n (mod) Mn. The question now is will this be a faster implementation of modulus than the previous algorithm, and can my observations be proven? I may prove them later; I suspect most of the observations can be proven by induction, so it should be a fairly trivial proof.

Apologies if I got any of the math formatting wrong, I am in high school, and I still have a lot of practicing to do to get good at writing my observations in mathematical terms! If my hypothesis is wrong, I suspect the issue may lie in writing it mathematically rather than an issue with the hypothesis itself. I also tested this out on many more (and larger) Lucas Lehmer tests than just 210-1 but I posted this small one as an example so you could follow my hypothesis with me. Just 8 iterations is not enough data to draw any conclusions upon indeed.
I like patterns but one thing I'd point out is that if d0 = d1+1 is true then the part using m0+d0-1 gets simplified to m0+d1 is there a reason I'm missing for not simplifying ? edit: realized I didn't use the full equation when I was talking about what I said.

Last fiddled with by science_man_88 on 2014-11-06 at 00:56
science_man_88 is offline   Reply With Quote
Old 2014-11-06, 01:06   #17
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

5×19 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I like patterns but one thing I'd point out is that if d0 = d1+1 is true then the part using m0+d0-1 gets simplified to m0+d1 is there a reason I'm missing for not simplifying ? edit: realized I didn't use the full equation when I was talking about what I said.
That and calculating m0 and d0 is trivial to do on a computer while d1 and m1 is not trivial to compute and it gets rid of the whole purpose of writing m1 in terms of m0 and d0.
Trilo is offline   Reply With Quote
Old 2014-11-06, 01:24   #18
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by Trilo View Post
That and calculating m0 and d0 is trivial to do on a computer while d1 and m1 is not trivial to compute and it gets rid of the whole purpose of writing m1 in terms of m0 and d0.
m1 is the last n bits and is the mod (Mn+1) you were talking of at last check ?
science_man_88 is offline   Reply With Quote
Old 2014-11-06, 04:02   #19
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·317 Posts
Default

Quote:
Apologies if I got any of the math formatting wrong, I am in high school, and I still have a lot of practicing to do to get good at writing my observations in mathematical terms!
Well, that explains it. You should say so from the start.
First thing, have a look to \TeX if you want to write math stuff in the future, hehe. Using lots of sub/sub/sup/sup does not look nice, and is "heavy" (not mentioning very difficult to write, but try a reply to your own post and see how it looks in quotes).

Quote:
Originally Posted by Trilo View Post
The question now is will this be a faster implementation of modulus than the previous algorithm, and can my observations be proven? I may prove them later; I suspect most of the observations can be proven by induction, so it should be a fairly trivial proof.
It will not be faster. And the proof is trivial. Assume that some number is equal to b (mod 2^n), this means the number is a*2^n+b, now add and substract a to it. You have a*2^n+a-a+b and by convenient pairing you have a*(2^n-1)+a+b, or say, your number is a+b (mod 2^n-1). That is what I said in the former post. You can do about the same for the +1 side. You didn't find anything beside a very trivial modular-math result, so simple it does not need any proof. Still ok, if you found that by yourself. That is approximately how I started too, years ago (and don't look to me, I am just a big mouth, but some big guns here also started like that, even if they don't want to recognize it anymore). The key is to work hard and learn new things...

Last fiddled with by LaurV on 2014-11-06 at 04:05
LaurV is offline   Reply With Quote
Old 2014-11-06, 06:20   #20
flagrantflowers
 
Apr 2014

27 Posts
Default

Quote:
Originally Posted by Trilo View Post
"Apologies if I got any of the math formatting wrong, I am in high school…
The fact that you acknowledge that your ideas may not be unique and may in fact be trivial is a big place to be in high school. I didn't have that and I don't think that most of the talented people here had that.

Keep on plugin' on…
flagrantflowers is offline   Reply With Quote
Old 2018-03-07, 02:22   #21
gophne
 
Feb 2017

3×5×11 Posts
Default Markers in Lucas-Lehmer?

The fact that the Lucas-Lehmer iteration works suggests to me that the distribution of mersenne prime numbers are "regular', dependant on the outcome of the LL iteration, but never-the-less "regular".

My question would be if anybody has ever looked or found any "marker/s" in the set of values generated by each mersenne prime iteration. Such things as say the term nearest to the "square root" position value of the set of iterations being of a certain relationship to the value of the successful value which would yield a return of "0", or any other relationship between the values comprising the set of iterations for a specific mersenne prime.

Any such marker could then either reduce the time needed to "prove" primality, or be an indicator whether it would be fruitful to continue with that iteration.
gophne is offline   Reply With Quote
Old 2018-03-07, 02:57   #22
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

22·31·79 Posts
Default

Quote:
Originally Posted by gophne View Post
The fact that the Lucas-Lehmer iteration works suggests to me that the distribution of mersenne prime numbers are "regular', dependant on the outcome of the LL iteration, but never-the-less "regular".
One could make the same claim with regard to, say, the base-2 Fermat compositeness test and the primes. Such tests 'work' because they rely in one manner or another on the existence of a primitive root of the mathematical group defined by multiplication modulo N, which means a root of the maximal possible order N−1. Such tests already short-cut the primitive-root checking as much as possible by proceeding (in effect) to computing an (N-1)th modular power via one-modmul-per-bit-of-N powering ladder; if you want to believe that this work estimate can be further improved on or that the fact that there exist fast methods of confirming existence of such a primitive root for various special classes of moduli equates to "theres a pattern to these primes" be my guest, but belief != proof (nor even plausibility).

One could just as well argue that "trial division up to sqrt(N) fails for N prime - thus there must a pattern!"

Last fiddled with by ewmayer on 2018-03-07 at 02:58
ewmayer is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucas-Lehmer test Mathsgirl Information & Answers 23 2014-12-10 16:25
proof the lucas lehmer test kurtulmehtap Math 13 2009-10-02 12:12
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas-Lehmer Test proof alpertron mersennewiki 16 2006-03-18 07:23
Lucas-Lehmer primality test CMOSMIKE Math 5 2002-09-06 18:46

All times are UTC. The time now is 20:52.

Sat Oct 31 20:52:28 UTC 2020 up 51 days, 18:03, 2 users, load averages: 1.68, 1.79, 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.