Hi... trying something not new.

[Lan]

Hi... can someone help me test this? Let say you want to verify a number whether it's prime or not.
For example 2^7-1=127. Rearrange the number so it looks like this, 2*(8^2)-1
From the 3rd sequence you have 194(closest to our number) and you rearrange the number to get, 14^2-2
You will get two squares numbers 14 and 8. Divide 14 with 8 and will get 6 as the reminder, 8*1+6=14
From this equation 8*1+6=14, 8 is the base number, 1 is the multiplier and 6 is the reminder.
You can set the number by using variable in case you could not see it like AB+C=D or whatever.
add 14 to 8 and then multiply 6 then you will get 132. Skip this part and go to the multiplier.
Square the multiplier. From the equation it's 1 so you will still get 1. After that plus 1.
So in case u don't get it, if the multiplier for example is 7,you square that 7 then u will get 49. After getting 49, you add 1 so get 50.
Ok now back to 1. After adding 1 for your multiplier, divide it with 2 so 2/2 is still 1.
Now back to 132, add the answer and minus (base number^2) from 132, 132+1-64=69
Minus the last result with 2. U will get final result, 67.

//just in case u have the final result larger than 127(while running your iteration)
What you need to do is just divide the number with 127 and then the reminder will
Be the new final number. I had been testing the iteration and it seemed that the final
Numbers were always smaller than the test number.(maybe because I hadn't test it
With big enough numbers.)

Repeat this iteration for 7-1=6

//If u can barely read it, I am sorry.. I used phone to post this thread.
Please help me test this thank you...

[Viliam Furik]

14^2-2 = 127 + 67 == 67 (mod 127). You have (probably - maybe coincidentally) computed the next iteration of the LL test.

[Lan]

Originally Posted by Viliam Furik

14^2-2 = 127 + 67 == 67 (mod 127). You have (probably - maybe coincidentally) computed the next iteration of the LL test.

That's what I mean by introducing this calculation. It can be substituted as a part of the original iterations.

[Lan]

Is there anyone who can comfirm the speed difference between using standard LL test and the test above.
I mean comparing between 194/mod127 with the solution given
Should I provide a full calculations instead?
Do you want me to write solutions for p13,17 and 19?

[Uncwilly]

Originally Posted by Lan

Is there anyone who can comfirm the speed difference between using standard LL test and the test above.

Unless it is double the speed, it does not make a difference (for MPrimes). Using PRP and the proof files we are almost double the speed of a LL test and a DC.

[kriesel]

Originally Posted by Uncwilly

Unless it is demonstrably more than double the speed, it does not make a difference (for MPrimes). Using PRP and the proof files we are almostmore than double the speed of a LL test and a DC & occasional TC, 4th, etc.

(FTFY)
PRP+proof ~1.01 test effort and high certainty of correctness.
LL & LL DC & ~4% LL TC ~2.04 test effort at wavefront. 2.04/1.01 >2. And PRP/GEC/proof gets more advantageous at higher exponent, since error rate & LLTC, 4thLL, etc cost goes up with run time. And uncorrected error is found empirically to be ~2%/LLtest, but only ~24ppm for PRP.
The OP appears to be a long way of performing an LL iteration. Lots of steps described = lots of chance for error.

[Lan]

Originally Posted by Uncwilly

Unless it is double the speed, it does not make a difference (for MPrimes). Using PRP and the proof files we are almost double the speed of a LL test and a DC.

Originally Posted by kriesel

(FTFY)
PRP+proof ~1.01 test effort and high certainty of correctness.
LL & LL DC & ~4% LL TC ~2.04 test effort at wavefront. 2.04/1.01 >2. And PRP/GEC/proof gets more advantageous at higher exponent, since error rate & LLTC, 4thLL, etc cost goes up with run time. And uncorrected error is found empirically to be ~2%/LLtest, but only ~24ppm for PRP.
The OP appears to be a long way of performing an LL iteration. Lots of steps described = lots of chance for error.

