mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-01-01, 19:18   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

7E116 Posts
Default 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
a1call is offline   Reply With Quote
Old 2018-01-01, 19:58   #2
jnml
 
Feb 2012
Prague, Czech Republ

101010112 Posts
Default

Quote:
Originally Posted by a1call View Post
It seems to me that the powermod() function is highly parallel-able.
Please show how to parallelize computation of powermod().
jnml is offline   Reply With Quote
Old 2018-01-01, 20:14   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2,017 Posts
Default

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)
a1call is offline   Reply With Quote
Old 2018-01-01, 20:19   #4
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

7·239 Posts
Default

The standard way to do this, in cases where you know the factorization of the exponent, is with the Chinese Remainder Theorem.
Nick is offline   Reply With Quote
Old 2018-01-01, 20:58   #5
jnml
 
Feb 2012
Prague, Czech Republ

32·19 Posts
Default

Quote:
Originally Posted by Nick View Post
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.
jnml is offline   Reply With Quote
Old 2018-01-01, 21:22   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2,017 Posts
Default

Quote:
Originally Posted by Nick View Post
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.
a1call is offline   Reply With Quote
Old 2018-01-01, 22:08   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by a1call View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-01-01, 22:27   #8
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2,017 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2018-01-01, 22:34   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
science_man_88 is offline   Reply With Quote
Old 2018-01-01, 22:39   #10
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2,017 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2018-01-01, 22:44   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by a1call View Post
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
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


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

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

Fri May 7 16:41:42 UTC 2021 up 29 days, 11:22, 1 user, load averages: 2.25, 2.70, 3.11

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.