A little multiplication exercise

[fivemack]

Why not multiply out

1907145664709063958354268537876114943171 * 2282249079063136761889376337454791894323802478621 * 1327437030532454031084789475205826920108788207304808616927065055833914814194080582426819377847


[the hardware and software state of the art is such that factoring 130-digit general numbers, or 180-digit numbers of sufficiently special shape, takes about a week on a 2007-vintage desktop computer using free software; there are various bits of the software you can tweak which I suspect can get that down to four or five days]

Comments

[randwolf.livejournal.com]

5777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777
777777777777777777777777777777777777777777777! Ain't bc wonderful?

[simont]

I presume those three factors are prime, on the grounds that it wouldn't be interesting if they were just products of a whole bunch of smaller prime factors?

So I think the more interesting question, to me, is: how did you find out in the first place that 5 × 10¹⁸⁰ + 7/9 × (10¹⁸⁰-1) was the product of sufficiently few sufficiently large primes to be worth factoring?

[fivemack.livejournal.com]

There's a program gmp-ecm (Debian package gmp-ecm) which uses a wonderful magic trick called the Elliptic Curve Method.

Basically, if you have a prime number p, there are a large number of algebraic groups (IE groups whose elements can be represented as a triplet of numbers mod-p and whose group operations are rational functions of the entries in the triplet) which are the elliptic curves.

The orders of these elliptic curves are between p-2*sqrt(p) and p+2*sqrt(p), and are distributed pretty much uniformly in that range. This means you've got a reasonable chance that, given a random elliptic curve, its order has only small prime factors.

And arithmetic modulo a composite number N is roughly equivalent to arithmetic modulo its prime factors, except if you try to divide by a number which is 0 modulo a prime factor, in which case the division routine fails in a way that tells you the factor.

So, you take a random elliptic curve modulo N, take a point on it (it's trivial to find one), and compute P*2*3*5*7*11*13*17*19* ... * 9999991. This will make the division routine fail, giving you a factor p of N, if the order of the point on the reduction of the elliptic curve modulo p had only factors smaller than 10^7; if it doesn't fail, pick another elliptic curve and try again. On my current desktop it takes 90 seconds to do this for a 150-digit N.

So, you run for 24 hours. At this point, either you have a complete decomposition of N into factors (obviously when you find one factor you divide it out, check that the cofactor is prime, and carry on with the cofactor if it isn't), or, by a slightly fiddly argument involving rather more analytic number theory than I can handle to get a prior distribution and P(factor of M digits found | such a factor exists) followed by Bayes' theorem, you have pretty good confidence that there are no factors of N less than about forty digits.

At this point it becomes worth running the number field sieve, which takes time proportional to the size of N rather than to the size of its smallest factor, but is guaranteeed to succeed.

Why did I pick 577777...777? There's a Japanese man called Mr Kamada who collects factors of such numbers and has a list of ones he'd particularly like to know; also such numbers are much easier to factorise than random numbers of that size because they can be written as simple polynomials in a smaller number, and this makes it possible to use the special number field sieve. For which see Wikipedia; I wrote about a third of the article there.

[fivemack.livejournal.com]

'proportional to' should be 'dependent on' when talking about the number field sieve; the general NFS takes about 24 hours for 110-digit numbers, 60 hours for 120-digit numbers, and 200-300 hours for 130-digit numbers on my hardware, the special NFS takes about 40 hours for 160 digits and 200 hours for 180 digits. I am too impatient to have done a 140-digit general number or a 200-digit special number yet.

[cartesiandaemon.livejournal.com]

Reading this suggests a new factorisation optimisation to me

1. Check for primality
2. Google
3. Factorise

[fivemack.livejournal.com]

Unfortunately, it only works the other way round.

I have several times spent a day coding and set a computer running for a week to find the smallest number with some interesting property, then googled for that number and found the Web page by the person who had found it earlier ...