20060206, 12:39  #1 
Feb 2006
11_{2} Posts 
Kraitchik's factorisation method
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(xy)(x+y) and hopefully gcd((xy),n) yields to a nontrival factor of n. Does the additional prerequisite x =! y (mod n) implies that gcd((xy),n) always yields to an nontrivial factor and n does not divide (xy) nor (x+y), respectively? 
20060206, 13:37  #2  
Tribal Bullet
Oct 2004
DD9_{16} Posts 
Quote:
jasonp 

20060206, 21:03  #3  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
Iff x !≡ ±y (mod n), the gcd will find a nontrivial factor. As Jason points out, the likelyhood of that depends on the number of prime factors in n. Alex Last fiddled with by akruppa on 20060206 at 21:04 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
B1 and B2 in P1 method  Miszka  Math  13  20131227 20:23 
factorisation  devarajkandadai  Factoring  7  20130706 03:44 
New Method  Unregistered  Miscellaneous Math  14  20130524 10:55 
Records for complete factorisation  BrianE  Math  25  20091216 21:40 
Being coy about a factorisation  fivemack  Math  7  20071117 01:27 