mersenneforum.org Happy New Year & parallel powermod
 Register FAQ Search Today's Posts Mark Forums Read

 2018-01-01, 19:18 #1 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 7BC16 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 parallel-able. 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 2018-01-04 at 15:55 Reason: editing title
2018-01-01, 19:58   #2
jnml

Feb 2012
Prague, Czech Republ

132 Posts

Quote:
 Originally Posted by a1call It seems to me that the powermod() function is highly parallel-able.
Please show how to parallelize computation of powermod().

 2018-01-01, 20:14 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 111101111002 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)
 2018-01-01, 20:19 #4 Nick     Dec 2012 The Netherlands 2×7×113 Posts The standard way to do this, in cases where you know the factorization of the exponent, is with the Chinese Remainder Theorem.
2018-01-01, 20:58   #5
jnml

Feb 2012
Prague, Czech Republ

132 Posts

Quote:
 Originally Posted by Nick The standard way to do this, in cases where you know the factorization of the exponent, is with the Chinese Remainder Theorem.
TIL, nice. Sad that that's not usable for prime exponents. Anyway, thanks for enlightenment.

2018-01-01, 21:22   #6
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

22·32·5·11 Posts

Quote:
 Originally Posted by Nick The standard way to do this, in cases where you know the factorization of the exponent, is with the Chinese Remainder Theorem.
I am not familiar with that. I will need to research it.
For FLT the exponent is not a prime if the candidate is an odd PRP since the power is raised to n-1.
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.

2018-01-01, 22:08   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by a1call I am not familiar with that. I will need to research it. For FLT the exponent is not a prime if the candidate is an odd PRP since the power is raised to n-1. 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.
https://en.m.wikipedia.org/wiki/Chin...ainder_theorem

 2018-01-01, 22:27 #8 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22·32·5·11 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.
2018-01-01, 22:34   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by a1call 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.
Think of lines intersecting, that may help.

 2018-01-01, 22:39 #10 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22·32·5·11 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.
2018-01-01, 22:44   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by a1call 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.
There's a difference between ${(2^n)}^2$ and $2^{(n^2)}$. So that might be why.remember exponent rules. Also Fermat's little theorem ( versus his last), can be extended to Euler's theorem.

Last fiddled with by science_man_88 on 2018-01-01 at 22:51

 Similar Threads Thread Thread Starter Forum Replies Last Post LaurV Lounge 46 2021-01-12 07:31 ji2my Lounge 0 2016-12-29 07:50 firejuggler Lounge 23 2013-01-02 06:40 ATH Lounge 17 2011-01-21 23:28 10metreh Lounge 7 2009-01-01 08:21

All times are UTC. The time now is 22:41.

Sun Jan 17 22:41:50 UTC 2021 up 45 days, 18:53, 0 users, load averages: 1.60, 1.80, 1.74