mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-04-11, 03:14   #1
Lan
 
Apr 2019

17 Posts
Default Reserve The Formula

Hi...
I am a programmer
I use a lot base 2 (binary) in my programs
I want to know...

why can't we reverse Lucas-lehmer's formula.
like if x=(2^p)-1 as divisor,
we write LL/x for p-2 times
why not p as divisor for less ((2^p)-1)/4 times
you see for (2^82589933)-1, if the divisor is p=82589933
p <<< LL divisor... and it is less than quarter times of (2^82589933)-1 to finish
small divisor=less time rite?
I know how LL work because i am a programmer
Lan is offline   Reply With Quote
Old 2019-04-11, 03:55   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

3·19·89 Posts
Default

Can you give an example on a smaller number, say 2^31 - 1, showing more work (like specific iterations)? I'm struggling to follow what you are trying to do.
VBCurtis is offline   Reply With Quote
Old 2019-04-11, 05:06   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×23×137 Posts
Default

Quote:
Originally Posted by Lan View Post
Hi...
I am a programmer
I use a lot base 2 (binary) in my programs
I want to know...

why can't we reverse Lucas-lehmer's formula.
like if x=(2^p)-1 as divisor,
we write LL/x for p-2 times
why not p as divisor for less ((2^p)-1)/4 times
you see for (2^82589933)-1, if the divisor is p=82589933
p <<< LL divisor... and it is less than quarter times of (2^82589933)-1 to finish
small divisor=less time rite?
I know how LL work because i am a programmer
To reverse LL you need to do a square root. And also to add to the difficulty, you need to do that square root as a modulus of the number. And you would get two possible answers with no way to know which is the correct one to choose for the next iteration. And not only that, doing correct modulus square roots would require factoring the number first.
retina is online now   Reply With Quote
Old 2019-04-11, 16:23   #4
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×5×593 Posts
Default

Quote:
Originally Posted by Lan View Post
Hi...
I am a programmer
I use a lot base 2 (binary) in my programs
I want to know...

why can't we reverse Lucas-lehmer's formula.
like if x=(2^p)-1 as divisor,
we write LL/x for p-2 times
why not p as divisor for less ((2^p)-1)/4 times
you see for (2^82589933)-1, if the divisor is p=82589933
p <<< LL divisor... and it is less than quarter times of (2^82589933)-1 to finish
small divisor=less time rite?
I know how LL work because i am a programmer
I'm skeptical about "I know how LL work". For starters, possible factors of 2p-1 with p a prime are of form 2kp+1 where k is a positive integer, so p itself is excluded as a factor. If p is composite, so is 2p-1, with some very easily found factors, so in that case there is no need of an LL test. Then there are the points retina has already raised, including that the inverse operation of LL's squaring is not division, it is square root. Square root is a harder function to compute than square. In the forward direction, square is single-valued; so is modulo. In the reverse direction, they are multivalued. (Simple examples sqrt(25)= +5 or -5; 49 mod 12 = 37 mod 12 = 25 mod 12 = 13 mod 12 = 1 mod 12 =1; what's the inverse-mod of 1,12? The infinite set 1, 13, 25, 37, 49, .... and the same issue occurs with prime p values instead of 12)
The initial post seems to me incoherent, which sometimes indicates lack of understanding, or unclear thinking.
kriesel is online now   Reply With Quote
Old 2019-04-11, 17:25   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

11×17×59 Posts
Default

Quote:
Originally Posted by kriesel View Post
I(Simple examples sqrt(25)= +5 or -5; 49 mod 12 = 37 mod 12 = 25 mod 12 = 13 mod 12 = 1 mod 12 =1; what's the inverse-mod of 1,12? The infinite set 1, 13, 25, 37, 49, .... and the same issue occurs with prime p values instead of 12)
The initial post seems to me incoherent, which sometimes indicates lack of understanding, or unclear thinking.
Oh, the irony is just too much. It is quite clear to almost all concerned that only the values between 0 and p-1 inclusive need be considered.

The quoted post seems to me incoherent, which sometimes indicates lack of understanding, or unclear thinking.

Nonetheless, the reverse algorithm, though possible, is too demanding of storage space. I once accused RDS of being an engineer rather than a mathematician with respect to this algorithm. He, of course, viewed the accusation with the humour which I'd intended.
xilman is offline   Reply With Quote
Old 2019-04-11, 17:46   #6
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

3·1,663 Posts
Default

Here’s the answer to “Reverse The Formula”: alumroF ehT”
pinhodecarlos is offline   Reply With Quote
Old 2019-04-11, 17:56   #7
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×23×137 Posts
Default

Just for fun let's reverse M5 (25-1 = 31)

Start with the assumption that it is prime, so the LL final step produces s=0

3) s=0
2) s=sqrt(0+2 mod 31) ==> s=8, or s=23, which do we choose? let's go with 8
1) s=sqrt(8+2 mod 31) ==> s=14, or s=17, which do we choose? let's go with 14
0) s=sqrt(14+2 mod 31) ==> s=4, or s=27, which do we choose? let's go with 4
so the final result is 4 success, it is prime. Yay

But what happens if we choose the other square root?

3) s=0
2) s=sqrt(0+2 mod 31) ==> s=8, or s=23, which do we choose? let's go with 23
1) s=sqrt(23+2 mod 31) ==> s=5, or s=26,(which do we choose? let's go with 5
0) s=sqrt(5+2 mod 31) ==> s=10, or s=21, which do we choose? let's go with 10
so the final result is 10 success, it is prime. Yay

Let's try another reverse path

