How to combine partial relations for multiple polynomial quadratic sieve?

Question

I've been trying to combine partial relations in the MPQS using the method here: https://en.wikipedia.org/wiki/Quadratic_sieve#Partial_relations_and_cycles

I am attempting to factor N = 523022617466601111760007224100074291200000001.

I have two relations which I would like to combine, which both share the prime factor 57389:

X1 = -6175407661671025670031

X2 = 15026956748675681812233

From what I understand, you first calculate the modular inverse of 57389 mod N, which is: 25882734210478439376856549451013451828887069

You then multiply: X1 * X2 * inverse (mod N) which gives: X = 523011886835272739214004532361021910836160985

However X^2 mod N in this case does not give a smooth value: 17 * 33407926819291367089 * 544340956119221163702203

I would be grateful if someone could explain what I'm doing incorrectly here?

Thank You

Answer 1

I just figured out what I was doing wrong:

When saving relations, I was saving them in the form:

X = Ax + B

Y = (X^2 - N) / A

This is how values are calculated for trial division, however this is not how relations should be stored. Once a smooth (or close to smooth) value is found using (X^2 - N) / A, it is stored as follows:

X = (Ax + B) * D^-1 (mod N)

Y = (X^2 - N) / A

Where D is the square root of A and D^-1 (mod N) is the modular inverse of D mod N.

Then to combine the relations:

1. Calculate P^-1 mod N, where P is the shared prime.

2. X = X1 * X2 * P^-1 mod N

3. Y = X^2 mod N