In the factoring problem, a natural number is given and the task is to find two factors of it or determine that the number is prime. Factoring is a well-known mathematical problem and, for example, the security of the RSA public key encryption method rests on the difficulty of factoring large integers.  Interesting challenging test cases can be obtained, e.g., by giving a product of two primes as the input. The benchmarks can be made gradually more and more difficult by increasing the number of bits in the binary number to be factored.

INPUT: A binary number.

OUTPUT: Two factors of the input if it is composite and otherwise
indication that the input is prime.

DATA SETS

There are five files each containing 10 lines of the form

p b1*b2

where p is a (binary) number having two prime factors b1 and b2. For example, the file 15-bits contains 10 such lines where each p has 15 bits.

10-bits
15-bits
20-bits
25-bits
30-bits

NOTES:

1. One way of solving the factoring problem is to encode binary multiplication in such a way that it can be used also in the backward direction, i.e., to compute two factors (B1,B2) of a binary number P.
2. For encoding binary multiplication typical regular hardware designs can be exploited (see, e.g., Pucknell and Eshraghian, Basic VLSI Design,
3. Prentice Hall or other similar textbooks). Rules with variables can used to present a regular design in a compact form.