3) s=0
2) s=sqrt(0+2 mod 31) ==> s=8, or s=23, which do we choose?)let's go with 23
1) s=sqrt(23+2 mod 31) ==> s=5, or s=26, which do we choose? let's go with 26
0) s=sqrt(26+2 mod 31) ==> s=11, or s=20, which do we choose? let's go with 11
so the final result is 11 (the same as 2/3) success, it is prime. Yay

So it does work, and we can end up with any of the possible start values 4, 10, 2/3 etc.

Let's try with a non-prime M11 (2047)

9) s=0 (assume it is prime)
8) s=sqrt(0+2 mod 2047) ==> s=64, or s=1983, which do we choose? let's go with 64
7) s=sqrt(64+2 mod 2047) ==> s=?? there is no result here, let's try the other side
7) s=sqrt(1983+2 mod 2047) ==> s=?? there is no result here either

So this number isn't prime, there are no paths that lead to a valid start value. And it only took two steps. So this is better than the LL test right? Fewer steps. But the details matter. How do we take fast square roots modulo a number? That is an exercise left for the reader.

Last fiddled with by retina on 2019-04-11 at 18:09
retina is online now   Reply With Quote
Old 2019-04-11, 18:06   #8
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×5×593 Posts
Default

Quote:
Originally Posted by xilman View Post
Oh, the irony is just too much. It is quite clear to almost all concerned that only the values between 0 and p-1 inclusive need be considered.

The quoted post seems to me incoherent, which sometimes indicates lack of understanding, or unclear thinking.

Nonetheless, the reverse algorithm, though possible, is too demanding of storage space. I once accused RDS of being an engineer rather than a mathematician with respect to this algorithm. He, of course, viewed the accusation with the humour which I'd intended.
Sorry, did not mean to imply that mod p was an acceptable substitute for mod Mp. (If it was, the speedup would be a lot more than a factor of 4.)

Or that the original poster was the only one capable of error or lack of clarity.

Another possibility is English is not Lan's native language. Lan's identity seems well concealed, so no clues available regarding that, other than the text in post 1 here.

Ok, LL iteration numbers 1 to p-2 get computed in the normal course, from a seed value corresponding to iteration number zero.
LL iteration values (residues) ranging 0 to Mp-1 are the normal result.
Negative iteration values (such as those computed in error, such as by a memory copy failure, giving zero for the square output, then the decrement by two occurring) get represented by underflow, as in the -2 case, as falling in the 0 to Mp-1 range (res64 fffffffffffffffd). Yet long-time posters in this forum write of them as value -2 on occasion.

Are you saying Lan's post initiating this thread was intended as a joke? I suggest a thread in https://www.mersenneforum.org/forumdisplay.php?f=7 called math humor, for any such posts.
kriesel is online now   Reply With Quote
Old 2019-04-11, 18:36   #9
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

134528 Posts
Default

Quote:
Originally Posted by retina View Post
...
Let's try with a non-prime M11 (2047)

9) s=0 (assume it is prime)
8) s=sqrt(0+2 mod 2047) ==> s=64, or s=1983, which do we choose? let's go with 64
7) s=sqrt(64+2 mod 2047) ==> s=?? there is no result here, let's try the other side
7) s=sqrt(1983+2 mod 2047) ==> s=?? there is no result here either

So this number isn't prime, there are no paths that lead to a valid start value. And it only took two steps. So this is better than the LL test right? Fewer steps. But the details matter. How do we take fast square roots modulo a number? That is an exercise left for the reader.
Great post, thanks.
I found these interesting:
https://math.stackexchange.com/quest...re-root#633174
http://www.ptrow.com/perl/calculator_bigint.pl
https://en.wikipedia.org/wiki/Tonell...anks_algorithm

Last fiddled with by kriesel on 2019-04-11 at 18:41
kriesel is online now   Reply With Quote
Old 2019-04-11, 19:54   #10
Lan
 
Apr 2019

1116 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Can you give an example on a smaller number, say 2^31 - 1, showing more work (like specific iterations)? I'm struggling to follow what you are trying to do.
for 2^31-1 is written like this:

((2^31-1-A))mod(2A*31+1) while A is its times for example if A is 2 means 2nd time.
3 means 3rd time.

lets use much smaller number say 2^13-1 which is prime. reverse it u will get 315
from 8191, repeat (315-A)mod(2A*13+1) until (2A*13+1) >= (315-A) u will get =/=0 then is prime.

lets try composite number say 2^11-1. reverse it u will get 93
from 2047, repeat (93-A)mod(2A*11+1) u will get ==0 at 1st time then is composite.
Lan is offline   Reply With Quote
Old 2019-04-11, 19:59   #11
Lan
 
Apr 2019

1116 Posts
Default

Quote:
Originally Posted by retina View Post
To reverse LL you need to do a square root. And also to add to the difficulty, you need to do that square root as a modulus of the number. And you would get two possible answers with no way to know which is the correct one to choose for the next iteration. And not only that, doing correct modulus square roots would require factoring the number first.
No... you dont need to do a square root.

Last fiddled with by Lan on 2019-04-11 at 20:46
Lan is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to reserve very low TF work snme2pm1 Information & Answers 17 2015-02-23 10:47
How to reserve an exponent? TheMawn Lone Mersenne Hunters 8 2013-05-26 14:50
How much to reserve for maual LLR? Ungelovende Prime Sierpinski Project 2 2008-09-13 22:53
Is it possible to reserve a specific n-value for 2^n-1? jasong PrimeNet 1 2006-09-21 00:10
Reserve 15K = 869688015 amphoria 15k Search 0 2005-09-18 19:56

All times are UTC. The time now is 12:48.


Tue Dec 7 12:48:40 UTC 2021 up 137 days, 7:17, 0 users, load averages: 1.97, 1.99, 1.80

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.