We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

# Project Euler #182: RSA encryption

# Project Euler #182: RSA encryption

Contest ends in

#### Sort by

recency

#### |

#### 9 Discussions

#### |

Please Login in order to post a comment

This problem can be transformed into a problem of evaluating sums of the form

Those two pages shall help: https://en.wikipedia.org/wiki/Chinese_remainder_theorem https://math.stackexchange.com/questions/58373/rsa-unconcealed-messages

Can anyone give a hint to the next step? I observed that the minimum sum is always 9. So I have to find e such that 1. gcd(e, t) == 1 2. gcd(e-1, p-1) == 2 3. gcd(e-1, q-1) == 2

Terminated due to timeout after 7 Testcases? Any hints?

## include

## include

## include

## include

## include

using namespace std;

long gcd(long x, long y) { long r; while(y!=0) { r=x%y; x=y; y=r; } return x; }

int main() { long phi,p,q, e, min=9999999,noum,ans=0; cin>>p>>q;

phi=(p-1)(q-1); for(e=2;e(gcd(e-1,q-1)+1); if(noum