Jeff Burdges
Reputation
257
Top tag
Next privilege 350 Rep.
Access review queues
 Dec2 comment How do we find the last two correspondences in an otherwise known even permutation? Create an object Pmod with two variables a and b such that Pmod(a) = n-1, Pmod(b) = n-2, and Pmod(j) = P(j) otherwise. For i=0..n-3, if done[i]==0 then : Initialize j=i. Loop setting done[j]=1 and j=Pmod(j)$until done[j]==1. If j==n-1, set a=i. If j==n-2, set b=i. You compute the answer using the final values of a and b. Dec2 comment How do we find the last two correspondences in an otherwise known even permutation? In that case, my second linear time algorithm requires an$n$bit array plus a few$O(log(n))$bit counters and integers. Dec2 comment How do we find the last two correspondences in an otherwise known even permutation? If your going for n bits plus O(1), then : Iterate thorough the entries exhausting each elements cycle as far as possible to gradually build out the cycle(s) that end in$n-2$and$n-1$. You use the n bit array to prevent reprocessing cycles. Dec2 comment How do we find the last two correspondences in an otherwise known even permutation? Inverse : Initialize$inverse[i] = -1$for$i=1..n$. Set$inverse[P(i)] = i$for$i=1..n$. If$inverse[n-2] = -1$or$inverse[n-1] = -1$, then use parity to decide whether it's a fixed point or maps to$n-1$or$n-2\$, respectively. Dec2 answered How do we find the last two correspondences in an otherwise known even permutation? Nov28 asked Is there any serious discussion about using blinding intermediaries in digital currency scenarios? Nov26 comment How does the wider cryptographic community view non-abelian group based cryptography? There are cases where identifying a hidden subgroup has applications though. These results tell us that non-abelian finite simple groups cannot play the same role as prime numbers in cryptographic applications; hence my motivation for asking this question. Nov26 comment How does the wider cryptographic community view non-abelian group based cryptography? There is an industry of identifying finite groups both simple and non-simple using Monte Carlo methods, called black box group theory. Afaik, non-simple groups are treated using variations on the component analysis techniques from the CFSGs. Nov26 comment How does the wider cryptographic community view non-abelian group based cryptography? I'll verify further later but I believe the reference should be this article by Artin as well as its predecessor : onlinelibrary.wiley.com/doi/10.1002/cpa.3160080403/abstract Nov26 comment How does the wider cryptographic community view non-abelian group based cryptography? I'll track one down but it's the fact that all finite simple groups has distinct orders except for B_n(q) and C_n(q) with q odd and n>2, and A_3(2) and A_2(4), amusingly even wikipedia states it sans citation : en.wikipedia.org/wiki/List_of_finite_simple_groups Nov25 awarded Teacher Nov25 awarded Supporter Nov25 answered What exactly is the impact of the hidden subgroup problem on cryptography? Nov25 comment How does the wider cryptographic community view non-abelian group based cryptography? Interesting thank! I'd naively assume any implementation would use only a bounded fragment of the infinite object for computational reasons, which avoids that side channel attack. You wouldn't be creating a finite group by imposing this bound, but maybe the CFSG still worms it's way into the picture somehow. Nov25 awarded Student Nov25 asked How does the wider cryptographic community view non-abelian group based cryptography?