# Polynomial long division using \polylongdiv

Cryptography and Network Security Page 126 on this book

\documentclass[usenames,dvipsnames]{beamer}
\usepackage{colortbl}
\usepackage{dcolumn}
\usefonttheme[onlymath]{serif}
\usepackage{amsmath}
\usepackage{array,multirow,booktabs,fourier,polynom}
\usepackage[justification=centering]{caption}
\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}


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
• 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

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:

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

Code is on github.

• 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