Factoring technique, faster than trial division?

paul at fatmans.demon.co.uk paul at fatmans.demon.co.uk
Mon Sep 23 20:02:43 PDT 1996



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, Paul at fatmans.demon.co.uk
  Paul at crypto.uk.eu.org, Paul at cryptography.uk.eu.org    
       Http://www.cryptography.home.ml.org/
      Email for PGP public key, ID: 5BBFAEB1
     "Don`t forget to mount a scratch monkey"






More information about the cypherpunks-legacy mailing list