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.
There are five files each containing 10 lines of the form
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.