194. RSA Cipher

Codeforces

IDCF10269194

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

The RSA cipher, invented in 1977, is widely used today for encryption of data online. The first step of making a key for the RSA cipher is choosing a number $n$ at the start. In the real world, $n$ is extremely large, usually at least 50 digits long, but for this problem, you'll select an $n$ less than $10^6$. When choosing the numbers for the key, $n$ must be a semiprime. A semiprime is any number that has exactly two prime factors, not necessarily distinct. For example, 6, 34, and 25 are semiprimes, but 30, 7, and 27 are not semiprimes. After choosing $n$, you choose another number $e$, which can be any number less than $n$ and greater than one that is relatively prime to $n$. Two numbers are relatively prime if they don't share any prime factors. $n$ and $e$ compose the "public key", and the private key is calculated differently, which won't be covered in this problem. Given a number $m$, find the public key that has the largest $n$, where $n$ and $e$ are less than or equal to $m$. If multiple answers have the same $n$, pick the one with the smallest $e$. The only line of input contains a single positive integer $m$: the upper limit on $n$ and $e$. Output two space-separated integers, representing your chosen public key: $n$ and $e$, as described above. $n$ and $e$ should both be less than or equal $m$, $n$ should be a semiprime, and $e$ should be relatively prime to $n$. ## Input The only line of input contains a single positive integer $m$: the upper limit on $n$ and $e$. ## Output Output two space-separated integers, representing your chosen public key: $n$ and $e$, as described above. $n$ and $e$ should both be less than or equal $m$, $n$ should be a semiprime, and $e$ should be relatively prime to $n$. [samples]

**Definitions** Let $ m \in \mathbb{Z}^+ $ be the upper bound. Let $ \mathcal{S} = \{ n \in \mathbb{Z} \mid 1 < n \leq m,\ n \text{ is a semiprime} \} $. For each $ n \in \mathcal{S} $, let $ \mathcal{E}_n = \{ e \in \mathbb{Z} \mid 1 < e \leq m,\ \gcd(e, n) = 1 \} $. **Constraints** 1. $ 1 < n \leq m $ 2. $ n $ is a semiprime (product of exactly two primes, not necessarily distinct) 3. $ 1 < e \leq m $ 4. $ \gcd(e, n) = 1 $ **Objective** Find $ (n^*, e^*) $ such that: - $ n^* = \max \mathcal{S} $, - $ e^* = \min \mathcal{E}_{n^*} $. Output: $ n^* $ and $ e^* $.

API Response (JSON)

{
  "problem": {
    "name": "194. RSA Cipher",
    "description": {
      "content": "The RSA cipher, invented in 1977, is widely used today for encryption of data online. The first step of making a key for the RSA cipher is choosing a number $n$ at the start. In the real world, $n$ is",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269194"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The RSA cipher, invented in 1977, is widely used today for encryption of data online. The first step of making a key for the RSA cipher is choosing a number $n$ at the start. In the real world, $n$ is...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ m \\in \\mathbb{Z}^+ $ be the upper bound.  \nLet $ \\mathcal{S} = \\{ n \\in \\mathbb{Z} \\mid 1 < n \\leq m,\\ n \\text{ is a semiprime} \\} $.  \nFor each $ n \\in \\mathcal{S} $, let $ \\m...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments