20180101, 19:18  #1 
"Rashid Naimi"
Oct 2015
Remote to Here/There
7E1_{16} Posts 
Happy New Year & parallel powermod
Hi all,
I have made no secret that I find the powermod() function very impressive and the best thing since sliced bread. However despite its empowering virtues, it remains the bottleneck at performing FLT PRP tests for large integers. The recent timing estimates for testing the N50 for a twin prime (40+ hours), got me thinking that there is room for improvement. It seems to me that the powermod() function is highly parallelable. I can think of a distributed computing architecture, where multiple hierarchies of computers break down the exponent to smaller integers, compute the Mods and multiply the results for much faster computation than currently possible. Please let me know your thoughts. Thank you in advance. Last fiddled with by CRGreathouse on 20180104 at 15:55 Reason: editing title 
20180101, 19:58  #2 
Feb 2012
Prague, Czech Republ
10101011_{2} Posts 

20180101, 20:14  #3 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2,017 Posts 
Well, there are 2 basic and related principles that can be utilised in parallel.
Mod(5,19)^6 Mod(7, 19) (Mod(5,19)^2)^3 Mod(7, 19) & Mod(5,19)^17 Mod(4, 19) (Mod(5,19)^9)*(Mod(5,19)^8) Mod(4, 19) 
20180101, 20:19  #4 
Dec 2012
The Netherlands
7·239 Posts 
The standard way to do this, in cases where you know the factorization of the exponent, is with the Chinese Remainder Theorem.

20180101, 20:58  #5 
Feb 2012
Prague, Czech Republ
3^{2}·19 Posts 

20180101, 21:22  #6  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2,017 Posts 
Quote:
For FLT the exponent is not a prime if the candidate is an odd PRP since the power is raised to n1. But my second posted "principle" does not require the knowing of the factorization of the exponent. I still maintain there is parallel computing advantage with the right hierarchial architecture. Thank you for all the replies. 

20180101, 22:08  #7  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:


20180101, 22:27  #8 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2,017 Posts 
Thank you SM.
There are a bit of too many steps and complexity for me to wrap my casual head around. But I think I get the concept. Thank you again. 
20180101, 22:34  #9 
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 

20180101, 22:39  #10 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2,017 Posts 
It seems like the Mod calculation to the power of n takes half the time of mod calculation to the power of n^2. As such the paralleling is not very straight forward. At first glance one might say calculate the closest nth root power and then raise that to the power of n and multiply the residue (1st use, hopefully correct) of the original exponent.
But this will end up taking the same amount of time. But by multiple threads calculating different small exponents and then multiplying the results and by doing this in multiple hierarchies, many computers will do simultaneously and different and small exponent calculations that should save time. 
20180101, 22:44  #11  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
Last fiddled with by science_man_88 on 20180101 at 22:51 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Happy New Year Everybody  LaurV  Lounge  46  20210112 07:31 
Happy New Year  ji2my  Lounge  0  20161229 07:50 
Happy new year  firejuggler  Lounge  23  20130102 06:40 
Happy Prime Year MMXI!  ATH  Lounge  17  20110121 23:28 
Happy New Year 2009!  10metreh  Lounge  7  20090101 08:21 