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.

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

over a system of linear congruences

where

are 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 constraint

and the observation that

when 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 of

can 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.

## Project Euler #182: RSA encryption

You are viewing a single comment's thread. Return to all comments â†’

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