[QUOTE=kriesel;513427]I'm skeptical about "I know how LL work". For starters, possible factors of 2[SUP]p[/SUP]-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 2[SUP]p[/SUP]-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.[/QUOTE]

No need to do square root

[QUOTE=retina;513437]But the details matter. How do we take fast square roots modulo a number? That is an exercise left for the reader. :razz:[/QUOTE]
Exactly right. The details matter. The computational cost of one sqrtmod is approximately the same as the full LL. [SPOILER]That is actually why George is confident that no user will be able to fake a valid savefile that is ~10000 steps away from the finish. When George receives the penultimate savefile, he runs the last ~10000 squarings and if the result is 0, then this is (>>better than) the proverbial 'you can take it to the bank'.[/SPOILER]

[QUOTE=kriesel;513438]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 [URL]https://www.mersenneforum.org/forumdisplay.php?f=7[/URL] called math humor, for any such posts.[/QUOTE]

yup... english is not my native language. thank you for your concerning :smile::smile::smile:

[QUOTE=Lan;513448]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.[/QUOTE]
For p=13, what happens in the first iteration? What do you mean by reverse it?

A=1

2[SUP]13[/SUP]-1-A=8190. 2 A p + 1 = 27. 8190 mod 27 = 9 not 315.

[QUOTE=kriesel;513459]For p=13, what happens in the first iteration? What do you mean by reverse it?

A=1

2[SUP]13[/SUP]-1-A=8190. 2 A p + 1 = 27. 8190 mod 27 = 9 not 315.[/QUOTE]

[QUOTE=kriesel;513427]I'm skeptical about "I know how LL work". For starters, possible factors of 2[SUP]p[/SUP]-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 2[SUP]p[/SUP]-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.[/QUOTE]

2kp+1 that's it... k=315

None of Lan's posts have a scintilla of NT. Please move the thread to Misc. Math due to its crankiness. :thumbs-down:

VBCurtis: Moved.

[QUOTE=Lan;513448]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.[/QUOTE]Right. So you are in fact not reversing the LL.

You are suggesting to reverse the TF stage. Going from the highest divisor down to the lowest. Amirite?

So for 2[sup]31[/sup]-1 your first k value is 69273666, so you need 69273666 steps. Compared to the LL test which needs only 29 steps.

[QUOTE=retina;513472]Right. So you are in fact not reversing the LL.

You are suggesting to reverse the TF stage. Going from the highest divisor down to the lowest. Amirite?

So for 2[sup]31[/sup]-1 your first k value is 69273666, so you need 69273666 steps. Compared to the LL test which needs only 29 steps.[/QUOTE]

no... only 558658 steps... i have not tried numbers that have more than 8 digits power so i cant say yes... less than that were pretty fast...

[QUOTE=Lan;513483]no... only 558658 steps... i have not tried numbers that have more than 8 digits power so i cant say yes... less than that were pretty fast...[/QUOTE]Are you aware that for 2^31-1 using k values above 747 are unnecessary? If you aren't then think about why that is so.

Anyhow, your proposed "speed up" would be an exponential slow-down. For numbers of the size we are testing today you couldn't finish testing even a single candidate before the heat death of the universe.

[QUOTE=Lan;513483]no... only 558658 steps... i have not tried numbers that have more than 8 digits power so i cant say yes... less than that were pretty fast...[/QUOTE]
"Only" 558658 steps for 2[SUP]31[/SUP]-1.

As opposed to a full forward TF of at most 747 steps as retina points out.
Or a total of 29 LL iterations, faster yet. (No fft or Karatsuba needed at such small operands.)
Just for kicks I put into prime95 v29.8b1's worktodo, the following.
[CODE]Factor=N/A,31,1,15
PFactor=N/A,1,2,31,-1,15,2
Test=N/A,31,15,1
[/CODE]It's too small to run correctly. Comm window:

[CODE][Main thread Apr 12 11:24:08] Starting worker.
[Main thread Apr 12 11:24:08] Error: Use ECM instead of trial factoring for exponent: 31
[Main thread Apr 12 11:24:08] Illegal line in worktodo.txt file: Factor=31,1,15
[Main thread Apr 12 11:26:53] Stopping all worker threads.[/CODE]Worker window:

[CODE][Apr 12 11:24:08] Worker starting
[Apr 12 11:24:08] Setting affinity to run worker on CPU core #2
[Apr 12 11:24:08] Optimal P-1 factoring of M31 using up to 4000MB of memory.
[Apr 12 11:24:08] Assuming no factors below 2^15 and 2 primality tests saved if a factor is found.
[Apr 12 11:24:08] M31 does not need P-1 factoring.
[Apr 12 11:24:08] Setting affinity to run helper thread 1 on CPU core #2
[Apr 12 11:24:08] Starting trial factoring of M31 to 2^[B]39[/B]
[/CODE]


[url]https://www.mersenne.org/various/math.php[/url]

[QUOTE=retina;513487]Are you aware that for 2^31-1 using k values above 747 are unnecessary? If you aren't then think about why that is so.

Anyhow, your proposed "speed up" would be an exponential slow-down. For numbers of the size we are testing today you couldn't finish testing even a single candidate before the heat death of the universe.[/QUOTE]

[QUOTE=kriesel;513518]"Only" 558658 steps for 2[SUP]31[/SUP]-1.

As opposed to a full forward TF of at most 747 steps as retina points out.
Or a total of 29 LL iterations, faster yet. (No fft or Karatsuba needed at such small operands.)
Just for kicks I put into prime95 v29.8b1's worktodo, the following.
[CODE]Factor=N/A,31,1,15
PFactor=N/A,1,2,31,-1,15,2
Test=N/A,31,15,1
[/CODE]It's too small to run correctly. Comm window:

[CODE][Main thread Apr 12 11:24:08] Starting worker.
[Main thread Apr 12 11:24:08] Error: Use ECM instead of trial factoring for exponent: 31
[Main thread Apr 12 11:24:08] Illegal line in worktodo.txt file: Factor=31,1,15
[Main thread Apr 12 11:26:53] Stopping all worker threads.[/CODE]Worker window:

[CODE][Apr 12 11:24:08] Worker starting
[Apr 12 11:24:08] Setting affinity to run worker on CPU core #2
[Apr 12 11:24:08] Optimal P-1 factoring of M31 using up to 4000MB of memory.
[Apr 12 11:24:08] Assuming no factors below 2^15 and 2 primality tests saved if a factor is found.
[Apr 12 11:24:08] M31 does not need P-1 factoring.
[Apr 12 11:24:08] Setting affinity to run helper thread 1 on CPU core #2
[Apr 12 11:24:08] Starting trial factoring of M31 to 2^[B]39[/B]
[/CODE]


[url]https://www.mersenne.org/various/math.php[/url][/QUOTE]

okkey... :coffee::coffee::coffee: