Re: Probabalistic algorithms.

From: J French (erewhon_at_nowhere.com)
Date: 11/20/03 

Date: Thu, 20 Nov 2003 22:48:35 +0000 (UTC)

Apologies to others, but this is a bookmark
- any suggestions for less obstructive methods for keeping links until
sober ... are welcome ... tomorrow awaits

On Thu, 20 Nov 2003 14:35:17 +0000, "Martin Harvey (Demon Account)"
<martin@pergolesi.demon.co.uk> wrote:

>On Wed, 19 Nov 2003 12:07:13 +0000 (UTC), erewhon@nowhere.com (J
>French) wrote:
>
>>Coding should not leave things to chance
>>
>>IMO, 'transformations' are fine, but 'hashing' is strictly for
>>undergraduates.
>
>ROFLMAO!
>
>Nothing personal Mr French, because I know how knowledgeable you are,
>and how much you've helped other people in this N.G with your
>extensive experience, but I *have* to disagree here.
>
>However, I'm only going to cover hashing lightly, because there's a
>*really* cool algorithm that is *vital* to most of the computing world
>that has chance as a crucial element. As you'll see, in some cases,
>it's absolutely vital that things are left to chance, so that some
>statistical properties hold.
>
>Hashing is typically just an optimisation. Taking data indexing and
>lookyp, the point of a hash is that you don't have the time or the
>energy to maintain a balanced tree, or it's simply not necessary, and
>all you need to do is decrease the cost of lookup by a large constant
>factor. In such cases, all the hash does is guarantee that given some
>data to hash, most of the hash values will be unique. In terms of
>program correctness, It doesn't matter if there's a hash collision or
>not - things just run faster if there are fewer collisions.
>
>Anyways, let's put hashing to one side, and consider a *really*
>important probabilistic algorithm where *chance* is in fact a vital
>part of what it does:
>
>What immediately sprung to mind was "Miller-Rabin", primality testing.
>
>Basically for public key cryptography, part of generating is keypair
>is finding two really marge prime numbers, and then multiplying them.
>The security of the cryptography resides in the fact that it's damn
>hard to factor the composite into its two prime factors.
>
>Now the problem is that if you want to generate a composite that's
>going to take longer than the age of the universe to factor, you haqve
>to find two really big primes, and although the composite is going to
>be much harder to factor than the primes, it's not exactly going to be
>a piece of cake to determine that the primes are in fact prime in the
>first place.
>
>So instead of proving your two multiplies prime beyond doubt, you
>cheat. You determine that they are 99.99999999999999% likely or better
>to be prime.
>
>Unlike hashing, the probabilistic nature of these algorithms is
>*crucial*. In order to generate large enough primes without making the
>factoring problem of the composite too easy, you *have* to use an
>algorithm that's dfaster than brute force factorisation, and when you
>have such an algorithm, you need to be darn sure that the
>probabilistic guarantees it gives are correct.
>
>I might mention that there are several way of soing these things: you
>can use a specific primality testing algorithm to show that it is
>probably prime, or alternatively, a probabilistic factorsiation
>algorithm to show that it isn't.
>
>see these web pages for details:
>
>http://www.rsasecurity.com/rsalabs/faq/2-5-1.html
>http://members.tripod.com/irish_ronan/rsa/factorization.html
>http://mathworld.wolfram.com/PrimalityTest.html
>
>
>MH.

Relevant Pages

  • Probabalistic algorithms.
    ... *really* cool algorithm that is *vital* to most of the computing world ... Hashing is typically just an optimisation. ... all the hash does is guarantee that given some ... Now the problem is that if you want to generate a composite that's ...
    (comp.lang.pascal.delphi.misc)
  • Re: to sig or not to sig?
    ... >> this block which will make the whole file generate the same hash as ... > hashing 2^m random messages. ... Finding two random messages that hashe to ... I guess what I wanted to know here was whether the md5 algorithm had been ...
    (comp.os.linux.misc)
  • Hopscotch Hashing
    ... With all the talk about concurrent wait-free hashing algorithms, ... Hopscotch Hashing: a Hash Map for the Multicore Era ... We present a new resizable hash table algorithm directed at multicore ...
    (comp.programming.threads)
  • Re: urgnet need for complete C# code for Password encryption/decryption
    ... I agree - hashing is becoming nearly a standard. ... Dejan Sarka, SQL Server MVP ... A hash algorithm ... > encryption algorithm is a two-way function. ...
    (microsoft.public.sqlserver.security)
  • Re: "index" efficiency... any help or ideas?
    ... no general purpose hashing method, no matter how good, is good enough ... to prevent the possibility that everything hash into the same place. ... > Downside of hashes; if the data is stored externally, ... > perfect hashing are techniques that require analysis of the data in advance, ...
    (alt.lang.asm)
Loading