mersenneforum.org Reserve The Formula
 Register FAQ Search Today's Posts Mark Forums Read

 2019-04-11, 03:14 #1 Lan   Apr 2019 23 Posts 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
 2019-04-11, 03:55 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 4,789 Posts 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.
2019-04-11, 05:06   #3
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

10111111111112 Posts

Quote:
 Originally Posted by Lan 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.

2019-04-11, 16:23   #4
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

24×3×107 Posts

Quote:
 Originally Posted by Lan 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.

2019-04-11, 17:25   #5
xilman
Bamboozled!

"đ’‰şđ’ŚŚđ’‡·đ’†·đ’€­"
May 2003
Down not across

29BE16 Posts

Quote:
 Originally Posted by kriesel 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.

 2019-04-11, 17:46 #6 pinhodecarlos     "Carlos Pinho" Oct 2011 Milton Keynes, UK 22·5·13·19 Posts Hereâ€™s the answer to â€śReverse The Formulaâ€ť: alumroF ehTâ€ť
 2019-04-11, 17:56 #7 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 6,143 Posts 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
2019-04-11, 18:06   #8
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

24·3·107 Posts

Quote:
 Originally Posted by xilman 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.

2019-04-11, 18:36   #9
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

24×3×107 Posts

Quote:
 Originally Posted by retina ... 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

2019-04-11, 19:54   #10
Lan

Apr 2019

23 Posts

Quote:
 Originally Posted by VBCurtis 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.

2019-04-11, 19:59   #11
Lan

Apr 2019

23 Posts

Quote:
 Originally Posted by retina 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

 Similar Threads Thread Thread Starter Forum Replies Last Post snme2pm1 Information & Answers 17 2015-02-23 10:47 TheMawn Lone Mersenne Hunters 8 2013-05-26 14:50 Ungelovende Prime Sierpinski Project 2 2008-09-13 22:53 jasong PrimeNet 1 2006-09-21 00:10 amphoria 15k Search 0 2005-09-18 19:56

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

Tue May 18 01:45:46 UTC 2021 up 39 days, 20:26, 0 users, load averages: 1.53, 2.00, 2.12