Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)

Replies: 11   Last Post: Jan 8, 2013 1:37 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
JT

Posts: 1,041
Registered: 4/7/12
Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)

Posted: Jan 4, 2013 8:55 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.


Date Subject Author
1/4/13
Read Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have
any restrictions upon size of (S number of possibilities)
David Bernier
1/4/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have
any restrictions upon size of (S number of possibilities)
David Bernier
1/4/13
Read Re: Another count sort that certainly must exist, it do not have
any restrictions upon size of (S number of possibilities)
David Bernier
1/4/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT
1/4/13
Read Re: Another count sort that certainly must exist, it do not have
any restrictions upon size of (S number of possibilities)
David Bernier
1/8/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
kiru.sengal@gmail.com
1/8/13
Read Re: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
JT

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.