find all multiplicands and multipliers for a number

[Stephen Tucker]

Dario Alpern has written a program that uses the Elliptic Curve Method
(ECM) for factorising a number. ECM is one of the _very_ fast methods for
finding the prime factors of a number. He has even offered the code for his
program. You could have a go at using or converting his code to do what you
are wanting to do. The URL for this is

http://www.alpertron.com.ar/ECM.HTM

This program found the prime factors of  2^111+1  in less than 1 second on
my computer. (And that is the string I gave it.)

What has been said by previous contributors about the difficulty of
factorising numbers is all true. However, there are some relatively fast
algorithms out there. Try searching for

Number Field Sieve
Quadratic Number Field Sieve

and see where they take you.



On Sat, Apr 11, 2015 at 3:04 AM, Steven D'Aprano <
steve+comp.lang.python at pearwood.info> wrote:

> On Sat, 11 Apr 2015 11:06 am, Dave Angel wrote:
>
> > But the real place to get improvement is to only divide by primes,
> > rather than every possible integer.  And once you've done the division,
> > let q be the next value for dividend.  So you'll get a list like
> >
> > [3, 3, 3, 37]
> >
> > for the value 999
>
>
> Prime factorization is a *hard* problem. If it wasn't, most of modern
> technology that relies on encryption (like https, ssh, internet banking
> etc.) would be trivially broken.
>
> But for what it is worth, my pyprimes library can return the prime
> factorization of numbers:
>
> py> import pyprimes.factors
> py> pyprimes.factors.factorise(1234567890)
> [2, 3, 3, 5, 3607, 3803]
> py> pyprimes.factors.factorise(9753124680)
> [2, 2, 2, 3, 3, 3, 5, 13, 191, 3637L]
>
> It may be a bit slow for very large numbers. On my computer, this takes 20
> seconds:
>
> py> pyprimes.factors.factorise(2**111+1)
> [3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]
>
>
> but that is the nature of factorising large numbers.
>
>
> http://code.google.com/p/pyprimes/source/browse/
>
>
>
> --
> Steven
>
> --
> https://mail.python.org/mailman/listinfo/python-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20150411/90d6e184/attachment.html>