Factoring Challenge

All submissions for this problem are available.
The goal is to factor a given 127/128bit integer N of the form N = P*Q, where P and Q are two 64 bit primes. It is wellknown that factorization is a hard problem, and hence you are provided with partial information about the bitpattern of the primes P and Q. In particular, you are given about 50% of the bits of both P and Q, at random. The goal is to factor N by reconstructing the missing bits of the primes.
Input
The first line specifies the number of test cases, followed by a blank line.
Each test case consists of the following:
N_hex = < 32 HEX characters >
P_bit = [< 64 characters, separated by a comma and a white space >]
Q_bit = [< 64 characters, separated by a comma and a white space >]
The test cases are separated by blank lines as well.
Note:
1. The 32 Hex characters in the first line specifies N, the number you have to factor.
2. Each of the 64 characters in P_bit and Q_bit may either be 0, 1 or x.
3. The known bits are 0 or 1 and are at random locations.
4. The unknown bits are denoted by x.
5. Ordering of hex characters: N = < most significant hex > < all other hex > < least significant hex >
6. Ordering of bits: P_bit = [ < least significant bit > < all other bits > < most significant bit > ]
Output
Your output must contain the primes P and Q for each of the test cases, in HEX format, as specified below.
P_hex = < 16 HEX characters >
Q_hex = < 16 HEX characters >
The different test case outputs should be separated by blank lines.
Note:
1. All test cases MUST have an output each.
2. Each of the outputs is UNIQUE as well.
3. Ordering of hex characters: P_hex = < most significant hex > < all other hex > < least significant hex >
Example
Input: The input file will contain everything within the dashed lines (including spaces, delimeters, and line breaks):  5 N_hex = 8749d9be4bfd74973b31a79e247e765f P_bit = [x, 1, 0, 1, x, x, 0, x, x, 1, 0, 0, 0, 1, x, 1, x, x, 0, x, 0, x, 1, x, x, 0, 1, 0, x, 0, 1, x, x, 1, x, x, 0, x, 1, x, 0, x, 1, x, x, 0, 0, x, x, x, 0, 1, x, x, 1, 0, x, 0, x, x, x, 0, x, x] Q_bit = [1, x, 1, x, 1, 1, x, x, x, x, x, 1, x, 0, 1, x, x, x, 0, x, 0, 0, x, 0, x, x, 1, x, x, x, 1, x, x, 1, 0, x, x, 0, x, x, 0, x, x, x, x, x, x, x, 1, 0, x, 0, x, 1, 1, x, 0, x, 1, 1, 0, x, 1, 1] N_hex = 806e763db47bbb6295171b44776c71c3 P_bit = [x, 0, 0, 0, x, 0, 0, 0, x, 1, 1, x, x, x, x, x, x, 1, x, 1, 1, x, 0, 1, x, 1, 0, 0, 1, 1, x, x, 0, 0, 1, x, 0, x, 0, 0, x, x, x, 1, x, 1, 0, 0, x, 0, x, x, x, 1, 0, 1, x, x, 1, x, x, x, x, 1] Q_bit = [1, x, 0, 0, 1, 0, 0, 1, x, x, x, 1, x, x, x, x, x, x, x, x, 1, 1, x, x, x, x, x, x, 1, 1, 1, x, 1, x, x, 0, 0, x, x, x, x, 1, 1, 0, x, 0, 1, 0, x, 1, x, 1, 0, 1, 0, 1, x, x, 0, x, 1, 0, 1, 1] N_hex = 7593211d38b631a6c140b6983e40016b P_bit = [x, x, 0, 0, 1, 1, 1, x, x, x, 1, x, x, 0, 0, x, 0, x, x, 0, x, 1, 0, 0, 1, x, x, x, x, 0, 0, x, 1, x, 1, x, 0, 1, 0, x, x, x, 1, 1, x, 1, 1, x, 1, 0, 1, 1, 1, 1, 0, x, 1, x, 0, 0, 1, x, x, 1] Q_bit = [x, x, x, x, x, 0, x, 1, 0, 0, 0, x, 0, 0, 0, x, 1, x, 1, 0, x, x, x, x, 0, 1, 1, 0, x, x, x, x, 0, 0, 0, 0, x, x, x, x, 0, 0, x, x, 1, 1, 0, 1, 0, x, 1, x, 1, x, x, 0, 1, x, x, 1, 0, 0, x, x] N_hex = 87dd37c7451f77336d5926253ee3560f P_bit = [1, x, x, x, 1, x, 0, 1, x, 0, 1, x, 1, 1, x, 1, 0, x, 1, x, x, x, x, 1, x, 0, 1, x, x, x, 0, 1, 0, x, x, x, x, 1, 0, x, 0, x, x, 1, x, x, x, 1, 1, x, x, x, x, x, 1, 0, x, x, x, 1, x, x, 0, 1] Q_bit = [1, x, 1, x, x, x, 0, 1, x, 1, x, x, 1, x, x, x, 0, x, 1, 0, x, 1, x, x, 0, 1, x, x, 0, 0, x, x, x, 1, x, x, x, 1, x, x, 0, 1, 0, x, 0, x, 1, 1, 0, 0, x, 0, x, x, x, x, 0, x, x, 1, x, 1, 1, x] N_hex = 4f743382568e0e15dc2ab5d520763a13 P_bit = [1, x, 0, x, x, x, x, 0, 0, 1, 1, x, 1, x, 1, x, 0, 0, x, 0, x, 0, x, 0, x, 1, x, x, x, 1, x, x, x, 1, 1, 1, 1, 1, 1, x, x, x, x, 1, x, 0, 1, x, x, 0, x, 0, 1, 1, x, x, x, 0, 0, 0, 0, 0, x, x] Q_bit = [1, x, x, 1, x, 0, 1, 1, x, x, x, 1, x, x, 0, 1, x, x, 1, 1, x, x, 1, x, 1, 0, x, 0, x, 0, x, 0, 0, 1, x, 1, x, 1, 1, 1, x, x, x, 1, 0, x, 1, x, 0, 0, 1, 1, x, 0, x, 0, x, 1, 1, 1, 1, x, 0, 1]  Output: The output file should contain everything within the dashed lines (including spaces, delimeters, and line breaks):  P_hex = 914986cbd440a28b Q_hex = ee61c81aed42d9fd P_hex = 95ac2c04329b2f11 Q_hex = dbab56837bffbb93 P_hex = 913d6da795340771 Q_hex = cf3cbcb016f7809b P_hex = 897fbc22ade6b5b1 Q_hex = fcf4caa206b4f7bf P_hex = 80b1d87e3f147629 Q_hex = 9e0ccdfe554e9ddb 
Author:  bst0602 
Tags  bst0602 
Date Added:  10012011 
Time Limit:  0.738994 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, GO, NODEJS, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 