User stephan müller - MathOverflow

Answer by Stephan Müller for cryptographic primitive process

2013-04-04T18:43:12Z

Hi,

from any blockcipher (for example as Threefish as mentioned by Gro-Tsen) you can build various other primitives. This is heavily related to their mode of operation. You can find basic pointers in wikipedia's article on block ciphers.But usually one uses dedicated algorithms for different problems like encryption, hashes, etc..

However there are other much more general approaches, for example many primitives can be seen as instances of sponge constructions. But it is hard to guess what you are looking for.

Also 'cryptographic primitive' is more an idea rather than a fixed notion. It is distinguishes 'cryptographic algorithms' from 'cryptographic schemes'. There is a beautiful paper from U.Maurer: Constructive cryptography about 'pasting' primitives.

All this said, it seems to be a question for crypto.stackexchange. Also you should provide more background in what (and why) your are interested.

Answer by Stephan Müller for Vertical and Horizontal Isomorphisms in 2-categories

2013-01-16T19:10:20Z

I assume your are talking about a symmetric strict monoidial category $\mathcal{M}$. I think, you have to choose, beside $\bar{A}$, an isomorphism $\iota_A: A \otimes \bar{A} \to I$, say. I think $\iota_A = \mathrm{id}$ for all $A$ is not possible.

For any $f: X \to Y$ and $g:Y \to X$ follows, with your definition of $\bar{\square}$ and the interchange law:

$\bar{f} \circ \bar{g} := (\bar{X} \otimes f \otimes \bar{Y}) \circ (\bar{X} \otimes g \otimes \bar{Y}) = \bar{X} \otimes f \circ g \otimes \bar{Y}: \bar{X} \otimes X \otimes \bar{Y} \to \bar{X} \otimes Y \otimes \bar{Y}$

(By the symmetry, both of your definitons of $\bar{\square}$ 'agree', that is they fit in suitable commutative diagram. However for composing bars you need to insert the symmetry isomorphism $\gamma: A\otimes B \otimes C \mapsto C \otimes B \otimes A$ in suitable places, like this $ \bar{f}:= \gamma \circ (\bar{X} \otimes f \otimes \bar{Y}): \bar{X} \otimes X \otimes \bar{Y} \to \bar{Y} \otimes X\otimes \bar{X}$.)

That is, $f$ and $g$ are inverse then $\bar{f}$ and $\bar{g}$ are inverse to each other. Well, of course, this is nothing the compatability laws in your monoidial category.

As you suggested, define $\hat{f}:= \rho_{\bar{X}} \circ (\bar{X} \otimes \iota_Y)\circ (\bar{X} \otimes f \otimes \bar{Y}) \circ (\iota_{\bar{X}} \otimes \bar{Y})^{-1} \circ \lambda_{\bar{Y}}^{-1}: \bar{Y} \to \bar{X}$

Where $\lambda_Y:I \otimes Y \to Y$ and $\rho_X: X \otimes I \to X$ are the designed natural isomorphims.

Exploiting the compatablity laws, this gives you $\hat{g} \circ \hat{f} = \mathrm{id}_X$ for $g:= f^{-1}$. Thus you obtain one implication.

I see, in the meantime Todd Trimble gave an answer which completly subsume mine. However as it took me some time to type it, i post it as a 'down to earth' version.

Edit: I wonder if you obtain an endofunctor $\mathcal{M}^{op} \to \mathcal{M}$ via $X \mapsto \bar{X}$ and $f \mapsto \hat{f}$.

Well, probably you need some conditions like $\bar{\bar{X}} = X$ and $\iota_{\bar{X}} = {\iota_X}^{-1}$. I will think about. This may be also related to other direction.

Answer by Stephan Müller for Elementary applications of linear algebra over finite fields

2013-01-14T19:26:56Z

