mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-09-24, 10:09   #1
Lan
 
Apr 2019

100012 Posts
Default Hi... trying something not new.

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...

Last fiddled with by Lan on 2021-09-24 at 10:13
Lan is offline   Reply With Quote
Old 2021-09-24, 14:01   #2
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2×3×113 Posts
Default

14^2-2 = 127 + 67 == 67 (mod 127). You have (probably - maybe coincidentally) computed the next iteration of the LL test.
Viliam Furik is offline   Reply With Quote
Old 2021-09-24, 15:03   #3
Lan
 
Apr 2019

17 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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 offline   Reply With Quote
Old 2021-09-25, 17:07   #4
Lan
 
Apr 2019

17 Posts
Default

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?
Lan is offline   Reply With Quote
Old 2021-09-25, 18:15   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2×33×5×37 Posts
Default

Quote:
Originally Posted by Lan View Post
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.
Uncwilly is offline   Reply With Quote
Old 2021-09-25, 18:32   #6
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

10110100010112 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
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.

Last fiddled with by kriesel on 2021-09-25 at 18:39
kriesel is online now   Reply With Quote
Old 2021-09-25, 20:40   #7
Lan
 
Apr 2019

17 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
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.
Quote:
Originally Posted by kriesel View Post
(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.
Lan is offline   Reply With Quote
Old 2021-09-25, 21:18   #8
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

1000010101102 Posts
Default

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.
a1call is online now   Reply With Quote
Old 2021-09-25, 22:40   #9
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

29·199 Posts
Default

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

Last fiddled with by kriesel on 2021-09-25 at 22:41
kriesel is online now   Reply With Quote
Old 2021-09-26, 20:57   #10
Lan
 
Apr 2019

1710 Posts
Default

Quote:
Originally Posted by a1call View Post
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 is offline   Reply With Quote
Old 2021-09-26, 21:06   #11
Lan
 
Apr 2019

17 Posts
Default

Quote:
Originally Posted by kriesel View Post
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.
Lan is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 03:57.


Sat Oct 16 03:57:08 UTC 2021 up 84 days, 22:26, 0 users, load averages: 0.91, 0.98, 1.02

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.