User stephan m&#252;ller - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T18:01:34Z http://mathoverflow.net/feeds/user/28011 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119735/cryptographic-primitive-process/126545#126545 Answer by Stephan Müller for cryptographic primitive process Stephan Müller 2013-04-04T18:43:12Z 2013-04-04T18:43:12Z <p>Hi, </p> <p>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 <a href="http://en.wikipedia.org/wiki/Block_cipher#Relation_to_other_cryptographic_primitives" rel="nofollow">wikipedia's article on block ciphers</a>.But usually one uses dedicated algorithms for different problems like encryption, hashes, etc..</p> <p>However there are other much more general approaches, for example many primitives can be seen as instances of <a href="http://en.wikipedia.org/wiki/Sponge_function" rel="nofollow">sponge constructions</a>. But it is hard to guess what you are looking for. </p> <p>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: <a href="http://www.crypto.ethz.ch/publications/abstract.html?label=Maurer11" rel="nofollow">Constructive cryptography</a> about 'pasting' primitives.</p> <p>All this said, it seems to be a question for <a href="http://crypto.stackexchange.com/" rel="nofollow">crypto.stackexchange</a>. Also you should provide more background in what (and why) your are interested.</p> http://mathoverflow.net/questions/119084/vertical-and-horizontal-isomorphisms-in-2-categories/119104#119104 Answer by Stephan Müller for Vertical and Horizontal Isomorphisms in 2-categories Stephan Müller 2013-01-16T19:10:20Z 2013-01-17T10:14:34Z <p>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.</p> <p>For any $f: X \to Y$ and $g:Y \to X$ follows, with your definition of $\bar{\square}$ and the interchange law:</p> <p>$\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}$</p> <p>(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}$.)</p> <p>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.</p> <p>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}$</p> <p>Where $\lambda_Y:I \otimes Y \to Y$ and $\rho_X: X \otimes I \to X$ are the designed natural isomorphims.</p> <p>Exploiting the compatablity laws, this gives you $\hat{g} \circ \hat{f} = \mathrm{id}_X$ for $g:= f^{-1}$. Thus you obtain one implication.</p> <p>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.</p> <p>Edit: I wonder if you obtain an endofunctor $\mathcal{M}^{op} \to \mathcal{M}$ via $X \mapsto \bar{X}$ and $f \mapsto \hat{f}$.</p> <p>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.</p> http://mathoverflow.net/questions/118903/elementary-applications-of-linear-algebra-over-finite-fields/118914#118914 Answer by Stephan Müller for Elementary applications of linear algebra over finite fields Stephan Müller 2013-01-14T19:26:56Z 2013-01-14T19:26:56Z <p>I suggest <a href="http://en.wikipedia.org/wiki/Linear_feedback_shift_register" rel="nofollow">Linear Feedback Shift Register (LFSR)</a> 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.</p> <p>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 <a href="http://nayuki.eigenstate.org/page/galois-linear-feedback-shift-register" rel="nofollow">Nayuki's blog</a>.</p> <p>I would explicitly pick the CRC algorithm. A description is located for example in this <a href="http://www-inst.eecs.berkeley.edu/~cs150/fa04/Lecture/lec26.pdf" rel="nofollow">lecture(pdf)</a> from D.Culler. This also relates to linear codes, which is also a good idea.</p> <p>More easy is an application as fancy counter. If you ever wondered how the shuffle mode of your media player works.</p> http://mathoverflow.net/questions/118275/origin-of-notion-of-split-grothendieck-group/118285#118285 Answer by Stephan Müller for Origin of notion of "split Grothendieck group"? Stephan Müller 2013-01-07T15:12:15Z 2013-01-07T15:12:15Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/122175/diffm-and-connectedness Comment by Stephan Müller Stephan Müller 2013-02-18T15:13:36Z 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? http://mathoverflow.net/questions/121089/notation-for-the-subobject-classifier Comment by Stephan Müller Stephan Müller 2013-02-07T18:54:44Z 2013-02-07T18:54:44Z Maybe they had the christian 'alpha &amp; omega' in mind. And the characteristic functions, as well as the true arrow end in omega. http://mathoverflow.net/questions/120671/non-zero-monoid Comment by Stephan Müller Stephan Müller 2013-02-05T10:44:55Z 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 [ <a href="http://www.maths.manchester.ac.uk/~mkambites/events/bmc2008/kambites.pdf" rel="nofollow">maths.manchester.ac.uk/~mkambites/events/bmc2008/&hellip;</a> ](pdf) is a survey of 'not-so-bad/good' presentations and their word problems. http://mathoverflow.net/questions/120671/non-zero-monoid Comment by Stephan Müller Stephan Müller 2013-02-03T18:23:41Z 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. http://mathoverflow.net/questions/119821/is-an-additive-category-a-balanced-category Comment by Stephan Müller Stephan Müller 2013-01-25T11:33:08Z 2013-01-25T11:33:08Z A necessary condition for punctured category to be balanced is &quot;every mono is the kernel of some morphism&quot; or dually &quot;every epi is the cokernel of some morphism&quot;. 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-&gt;Z form Eric Wofseys example is not the cokernel of something. http://mathoverflow.net/questions/119282/np-problem-implications Comment by Stephan Müller Stephan Müller 2013-01-18T18:20:01Z 2013-01-18T18:20:01Z That could be <a href="http://math.stackexchange.com/" rel="nofollow">math.stackexchange.com</a> but there are many other as well http://mathoverflow.net/questions/118903/elementary-applications-of-linear-algebra-over-finite-fields/118929#118929 Comment by Stephan Müller Stephan Müller 2013-01-15T14:24:39Z 2013-01-15T14:24:39Z This is similar to the card game SET!, see <a href="http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13645#13645" rel="nofollow" title="which popular games are the most mathematical">mathoverflow.net/questions/13638/&hellip;</a> http://mathoverflow.net/questions/118789/proving-a-determinant-0/118823#118823 Comment by Stephan Müller Stephan Müller 2013-01-15T11:28:23Z 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 &quot;rediscover&quot; Leibniz' formula. http://mathoverflow.net/questions/118433/examples-of-applications-that-use-the-schnorr-digital-signature Comment by Stephan Müller Stephan Müller 2013-01-09T11:56:00Z 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 <a href="http://crypto.stackexchange.com/" rel="nofollow">crypto.stackexchange.com</a>