I suggest Linear Feedback Shift Register (LFSR) as an easy example. They can be used as pseudo random number generators and have a wide practical use in communication and cryptography, GPS, GSM, CRC, WIFI, .. (non-math) applications which are usually accepted as usefull.

Usually they work over $\mathbb{F}_2$, but other fields are possible. Basically you have to work with polynomials (including long division) over $\mathbb{F}_2$. The need for primitive polynomials may motivate some more advanced considerations. A brief summary for mathematicians is Nayuki's blog.

I would explicitly pick the CRC algorithm. A description is located for example in this lecture(pdf) from D.Culler. This also relates to linear codes, which is also a good idea.

More easy is an application as fancy counter. If you ever wondered how the shuffle mode of your media player works.

Answer by Stephan Müller for Origin of notion of "split Grothendieck group"?

2013-01-07T15:12:15Z

These groups are mentioned in [Swan '68 - Algebraic K-Theory, p.69]. He constructs $K_0(\mathcal{A}, S)$ for a class $S$ of exact sequences in $\mathcal{A}$. Take the free abelian group mod the relations from sequences in $S$. For example the class of all exact sequences for the Grothendieck-group $K_0(\mathcal{A})$ or all exact split seqences for the group you mentioned. The name 'split-Grothendieck-group' does not appear.

He generalizes further to $K_0(\mathcal{A}, F)$ for a bifunctor $F:\mathcal{A} \times \mathcal{A} \to \mathcal{A}$ and obtains a generalized Picard-group.

Comment by Stephan Müller

2013-02-18T15:13:36Z

I guess the question is a bit vague. Is Diff(M) the subsheaf of C(M) of smooth functions on M? Clearly, if Diff(M) has non-trivial idempotents, so has C(M). Are you asking for the converse?

Comment by Stephan Müller

2013-02-07T18:54:44Z

Maybe they had the christian 'alpha & omega' in mind. And the characteristic functions, as well as the true arrow end in omega.

Comment by Stephan Müller

2013-02-05T10:44:55Z

Thanks, your are right. Somehow I missed that. I am not sure if the OP has such answers in mind, but here [ maths.manchester.ac.uk/~mkambites/events/bmc2008/… ](pdf) is a survey of 'not-so-bad/good' presentations and their word problems.

Comment by Stephan Müller

2013-02-03T18:23:41Z

wccanard, thanks for pointing this out. I didn't know. Your are probably talking about the 'word problem for groups' ( en.wikipedia.org/wiki/Word_problem_for_groups ). That is given an element in terms of generators, decide whether it is the trivial element. Correct me if i am wrong. Jacks questions is slightly different and asks for the existence of a non-trivial element. This may be much easier. And also the above problem is decidable for many groups and only undecidable 'in worst case'. So it really depends the monoid in consideration.

Comment by Stephan Müller

2013-01-25T11:33:08Z

A necessary condition for punctured category to be balanced is "every mono is the kernel of some morphism" or dually "every epi is the cokernel of some morphism". In view of this, existence of counterexamples seems much more plausible than if one thinks of an 'almost abelian' setting. ---- And the map n:Z->Z form Eric Wofseys example is not the cokernel of something.

Comment by Stephan Müller

2013-01-18T18:20:01Z

That could be math.stackexchange.com but there are many other as well

Comment by Stephan Müller

2013-01-15T14:24:39Z

This is similar to the card game SET!, see mathoverflow.net/questions/13638/…

Comment by Stephan Müller

2013-01-15T11:28:23Z

The Lemma is very nice. Thanks for the pointer. But how do you manage to find an easy (directed and weighted) graph representing a given matrix? I know you don't claimed this to be feasible but are some considerations? I can imagine there is a generic algorithm which allows to "rediscover" Leibniz' formula.

Comment by Stephan Müller

2013-01-09T11:56:00Z

I think this scheme is not widespread because of patent issues. It is similar to DSA which is frequently used. Maybe it is used for some smartcards because of its better performance. It's probably the best to ask again on crypto.stackexchange.com