Re: find all multiplicands and multipliers for a number

References	<890bd388-f50a-4dec-9ef5-27715427472a@googlegroups.com> <mailman.209.1428714381.12925.python-list@python.org> <55288135$0$12997$c3e8da3$5496439d@news.astraweb.com>
Date	2015-04-11 06:11 +0100
Subject	Re: find all multiplicands and multipliers for a number
From	Stephen Tucker <stephen_tucker@sil.org>
Newsgroups	comp.lang.python
Message-ID	<mailman.213.1428729074.12925.python-list@python.org> (permalink)

Show all headers | View raw

[Multipart message — attachments visible in raw view] - view raw

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@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
>

Thread

find all multiplicands and multipliers for a number ravas <ravas@outlook.com> - 2015-04-10 16:37 -0700
  Re: find all multiplicands and multipliers for a number Dave Angel <d@davea.name> - 2015-04-10 21:16 -0400
  Re: find all multiplicands and multipliers for a number Dave Angel <davea@davea.name> - 2015-04-10 21:06 -0400
    Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-11 12:04 +1000
      Re: find all multiplicands and multipliers for a number Stephen Tucker <stephen_tucker@sil.org> - 2015-04-11 06:11 +0100
      Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-10 23:08 -0700
        Re: find all multiplicands and multipliers for a number Marko Rauhamaa <marko@pacujo.net> - 2015-04-11 10:14 +0300
          Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-11 09:59 -0700
            Re: find all multiplicands and multipliers for a number Marko Rauhamaa <marko@pacujo.net> - 2015-04-11 20:31 +0300
              Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-11 10:52 -0700
                Re: find all multiplicands and multipliers for a number Chris Angelico <rosuav@gmail.com> - 2015-04-12 07:10 +1000
                Re: find all multiplicands and multipliers for a number Terry Reedy <tjreedy@udel.edu> - 2015-04-11 19:58 -0400
                Re: find all multiplicands and multipliers for a number Chris Angelico <rosuav@gmail.com> - 2015-04-12 10:16 +1000
          Re: find all multiplicands and multipliers for a number wolfram.hinderer@googlemail.com - 2015-04-11 16:17 -0700
            Re: find all multiplicands and multipliers for a number Marko Rauhamaa <marko@pacujo.net> - 2015-04-12 10:17 +0300
              Primes [was Re: find all multiplicands and multipliers for a number] Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-12 20:48 +1000
              Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 18:56 -0700
                Re: find all multiplicands and multipliers for a number Dave Angel <davea@davea.name> - 2015-04-12 22:35 -0400
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 20:30 -0700
                Re: find all multiplicands and multipliers for a number Dave Angel <davea@davea.name> - 2015-04-13 00:35 -0400
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 22:25 -0700
                Re: find all multiplicands and multipliers for a number Dave Angel <davea@davea.name> - 2015-04-13 01:43 -0400
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 22:57 -0700
                Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-13 17:21 +1000
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-13 19:42 -0700
                Re: find all multiplicands and multipliers for a number Chris Angelico <rosuav@gmail.com> - 2015-04-14 12:47 +1000
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-13 19:54 -0700
                Re: find all multiplicands and multipliers for a number Rustom Mody <rustompmody@gmail.com> - 2015-04-14 03:35 -0700
                Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-14 23:30 +1000
                Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-14 23:40 +1000
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-14 19:37 -0700
                Re: find all multiplicands and multipliers for a number Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-15 09:59 -0600
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-15 09:21 -0700
                Re: find all multiplicands and multipliers for a number Chris Kaynor <ckaynor@zindagigames.com> - 2015-04-15 09:46 -0700
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-15 10:37 -0700
                Searching the archives Gil Dawson <Gil@GilDawson.com> - 2015-04-15 11:47 -0700
                Installing Python Gil Dawson <Gil@GilDawson.com> - 2015-04-15 12:09 -0700
                Re: Searching the archives Tim Golden <mail@timgolden.me.uk> - 2015-04-15 20:16 +0100
                Re: Installing Python Ned Deily <nad@acm.org> - 2015-04-15 13:32 -0700
                Re: find all multiplicands and multipliers for a number Rustom Mody <rustompmody@gmail.com> - 2015-04-15 21:17 -0700
        Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-11 17:35 +1000
          Re: find all multiplicands and multipliers for a number jonas.thornvall@gmail.com - 2015-04-11 01:47 -0700
          Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-11 09:31 -0700
            Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-12 12:22 +1000
              Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-11 21:24 -0700
                Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-12 14:29 +1000
          Re: find all multiplicands and multipliers for a number Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-11 12:41 -0400
            Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-11 10:02 -0700
        Re: find all multiplicands and multipliers for a number Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-11 12:37 -0400
      Re: find all multiplicands and multipliers for a number Brian Gladman <blindanagram@nowhere.net> - 2015-04-12 10:34 +0100
        Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-13 00:29 +1000
          Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 10:20 -0700
            Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 10:23 -0700
            Re: find all multiplicands and multipliers for a number Brian Gladman <blindanagram@nowhere.net> - 2015-04-12 20:15 +0100
              Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 12:45 -0700
          Re: find all multiplicands and multipliers for a number Brian Gladman <blindanagram@nowhere.net> - 2015-04-12 20:07 +0100
  Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-10 18:28 -0700
  Re: find all multiplicands and multipliers for a number Dave Farrance <DaveFarrance@OMiTTHiSyahooANDTHiS.co.uk> - 2015-04-11 10:03 +0100
  Re: find all multiplicands and multipliers for a number ravas <ravas@outlook.com> - 2015-04-11 10:11 -0700

csiph-web