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: 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; '>': 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> <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 To: "Steven D'Aprano" 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: 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 --001a113ce222c8b03805136be880 Content-Type: text/plain; charset=UTF-8 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 > --001a113ce222c8b03805136be880 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Dario Alpern has written a progra= m that uses the Elliptic Curve Method (ECM) for factorising a number. ECM i= s 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.alpert= ron.com.ar/ECM.HTM

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

What has been said by previous contributor= s about the difficulty of factorising numbers is all true. However, there a= re some relatively fast algorithms out there. Try searching for

Number Field Sieve
Quadratic Number Field Sieve

and= see where they take you.



<= div class=3D"gmail_quote">On Sat, Apr 11, 2015 at 3:04 AM, Steven D'Apr= ano <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.=C2=A0 And once you've done the= division,
> let q be the next value for dividend.=C2=A0 So you'll get a list l= ike
>
> [3, 3, 3, 37]
>
> for the value 999


Prime factorization is a *hard* problem. If it wasn't, most of m= odern
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<= br> 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

--001a113ce222c8b03805136be880--