Thanks to both of you for replying. Actually those tests are quite similar, though prp test has few operations involved.
(That explains why it's much faster).Even if involving more operations in one iteration will lead to errors but what I request is compare the speed of my test with the LL test ( or perhaps prp test too). I want a speed report. Thats all.

Anyway if you want me to write full calculations as an example, I will proceed.

[a1call]

You can use the LL-Test codes below to compare with your own code.
PARI-GP would probably be the most practical.

http://www.rosettacode.org/wiki/Lucas-Lehmer_test

Please let us know how your code compares.

[kriesel]

Originally Posted by Lan

Actually those tests are quite similar, though prp test has few operations involved.
(That explains why it's much faster).

PRP is fast in large part because we only need to do it once per exponent. The VDF based proof generation allows verification of correct completion for additional effort that's a fraction of a percent of a first test or of a second test.
PRP: start with seed 3. Square it mod Mp, p-1 times.
LL: start with seed 4. Square it, subtract 2 (which is almost free when done as part of carry propagation), mod Mp, p-2 times.
Best available large-number squaring algorithm is used for both in the usual GIMPS software.

Describe your method in exponent-as-a-parameter terms for exponent ~100,000,000, for comparison with the above. In algebraic form, not worked numeric trivially-small-exponent examples.
Describe what error detection and recovery methods you would incorporate in your sequence to ensure high probability of correct completion of ~100,000,000+ iterations on 100,000,000+ bit length operands.
Explain how scaling (proportionality constants or order) for your method is superior to what's described in https://www.mersenneforum.org/showpo...65&postcount=3 and elsewhere.

[Lan]

Originally Posted by a1call

You can use the LL-Test codes below to compare with your own code.
PARI-GP would probably be the most practical.

http://www.rosettacode.org/wiki/Lucas-Lehmer_test

Please let us know how your code compares.

Most of the time, people want to see the program output themselves rather than just its report. It's best for you to try I suggest, see the output with your own eyes. Here the complete calculations for p13.

Edited
I am sorry... I still don't have access to the main computer. I couldn't attach the document so I wrote it manually but I think you will get the point.


P13 =8191
37634=194^2-2
Y=194

a=2^((p-1)/2) p=13
a=2^6 a^2=2^12

Y=ax+c
194=64(3)+2

M_value=(y+ax)/c
M_value=772

x=3, x is odd
//if odd, after squaring, subtract 1 before
//dividing with 2

(3^2-1)/2
=4 add to M_value
M_value=772+4=776

Add a^2 to M_value
M_value=4096+776
M_value=4872

Subtract 2 from M_value
M_value=4870

Check if divisible by p13
No

Move M_value, y;

Y=ax+c
4870=64(76)+6

M_value=(y+ax)/c
M_value=58404

x=76, x is even
//if even, You don't have to -1
(76^2)/2
=2888 add to M_value
M_value=58404+2888=61292

//for even numbers skip this part
Add a^2 to M_value
M_value=
M_value=

Subtract 2 from M_value
M_value=61290

Check if divisible by p13
yes
M_value=61290/8191
M_value=3953

Move M_value, y;

//The rest of the calculations are the same

If you want to try on PRP test. Just substitute y with 3
(Check if divisible) and skip subtracting 2 at the end
but !!! Don't Substitute with squared number !!!
Just simply input 3, not 3^2. For example, if you substitute y
with 81^2 for p7, you won't get 84 at the end.
I hope you will give it a try.

[Lan]

Originally Posted by kriesel

PRP is fast in large part because we only need to do it once per exponent. The VDF based proof generation allows verification of correct completion for additional effort that's a fraction of a percent of a first test or of a second test.
PRP: start with seed 3. Square it mod Mp, p-1 times.
LL: start with seed 4. Square it, subtract 2 (which is almost free when done as part of carry propagation), mod Mp, p-2 times.
Best available large-number squaring algorithm is used for both in the usual GIMPS software.

Describe your method in exponent-as-a-parameter terms for exponent ~100,000,000, for comparison with the above. In algebraic form, not worked numeric trivially-small-exponent examples.
Describe what error detection and recovery methods you would incorporate in your sequence to ensure high probability of correct completion of ~100,000,000+ iterations on 100,000,000+ bit length operands.
Explain how scaling (proportionality constants or order) for your method is superior to what's described in https://www.mersenneforum.org/showpo...65&postcount=3 and elsewhere.

I will try... but I can't guarantee since I don't have access to the main computer (yet).
Nevertheless, you can try coding my calculations and see the result yourself.