[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

259.0. "Making factoring faster" by SUPER::MATTHEWS () Wed Apr 17 1985 01:38

"Making Factoring Faster,"  SCIENCE,  19 April 1985

"The Dutch mathematician Hendrik Lenstra recently announced his discovery
of a new factoring method that has surprised and delighted the mathematical
community by its simplicity and cleverness...

"Lenstra's method is limited. It is very fast for numbers whose prime factors
are of different sizes. For numbers whose prime factors are approximately
equal in size, however, the algorithm is only about as fast as the best
existing methods.

"Because of this limitation, Lenstra's method is expected to alter the
sociology of the factoring community, splitting the pure from the applied
factorers. Until recently, nearly all factorers were pure. Most mathematicians
who were interested in factoring were motivated simply because the numbers
were there... As they got better at factoring, they gradually knocked off
one number after another from their list... like stamp collectors who try
to fill in missing gaps in their collections.

"In contrast to these mathematicians, there is now a group that factors
because factoring is related to cryptography... Factoring to break one of
the new codes, however, is a very particular type of factoring. To break
these codes, it is necessary to factor a large number... composed of two
prime factors of approximately equal size, which means that Lenstra's method
will be no better than the methods already at hand...

"Lenstra uses mathematical objects, called elliptic curves, to elicit
information about a number's factors by working solely with the number to
be factored... A factoring scheme devised by the English mathematician J.
Pollard, called the Pollard rho method, does the same sort of thing, only
using quadratic functions rather than elliptic curves. [This article gives
no further explanation of the method.]

"But now that the door has been opened, it is possible that mathematicians
may find other sorts of functions useful for factoring... mathematicians
are left with the question of whether factoring is intrinsically a hard
problem or whether there is some as yet undiscovered method that will make
it easy."
T.RTitleUserPersonal
Name
DateLines