Re: Random mapping

On Thu, 19 Jun 2008 17:16:23 -0700, Greg Rose wrote:

On Jun 18, 9:16 am, gadolin <t...@xxxxxxxxxxx> wrote:
I would like to make security analysis of my algorithm by comparison it
to random mapping behaviour, do you know paper where similar analysis
is conducted in details, i did search.

K.

Chapter 2 of the Handbook of Applied Cryptography, available at
http://www.cacr.math.uwaterloo.ca/hac/ .
niku wybuchu zginął dowódca patrolu ppor. Robert Marczewski a czterech
innych, jadących tym samym samochodem Polaków, zostało rannych. Jak
podkreślił mjr Popławski, cała czwórka została przetransportowana do
szpitala wojskowego w Orgun, a życiu żołnierzy nie grozi
niebezpieczeństwo.
Greg.

Thanks for reply,
I read that have read the chapter you advised,
i started tests, where i count avg of number of cycles of different length
for random functional graph, and graph that comes from my alg. Number of
test is 10^6, and set is n = 128. I would like to confront my results, i
read that expected value of strongest component is for n-> inf,
c2*sqrt(n), in my case it is significantly greater then value gained in
tests 1.73746*11.31 = 19.5, while i get goes to infinity, while in test on
avg it is: 8.95634.

I know that's equation for n->inf, but still I am worried. I tried to
check the expected value of strongest component for n =128, but can't get
it.
I have read "Random Mapping Statistics - Flajolet, Odlyzko", but it is
quit complicated for me.
Could you please help me, are there some tables containing calculated avg
values for random mapping for particular sizes.

below i add avg values of cycles of different length(cycle size, random
mapping, my alg)

1 0.999605 0.999921
2 0.496328 0.496354
3 0.325465 0.325305
4 0.238283 0.239442
5 0.184611 0.18444
6 0.147905 0.147819
7 0.120842 0.120841
8 0.100148 0.0998307
9 0.0833737 0.0832222
10 0.0697589 0.0696981


K.

.

Quantcast