2

Cryptography and Network Security Page 126 on this book

enter image description here

\documentclass[usenames,dvipsnames]{beamer}
\usepackage{colortbl}
\usepackage{dcolumn}
\usefonttheme[onlymath]{serif}
\usepackage{amsmath}
\usepackage{array,multirow,booktabs,fourier,polynom}
\usepackage[justification=centering]{caption}
\usetheme{Madrid}
\newcolumntype{2}{D{.}{}{2.0}}
\begin{document}

  \begin{frame}
  \frametitle{Polynomial Arithmetic over $GF(2)$}
\polylongdiv{x^3+x+1}{x+1}
  \end{frame}
 \end{document}

enter image description here

Can I make the division shown in the book using \polylongdiv? I know that it can be achieved using array, but \polylongdiv is very simple.

  • Can you clarify the question please? It looks as though you would like to do polynomial long division using the \polylongdiv command but with coefficients mod 2. Is this right? – Loop Space Aug 6 '18 at 14:16
  • @LoopSpace Yes and in the book they not shown the -(minus) sign when subtract to find out the remainder.(x^3+x^2) instead of (-x^3-x^2) – alhelal Aug 6 '18 at 14:22
  • it comes up every few months the slightly weird negated layout used by that package, It's not exactly trivial to change it (I looked once) as the display layout and the arithmetic logic are somewhat interlinked. – David Carlisle Aug 6 '18 at 14:29
  • 1
    Uh, the book is wrong. Are you asking how to get \polylongdiv to make mistakes? – John Kormylo Aug 6 '18 at 21:38
  • @JohnKormylo As my teacher teaches this book, I can't tell that this book is wrong without any reference. Do you have any reference that the book is wrong? Mentioned that the book uses x-or in addition and subtraction. – alhelal Aug 7 '18 at 0:26
2

A little while back I had a go at reimplementing polynomial long division as what I wanted wasn't easily available via the polynom package. I've just had a go at putting in modular arithmetic and the first attempt seems to work with some caveats - the main one being that I haven't implemented modular division, so providing your steps don't involve figuring out the multiplicative inverse of an integer modulo a base, then you should be fine.

Sample code:

\documentclass{article}
%\url{https://tex.stackexchange.com/q/444837/86}
\usepackage{polydiv}

\begin{document}

\PolySet{p}{1,0,1,1}
\PolySet{q}{1,1}

\[
  \PolyLongDiv[base=2]{p}{q}
  \]

\end{document}

Result:

Modular polynomial division

(The pink background is a "feature" of the screenshot program.)

Code is on github.

  • 1
    This is truly wonderful! An observation for other users: if the leading term of q is a (mod your prime), then it has an inverse mod your prime (call it a^{-1}). Now p = gq + r implies p = (ag)(a^{-1}q) + r, so the intrepid user can work out the (original) quotient (ag) and remainder (r) from your code. – Courtney Gibbons Mar 4 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.