mersenneforum.org > Math Proof for the efficient algorithm used in trial factoring?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-04-22, 20:07 #1 neomacdev   Apr 2019 2·11 Posts Proof for the efficient algorithm used in trial factoring? Hi, I am well acquainted with the "very efficient algorithm for determining if a number divides 2P-1" as described at the link below. https://www.mersenne.org/various/mat...rial_factoring I've written my own implementation and have no doubt that it works as described. However, it is not obvious to me where this approach comes from. And I am curious about how to PROVE that this approach works. Specifically, why the approach of examining the exponent bit by bit, and conducting the repeated squaring, conditional multiplications by 2, and moding with the candidate factor should result in a value of 1 only when the candidate factor is indeed a divisor. Note, I've tried searching at length to find an explanation for why this works, but have not found anything. Perhaps because there doesn't appear to be a proper name for this approach, so my description isn't matching relevant results. If anyone can either share the proper name for this approach, or a link or other references to a proof, or any explanation what-so-ever that would allow me to define/derive a formal proof for this I would appreciate it. Thank you.
2019-04-22, 20:10   #2
preda

"Mihai Preda"
Apr 2015

23×149 Posts

Quote:
 Originally Posted by neomacdev Hi, I am well acquainted with the "very efficient algorithm for determining if a number divides 2P-1" as described at the link below. https://www.mersenne.org/various/mat...rial_factoring I've written my own implementation and have no doubt that it works as described. However, it is not obvious to me where this approach comes from. And I am curious about how to PROVE that this approach works. Specifically, why the approach of examining the exponent bit by bit, and conducting the repeated squaring, conditional multiplications by 2, and moding with the candidate factor should result in a value of 1 only when the candidate factor is indeed a divisor. Note, I've tried searching at length to find an explanation for why this works, but have not found anything. Perhaps because there doesn't appear to be a proper name for this approach, so my description isn't matching relevant results. If anyone can either share the proper name for this approach, or a link or other references to a proof, or any explanation what-so-ever that would allow me to define/derive a formal proof for this I would appreciate it. Thank you.
I think the name is "left to right binary exponentiation" https://en.wikipedia.org/wiki/Modular_exponentiation

2019-04-23, 06:33   #3
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·19·29 Posts

Quote:
 Originally Posted by preda I think the name is "left to right binary exponentiation" https://en.wikipedia.org/wiki/Modular_exponentiation
Added to #12 of "Concepts in GIMPS trial factoring", thanks. https://www.mersenneforum.org/showpo...23&postcount=6

2019-04-23, 06:45   #4
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23×19×29 Posts

Quote:
 Originally Posted by neomacdev Hi, I am well acquainted with the "very efficient algorithm for determining if a number divides 2P-1" as described at the link below. https://www.mersenne.org/various/mat...rial_factoring I've written my own implementation and have no doubt that it works as described. However, it is not obvious to me where this approach comes from. And I am curious about how to PROVE that this approach works. Specifically, why the approach of examining the exponent bit by bit, and conducting the repeated squaring, conditional multiplications by 2, and moding with the candidate factor should result in a value of 1 only when the candidate factor is indeed a divisor.
The eample was 223 = 1 mod 47. Subtract 1 from both sides. 223-1 = 0 mod 47
1) The method correctly implemented computes 2p mod f.
2) If and only if 2p=1 mod f, 2p-1 = 0 mod f, meaning remainder is zero, f divides 2p-1; f is a factor of 2p-1.

Last fiddled with by kriesel on 2019-04-23 at 06:48

 2019-04-27, 20:08 #6 travisjank   Feb 2019 2 Posts You have me intrigued, I look forward to this powerpoint and animations!

 Similar Threads Thread Thread Starter Forum Replies Last Post GreasyScooby Factoring 4 2018-04-27 13:48 Visu Math 66 2008-05-12 13:55 Citrix Factoring 6 2007-12-23 11:36 TheJudger Math 4 2007-10-18 19:01 Visu Factoring 22 2006-11-09 10:43

All times are UTC. The time now is 11:31.

Sun Sep 20 11:31:50 UTC 2020 up 10 days, 8:42, 0 users, load averages: 1.33, 1.21, 1.27