Date: Jan 4, 2013 9:53 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 08:55 PM, JT wrote:

> On 5 Jan, 02:39, David Bernier<david...@videotron.ca> wrote:

>> 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".

>>

>> The relevant line on the Web-page referenced below contains

>> the text: "M. Vang, Zimmermann& Kruppa" in the "Discoverer"

>> column:

>> <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. ... )

>>

>> dave

>

> Is reading out a binary tree from smallest to biggest in anyway

> related to TSP, i have slight memory of doing a algoritmic solution

> for TSP when i tried to factor RSA primeproducts, unfortunatly it is

> all gone from my mind. Could you please make a short layman approach

> for how TSP and sorting is related to factorization it may come back

> to my memory. I lack the key so to speech to the problem.

The key lies within the mind. The mind may appear to be a part

of reality, but in reality, all is mind ...

dave