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 http://www.sci.utah.edu/nvidia-coe.html but I don't know the specifics other than they reported 1000 fold increases in throughput.


Bryan
http://prometheus.med.utah.edu/~bwjones/



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: http://www.wolframalpha.com/input/?i=prime+factors+of+10^100+++1
10^100 + 5: http://www.wolframalpha.com/input/?i=prime+factors+of+10^100+++5
10^100 + 7: http://www.wolframalpha.com/input/?i=prime+factors+of+10^100+++7
10^100 + 9: http://www.wolframalpha.com/input/?i=prime+factors+of+10^100+++9
10^100 + 10: http://www.wolframalpha.com/input/?i=prime+factors+of+10^100+++10
10^100 + 12: http://www.wolframalpha.com/input/?i=prime+factors+of+10^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?  http://www.wolfram.com/  I remember doing factorization there quite some time ago, but I don't have any benchmark experience with it.

    There was also Sage.  http://www.sagemath.org/


    Bryan
    http://prometheus.med.utah.edu/~bwjones/


    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.
    email@hidden
    Moran Eye Center
    65 Mario Capecchi Dr., Rm S3872
    Salt Lake City, Utah 84132
    http://prometheus.med.utah.edu/~marclab/
    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.

1-800-MY-APPLE


Contact Apple | Terms of Use | Privacy Policy


Copyright © 2011 Apple Inc. All rights reserved.