On 01/04/2013 12:07 PM, David Bernier wrote: > On 01/04/2013 10:46 AM, JT wrote: >> On 4 Jan, 15:46, JT<jonas.thornv...@gmail.com> wrote: >>> I remember doing this in a tentamen during my education in information >>> theory beleiving what i did was binary sort but my teacher informed me >>> it wasn't so what is it. [...]
>> heap, what is the difference betwee a heap and a tree?). >> >> So what you think about the mix using this kind of sort for counting >> in values, and then quicksort to sort the none null tree nodes by >> sizes. > > Oops.. below is about factoring. The best algorithms > have been getting better since Maurice Kraitchik's [1920s] > improvement on Fermat's method of expressing a number > as a difference of squares, n = a^2 - b^2, so > n = (a-b) (a+b). > > > There's a very good article called "A Tale of Two Sieves" > by Carl Pomerance: Notices of the AMS, vol. 43, no. 12, > December 1996: > < http://www.ams.org/notices/199612/index.html > > > The 9th Fermat number F_9 = 2^(512)+1 had been factored > around 1990 by the Lenstras et al using the Number Field > sieve (which had supplanted the quadratic sieve). > > The Quadratic sieve is easier to understand than the > Number Field Sieve, which I don't understand. > > F_10 and F_11 were fully factored then, using the elliptic > curve method (which can find smallish prime factors). > > F_12 was listed as not completely factored, with > F_12 being a product of 5 distinct odd primes and > the 1187-digit composite: > > C_1187 = > 22964766349327374158394934836882729742175302138572\ [...]
> 66912966168394403107609922082657201649660373439896\ > 3042158832323677881589363722322001921. > > At 3942 bits for C_1187 above, what's the > probability density function of expected time > till C_1187 is fully factored?
For the Fermat number F_12 = 2^(2^12) + 1 or 2^4096 +1 , another prime factor was found around 2010. So, this new prime factor would be a divisor of C_1187, a 1187-digit number. F_12 is listed as known to be "not completely factored".