- All Contests
- ProjectEuler+
- Project Euler #182: RSA encryption

# Project Euler #182: RSA encryption

# Project Euler #182: RSA encryption

_{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.