[RC5] More on Quantum Computing and Crypto

Jon Loeliger jdl at jdl.com
Fri May 21 15:02:56 EDT 1999


So, like Greg Hewgill was saying to me just the other day:
>
> I'm not sure this is a perfect analogy. Consider the following small fragment
> of your conceptual spider web (please excuse the ascii art):
> 
>   A      B       C      D
>    ------+-------+------
>          |       |
>          +-------+
> 
> That is, a taut connection between ABCD with a loop of web dangling from B and
> C. While there is a wasy for this to break (at the short path between B and C)
> to produce the longest connecting path, this will not be the case in general.
> All other things being equal, there is a probability 1/3 that the short BC
> connection will break first, rather than AB or CD. Of course, if AB or CD
> breaks, then this web fragment becomes disconnected and is disqualified.
> 
> I think that at best, you could come up with a probability that the last
> connected path is really the longest path.


Those interested in this problem might consider reading up
on Tarjan's "Min-cut-max-flow" algorithms as well.  This is
a _similar_ problem, but it looks reducible.  But I confess
I've only been paying half-attention to this thread....

_Data_Structures_and_Network_Algorithms_, Robert Endre Tarjan, 1983

jdl
--------------------------------------------------------------------
Jon Loeliger		| I remember the letter wrinkled in my hand,
Loeliger Consulting	| "I'll love you always" filled my eyes.
jdl at jdl.com		|				Berlin

--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list