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

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

over a system of linear congruenceswhereare distinct prime factors of the Carmichael totient , and subsequently adding up the sums using the inclusion-exclusion principle based on the number of equations chosen in each system. The value of depends on . This algorithm can be derived from the constraintand the observation thatwhen the number of unconcealed messages for is minimum. Ergo, this algorithm is equivalent to summing up all potential candidates for and then subtracting those candidates that fail to meet the constraints. The prime factorization for large numbers in the ballpark ofcan be computed rapidly using the Pollard's rho algorithm. Some care is needed to prevent loss of precision while dividing big numbers in Pollard's algorithm. Each system of linear congruences can be solved via the Chinese remainder theorem.

+ 1 comment def gcd(a, b): while b != 0: t = b b = a % t a = t return a p, q = input().split() p = int(p) q = int(q) n = p*q phi = (p-1)*(q-1) bmin = -1 lis = set() for e in range(2, phi): mini = 0 if gcd(e, phi) != 1: continue for m in range(n): c = (m ** e)%n if c == m: mini += 1 if bmin != -1 and mini > bmin: break if bmin == -1 or bmin > mini: bmin = mini lis.clear() lis.add(e) elif bmin == mini: lis.add(e) print(sum(lis) % (10 ** 9 + 7))

Can someone explain where can the code be optimized? It gets a timeout on all but the 1st test case

+ 0 comments

+ 0 comments 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

+ 0 comments Terminated due to timeout after 7 Testcases? Any hints?

Load more conversations

Sort 9 Discussions, By:

Please Login in order to post a comment