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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #182: RSA encryption

Project Euler #182: RSA encryption

Problem
Submissions
Leaderboard
Discussions

This problem is a programming version of Problem 182 from projecteuler.net

The RSA encryption is based on the following procedure:

Generate two distinct primes and .
Compute and .
Find an integer , , such that .

A message in this system is a number in the interval .
A text to be encrypted is then somehow converted to messages (numbers in the interval ).
To encrypt the text, for each message, , is calculated.

To decrypt the text, the following procedure is needed: calculate such that , then for each encrypted message, , calculate .

There exist values of and such that .
We call messages for which unconcealed messages.

An issue when choosing is that there should not be too many unconcealed messages.
For instance, let and .
Then and .
If we choose , then, although it turns out that all possible messages () are unconcealed when calculating .
For any valid choice of there exist some unconcealed messages.
It's important that the number of unconcealed messages is at a minimum.

For given and find the sum of all values of , and , so that the number of unconcealed messages for this value of is at a minimum.

Input Format

Every test case contains a single line with two integers separated by a single space: and .

Constraints

and are distinct primes.

.

But for more than half of tests .

Output Format

Output the sum of all values of for which the number of unconcealed messages is at a minimum. As this number may be huge, output it modulo .

Sample Input

11 13

Sample Output

438

Explanation

The needed values of are , , , , and which give us only unconcealed messages.

Author

bayleef

Difficulty

Expert

Max Score

100

Submitted By

230

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy