Date: Jan 4, 2013 8:39 PM
Author: David Bernier
Subject: Re: Another count sort that certainly must exist, it do not have<br> any restrictions upon size of (S number of possibilities)
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
> 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 =
> 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".
The relevant line on the Web-page referenced below contains
the text: "M. Vang, Zimmermann & Kruppa" in the "Discoverer"
< http://www.prothsearch.net/fermat.html#Complete >
Also, lower down in the page,
"50 digit k = 17353230210429594579133099699123162989482444520899"
This does relate to a factor of F_12 by PARI/gp.
Then, by my calcultions, the residual unfactored part
of F_12 has 1133 decimal digits and is a composite number.
> Or, centiles: e.g. 50% chance fully factored
> within <= 10 years. 95% chance fully factored within
> <= 95 years, etc. ...
Maybe 50% to 50% chances for "fully factored by 2100 " ?
(or 2060, or 2200 etc. ... )