![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
A little multiplication exercise
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]
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]
no subject
777777777777777777777777777777777777777777777! Ain't bc wonderful?
no subject
So I think the more interesting question, to me, is: how did you find out in the first place that 5 × 10180 + 7/9 × (10180-1) was the product of sufficiently few sufficiently large primes to be worth factoring?
no subject
1. Check for primality
2. Google
3. Factorise
no subject
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.
no subject
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 ...
no subject