Cryptography and Network Security Page 126 on this book

enter image description here


  \frametitle{Polynomial Arithmetic over $GF(2)$}

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? Aug 6, 2018 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, 2018 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. Aug 6, 2018 at 14:29
  • 1
    Uh, the book is wrong. Are you asking how to get \polylongdiv to make mistakes? Aug 6, 2018 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, 2018 at 0:26

1 Answer 1


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:







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. Mar 4, 2019 at 23:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .