[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Factoring technique, faster than trial division?




just an idea I came up with today, I don`t suggest it is a fast 
factoring method, but it would be interesting to know if it is faster 
than say trial division:

Calcuate a composite number H such that H has a large number of prime 
factors (hundreds).

now  use the euclidean algorithm to try to find a gcd of X (the 
number being factored) and H, if there is none try a new H, if there 
is you have found a factor.

It is hardly elegant but I would nevertheless be interested to see if 
it is apreciably faster than other kludge methods like trial 
division. 


  Datacomms Technologies web authoring and data security
       Paul Bradley, [email protected]
  [email protected], [email protected]    
       Http://www.cryptography.home.ml.org/
      Email for PGP public key, ID: 5BBFAEB1
     "Don`t forget to mount a scratch monkey"