Kraitchik's factorisation method

[Robertcop]

Hi, I'm a new member here and I have a question concerning Kraitchik's factorisation method.
Let x^2 = y^2 (mod n). It follows that n|(x-y)(x+y) and hopefully
gcd((x-y),n) yields to a non-trival factor of n.
Does the additional prerequisite x =! y (mod n) implies that gcd((x-y),n) always yields to an non-trivial factor and n does not divide (x-y) nor (x+y), respectively?

[jasonp]

Originally Posted by Robertcop

Hi, I'm a new member here and I have a question concerning Kraitchik's factorisation method.
Let x^2 = y^2 (mod n). It follows that n|(x-y)(x+y) and hopefully
gcd((x-y),n) yields to a non-trival factor of n.
Does the additional prerequisite x =! y (mod n) implies that gcd((x-y),n) always yields to an non-trivial factor and n does not divide (x-y) nor (x+y), respectively?

See p. 48 of Per Leslie Jensen's thesis 'Integer Factorization', where he reproduces a table I vaguely remember seeing elsewhere. For n the product of two prime factors, there are 8 combinations possible and 6 of them yield a nontrivial factor.

jasonp

[akruppa]

Originally Posted by Robertcop

Does the additional prerequisite x =! y (mod n) implies that gcd((x-y),n) always yields to an non-trivial factor and n does not divide (x-y) nor (x+y), respectively?

Not by itself. If x² ≡ y² (mod n), then x ≡ ±y (mod p) for all p|n. We get the trivial factorisation iff for all such p either (1) x ≡ y (mod p) or (2) x ≡ -y (mod p). Your condition rules out case (1), you still need to rule out case (2). Thus:

Iff x !≡ ±y (mod n), the gcd will find a non-trivial factor.

As Jason points out, the likelyhood of that depends on the number of prime factors in n.

Alex