A: Extended RSA

Submit

Time Limit: 3000ms
Please log-in before you submit.
See http://oucpc.imoz.jp/upload/imos01_4382.pdf.
If you need Japanese Problem Statement, please request in the clar with your e-mail address.

Description

RSA is a well-known algorithm for public-key encryption. It uses a number which is the product of two primes as a public-key. Usually the two primes are selected randomly, but Dr. Imo found that the number can contain more information by choosing particular primes. Of course, Dr. Imo is intelligent enough to demonstrate that the public-key of the new method is as marvelously strong as that of the older method.

The Imo method is simple. Seek the pair of primes if you are given one prime and two number. The two primes and the two number meet the following requirements.

  • There are two primes a, b and two number c, d (c < 2d).
  • ab ≡ c (mod 2d). ((a * b) mod (2 ** d) = c)

Thus, you can generate an RSA public-key ab which has information about c. For example, if a is 2, b is 13, c is 10 and d is 4, the remainder of division of a key 26(=ab) by 24(=2d) includes information 10(=c).

One prime b and two numbers c, d are given. You need to find the minimum prime a to assist him.