Mailing Lists: Apple Mailing Lists
Image of Mac OS face in stamp
Re: [apple scitech] Request: Factorization
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [apple scitech] Request: Factorization

The examples shown below are relatively easy as compared to, well, hard-to-factor 100 digit integers. Most were handled by a combination of trial division and Pollard methods (Almost certainly Pollard p-1 is used in some; Pollard rho might or might not be used as well). Also I will mention that probabilistic primality testing is used to determine when to stop.

A couple of them, in particular 10^100+7, look like they also made their way into the ECM (elliptic curve method). None of these examples went into MPQS (the multi-polynomial quadratic sieve). Had they done so, I'm not sure they would emerge. Factoring integers in that size range can be strenuous (well, primes are easy...).

Somewhere in the middle are examples like 100^10+20. It takes a few minutes and I'm sure is making substantial use of ECM. The larger factors have digit lengths of around {7, 11, 13, 22, 47}. All but the first look like they would not surrender themselves to the Pollard posse.

Daniel Lichtblau
Wolfram Research

Re: [apple scitech] Request: Factorization

    Subject: Re: [apple scitech] Request: Factorization
    From: Bryan Jones <email@hidden>
    Date: Wed, 12 Oct 2011 06:47:55 -0600
    Accept-language: en-US
    Acceptlanguage: en-US
    Delivered-to: email@hidden
    Delivered-to: email@hidden
    Thread-index: AcyI3Sk0vSmd3kQZSQ+LYbYuqNnTWA==
    Thread-topic: [apple scitech] Request: Factorization

Nice.  The speed on Alpha is pretty impressive.  I wonder what their infrastructure is.

Not OS X specific unfortunately, but we had some students doing factorization on GPUs a year or so ago that was running on our nVidia cluster but I don't know the specifics other than they reported 1000 fold increases in throughput.


On Oct 12, 2011, at 6:35 AM, Aaron Golden wrote:

I wouldn't have thought that Mathematica could handle it, but I was surprised to see that Wolfram Alpha will do a few of these:

10^100 + 1:^100+++1
10^100 + 5:^100+++5
10^100 + 7:^100+++7
10^100 + 9:^100+++9
10^100 + 10:^100+++10
10^100 + 12:^100+++12

so maybe that indicates that the very latest and greatest Mathematica can do it.  (I haven't updated Mathematica since version 6.)  Or this could just mean that Mathematica can handle the problem when it has access to a large number of computers on which to parallelize, but not necessarily on any single Mac.

-- Aaron

On Wed, Oct 12, 2011 at 5:13 AM, Bryan Jones <email@hidden> wrote:

    Hey Richard,

    Dumb question, but have you tried Mathematica?  I remember doing factorization there quite some time ago, but I don't have any benchmark experience with it.

    There was also Sage.


On Oct 12, 2011, at 5:51 AM, Richard Crandall wrote:

    > Dear Scitech Colleagues,
    > I am looking for a factorization tool to run on OS X,
    > which can provide the complete factorization
    > of any 100-digit number in under an hour, say.
    > The test will be to factor the first 100 integers
    > exceeding a googol.  That is, to completely factorize
    > 10^100+1,
    > 10^100+2,
    > 10^100+3,
    > ... ,
    > 10^100 + 100.
    > Respectfully,
    > Richard Crandall
    > Advanced Computation Group
    > _______________________________________________
    > Do not post admin requests to the list. They will be ignored.
    > Scitech mailing list      (email@hidden)
    > Help/Unsubscribe/Update your Subscription:
    > This email sent to email@hidden

    Bryan William Jones, Ph.D.
    Moran Eye Center
    65 Mario Capecchi Dr., Rm S3872
    Salt Lake City, Utah 84132
    iChat/AIM address:  email@hidden

Do not post admin requests to the list. They will be ignored.
Scitech mailing list      (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden

Visit the Apple Store online or at retail locations.

Contact Apple | Terms of Use | Privacy Policy

Copyright © 2011 Apple Inc. All rights reserved.