Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Can someone explain how to find inverses in truncated polynomial rings manually (i.e. on pen and paper)? As an example from the tutorial:

Example. Take $N=7$, $q=11$, $a=3+2X^2-3X^4+X^6$. The inverse of $a \bmod 11$ is $a^{-1}=-2+4X+2X^2+4X^3-4X^4+2X^5-2X^6$, since

$(3+2X^2-3X^4+X^6)*(-2+4^X+2X^2+4X^3-4X^4+2X^5-2X^6) \equiv -10+22X+22X^3-22X^6 \equiv 1 \mod 11$.

How to find $a^{-1} = -2+4X+2X^2+4X^3-4X^4+2X^5-2X^6$, manually, not using the pseudocode?

share|improve this question
2  
I don't get your "not pseudo-code". To do it manually, you should execute the pseudo-code manually. –  CodesInChaos Mar 11 '13 at 10:13
    
I want to know all step of the process, so i can solve it with handwriting, if its posible –  Sunia Raharja Mar 11 '13 at 10:22
2  
To be honest, there is typically a fair amount of work required to do this by hand even for such a small example. It requires long division of polynomials as you are basically doing the extended euclidean algorithm, then substituting back up until you get something of the form $p_1a+p_2b=1$ where $p_1,p_2$ are polynomials and $b=x^7-1$. Since $x^7-1\equiv 0$ in your ring, you have $p_1a=1$ so $a^{-1}=p_1$. Not sure if someone here will be willing to work everything out by hand. We'll see. Just being realistic though. –  mikeazo Mar 11 '13 at 13:02
1  
A fairly simple algorithm (extended euclidean algorithm) tells you exactly what you need to do to solve the problem. To better understand the algorithm, start with simple integers as in this question –  mikeazo Mar 11 '13 at 13:11
1  
Basically, using Extended Euclidean, do the inverse computation of $a$ in $\mathbb{Z}[X]$, doing the gcd with $X^7 - 1$, and reduce the coefficients modulo 11 afterwards. –  Henno Brandsma Mar 11 '13 at 21:39
show 8 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.