Re: Random array

Stephen P. Gibbons (steve@aztech.net)
Thu, 29 Oct 1998 21:17:38 -0700

• Next message: Alex Alten: "Re: Shuffling"
• Previous message: Jim Gillogly: "Re: Random array"

As an amateur cryptographer, I was looking at as similar system a while
back (for a scheme that I eventually decided wasn't worth publishing.)

The easy/quick way to avoid sorting munges is to use "random" n-bit
(where n is probably a multiple of 32) ints on the index, and to fill the
lower x-bits (where x is log2 of the number of elements in the array)
of the index with sequential numbers. This should be functionally
equivalent to your suggestion, but hopefully more efficient.

Ultimately, I gave up on my crypto scheme as probably being too
inefficient for today's needs, even though I thought it would have certain
(maybe/probably) provable properties. Also, I keep stumbling across
previous works with remarkable similarities, and I oftentimes think that
I've reinvented the wheel. (Which I don't necessarily see as being a bad
thing), I just wish I'd read more (and I thought that I'd read a lot!) before
donning the inventor's cap. I chalk it up to an experience in "thinking about
cryptography."

--
Steve
Jim Gillogly wrote:
> On Thu, 29 Oct 1998, Greg Rose wrote:
> > [A]nother, theoretically interesting, way to
> > randomise is to take a sorting algorithm and make random binary choices
> > everywhere it would compare two elements and swap them if out of order.
>
> "David R. Conrad" <drc@adni.net> responded:
> > The only caveat here is to make sure that this doesn't mung the operation
> > of the sort.
>
> One could modify Greg's suggestion slightly by attaching an auxiliary
> array of 256 random numbers to each of the members of the original
> array and then using the most efficient handy sort algorithm to sort
> those random numbers, dragging along their associated original array
> elements.  This way it doesn't have a chance to interfere with the
> operation of the sorting algorithm, at the cost of an extra array.
>
> --
>         Jim Gillogly
>         Trewesday, 9 Blotmath S.R. 1998, 04:00
>         12.19.5.11.11, 9 Chuen 4 Zac, Sixth Lord of Night

• Next message: Alex Alten: "Re: Shuffling"
• Previous message: Jim Gillogly: "Re: Random array"