Sorry, an error occurred while loading the content.
Browse Groups

• ## Re: [PrimeNumbers] Does such a factoring algorithm exist?

(7)
• NextPrevious
• ... I have not heard of Bernstein s product-tree before but it sounds like my TreeSieve: http://groups.yahoo.com/group/primeform/message/4231 The GMP based
Message 1 of 7 , May 4, 2004
View Source
Paul Leyland wrote:
> > Is there a factoring algorithm which depends on the size of
> > the factors (and
> > not the integer being factored itself), and is faster than
> > trial division,
> > yet upon failure it provides a proven lower bound on the factors?
>
> Yes, if you regard Dan Bernstein's product-tree method of finding
> small prime divisors as being different from "trial division". It's
> certainly faster asymtotically than the algorithm conventionally
> known as trial division.

I have not heard of Bernstein's product-tree before but it sounds like my
TreeSieve:
http://groups.yahoo.com/group/primeform/message/4231
The GMP based implementation is 12 times faster than individual trial factoring
by primeform for 50000-digit numbers, but slow for small numbers.
This version can only factor to 2^32.

--
Jens Kruse Andersen
• The question is how it can prove a lower bound for the factors of a number. I imagine this would be easy for numbers such as repunits where factors are
Message 1 of 7 , May 4, 2004
View Source
The question is how it can prove a lower bound for the factors of a
number. I imagine this would be easy for numbers such as repunits
where factors are restricted to special forms, but for other numbers
it might not work very well because of the astonishing number of
primes.

For example, for the repunits R311 (not to be confused with R317),
R509 and R557 - the status of which is "Composite But No Factor
Known", this method seems very promising because what I once read
about repunits suggests that these numbers must have two very large
factors and if primality tests for numbers of the correct form are
available, it might solve the problem well, especially for R311,
which mystified me on seeing it in a table of repunits.

The problem is with how to test the primality of the numbers of the
appropriate form - though the effect of not doing this is most likely
to be mere wastage of time ratehr than errors - for instance with the
large 1187-digit cofactor of F12.
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.