**Problem:**

The RSA encryption is based on the following procedure:

Generate two distinct primes p and q.

Compute n=pq and φ=(p-1)(q-1).

Find an integer e, 1[<]e[<]φ, such that gcd(e,φ)=1.

A message in this system is a number in the interval [0,n-1].

A text to be encrypted is then somehow converted to messages (numbers in the interval [0,n-1]).

To encrypt the text, for each message, m, c=me mod n is calculated.

To decrypt the text, the following procedure is needed: calculate d such that ed=1 mod φ, then for each encrypted message, c, calculate m=cd mod n.

There exist values of e and m such that me mod n=m.

We call messages m for which me mod n=m unconcealed messages.

An issue when choosing e is that there should not be too many unconcealed messages.

For instance, let p=19 and q=37.

Then n=19*37=703 and φ=18*36=648.

If we choose e=181, then, although gcd(181,648)=1 it turns out that all possible messages

m (0[≤]m[≤]n-1) are unconcealed when calculating me mod n.

For any valid choice of e there exist some unconcealed messages.

It's important that the number of unconcealed messages is at a minimum.

Choose p=1009 and q=3643.

Find the sum of all values of e, 1[<]e[<]φ(1009,3643) and gcd(e,φ)=1, so that the number of unconcealed messages for this value of e is at a minimum.

Generate two distinct primes p and q.

Compute n=pq and φ=(p-1)(q-1).

Find an integer e, 1[<]e[<]φ, such that gcd(e,φ)=1.

A message in this system is a number in the interval [0,n-1].

A text to be encrypted is then somehow converted to messages (numbers in the interval [0,n-1]).

To encrypt the text, for each message, m, c=me mod n is calculated.

To decrypt the text, the following procedure is needed: calculate d such that ed=1 mod φ, then for each encrypted message, c, calculate m=cd mod n.

There exist values of e and m such that me mod n=m.

We call messages m for which me mod n=m unconcealed messages.

An issue when choosing e is that there should not be too many unconcealed messages.

For instance, let p=19 and q=37.

Then n=19*37=703 and φ=18*36=648.

If we choose e=181, then, although gcd(181,648)=1 it turns out that all possible messages

m (0[≤]m[≤]n-1) are unconcealed when calculating me mod n.

For any valid choice of e there exist some unconcealed messages.

It's important that the number of unconcealed messages is at a minimum.

Choose p=1009 and q=3643.

Find the sum of all values of e, 1[<]e[<]φ(1009,3643) and gcd(e,φ)=1, so that the number of unconcealed messages for this value of e is at a minimum.

**Solution:**

45228

**Code:**

The solution may include methods that will be found here: Library.java .

The solution may include methods that will be found here: Library.java .

public interface EulerSolution{

public String run();

}

We don't have code for that problem yet! If you solved that out using Java, feel free to contribute it to our website, using our "Upload" form.

## No comments :

## Post a Comment