257 reputation
16
bio website
location http://www.maths.manchester.ac.uk/~burdges/
age 38
visits member for 3 years, 1 month
seen Mar 4 at 13:40

Dec
2
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.
Dec
2
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.
Dec
2
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.
Dec
2
answered How do we find the last two correspondences in an otherwise known even permutation?
Nov
28
asked Is there any serious discussion about using blinding intermediaries in digital currency scenarios?
Nov
26
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.
Nov
26
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.
Nov
26
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
Nov
26
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
Nov
25
awarded  Teacher
Nov
25
awarded  Supporter
Nov
25
answered What exactly is the impact of the hidden subgroup problem on cryptography?
Nov
25
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.
Nov
25
awarded  Student
Nov
25
asked How does the wider cryptographic community view non-abelian group based cryptography?