1996-09-24 - Factoring technique, faster than trial division?

Header Data

From: paul@fatmans.demon.co.uk
To: cypherpunks@toad.com
Message Hash: 0e500712f49cc6057ee5e7b5428f1e2831e980a8e64057bab16e14af272f9632
Message ID: <843513658.17121.0@fatmans.demon.co.uk>
Reply To: N/A
UTC Datetime: 1996-09-24 03:02:43 UTC
Raw Date: Tue, 24 Sep 1996 11:02:43 +0800

Raw message

From: paul@fatmans.demon.co.uk
Date: Tue, 24 Sep 1996 11:02:43 +0800
To: cypherpunks@toad.com
Subject: Factoring technique, faster than trial division?
Message-ID: <843513658.17121.0@fatmans.demon.co.uk>
MIME-Version: 1.0
Content-Type: text/plain



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@fatmans.demon.co.uk
  Paul@crypto.uk.eu.org, Paul@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"





Thread