Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #88802

Re: find all multiplicands and multipliers for a number

Path csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path <stephen_tucker@sil.org>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.088
X-Spam-Evidence '*H*': 0.82; '*S*': 0.00; 'string': 0.09; 'curve': 0.09; 'subject:number': 0.09; 'cc:addr:python-list': 0.11; '999': 0.16; '[2,': 0.16; 'broken.': 0.16; 'contributors': 0.16; 'division,': 0.16; 'elliptic': 0.16; 'integer.': 0.16; 'ssh,': 0.16; 'subject:skip:m 10': 0.16; 'to:addr:pearwood.info': 0.16; 'to:addr:steve+comp.lang.python': 0.16; "to:name:steven d'aprano": 0.16; 'trivially': 0.16; 'sat,': 0.16; 'wrote:': 0.18; 'do.': 0.18; 'library': 0.18; 'bit': 0.19; 'written': 0.21; 'import': 0.22; 'cc:addr:python.org': 0.22; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; '&gt;': 0.26; 'second': 0.26; 'header:In-Reply- To:1': 0.27; 'skip:p 30': 0.29; 'am,': 0.29; 'url:code': 0.29; '(like': 0.30; 'converting': 0.30; 'nature': 0.30; 'message- id:@mail.gmail.com': 0.30; 'url:mailman': 0.30; 'code': 0.31; '13,': 0.31; "d'aprano": 0.31; 'relies': 0.31; 'steven': 0.31; 'there.': 0.32; 'subject:all': 0.32; 'url:python': 0.33; 'computer.': 0.33; 'url:source': 0.33; 'could': 0.34; 'received:209.85': 0.35; 'offered': 0.35; 'problem.': 0.35; 'received:209.85.220': 0.35; 'etc.)': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'done': 0.36; 'url:listinfo': 0.36; 'next': 0.36; 'method': 0.36; 'possible': 0.36; 'url:org': 0.36; 'searching': 0.37; 'list': 0.37; 'received:209': 0.37; 'previous': 0.38; 'rather': 0.38; 'url:mail': 0.40; 'even': 0.60; 'algorithms': 0.60; 'dave': 0.60; 'most': 0.60; 'numbers': 0.61; 'you.': 0.62; "you'll": 0.62; "you've": 0.63; 'real': 0.63; 'field': 0.63; 'url:p': 0.64; 'relatively': 0.65; 'difficulty': 0.68; 'url:ar': 0.68; 'internet': 0.71; 'url:htm': 0.73; 'prime': 0.74; '2015': 0.84; 'divide': 0.84; 'improvement': 0.84; 'subject:find': 0.84; 'worth,': 0.84; 'banking': 0.87; 'angel': 0.91; 'numbers:': 0.91; 'wanting': 0.93; 'factors': 0.97
X-Google-DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=74MGHijcM0lhWVlJhQcUfdFbIrsrRnB65w0tKC08ueY=; b=XECB7geYEF6wkheZFgpvM5b5S76fK/ejdG/KmXOPLhez7dte+qmmFA8yZ+A7xA7Fjt Oiv+gD1iLyXxbJBNZebFCqUxM22qf5mz+DjyH4aCZd6mSVcFzL3aOqKeJhuREMDRlCLZ ud0Kkf7/rpMtDolhIU63HIZOjqA8CU/9GTa0Qw6I73P8gz2TSDXlnZOs4Ff2v+Zl5Wbj IF4kjyLTeJ0+LDYs/ybTGBIu/bLoGqmAwHpJL5dmD3CYCiN2MZ4cDAwqX9lCEk112j4i 49iVcGXhkU2B2dQFCI+yJkwauyStrg1nOe76w0WlhqXTJWZFU4midk9aq1v0gB0O5wGZ kAmw==
X-Gm-Message-State ALoCoQn8FvZkRvB99/H3fTjB0Z1baGTbTb7HI4IFngB8zCgRSEfdeItbh15YQrYRZEwedMT4It0n
MIME-Version 1.0
X-Received by 10.202.184.3 with SMTP id i3mr930196oif.61.1428729071440; Fri, 10 Apr 2015 22:11:11 -0700 (PDT)
In-Reply-To <55288135$0$12997$c3e8da3$5496439d@news.astraweb.com>
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 Sat, 11 Apr 2015 06:11:11 +0100
Subject Re: find all multiplicands and multipliers for a number
From Stephen Tucker <stephen_tucker@sil.org>
To "Steven D'Aprano" <steve+comp.lang.python@pearwood.info>
Cc python-list@python.org
Content-Type multipart/alternative; boundary=001a113ce222c8b03805136be880
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.20
Precedence list
List-Id General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive <http://mail.python.org/pipermail/python-list/>
List-Post <mailto:python-list@python.org>
List-Help <mailto:python-list-request@python.org?subject=help>
List-Subscribe <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups comp.lang.python
Message-ID <mailman.213.1428729074.12925.python-list@python.org> (permalink)
Lines 148
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1428729074 news.xs4all.nl 2865 [2001:888:2000:d::a6]:52125
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:88802

Show key headers only | 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
>

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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