Databases
StackOverflow2013
Postsdbo
PONTRU Pseudo-code for computing Polynomial Inverses
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PONTRU Pseudo-code for computing Polynomial Inverses
    primarykey
    data
    text
    <p>I was wondering if anyone could tell me how to implement line 45 of the following pseudo-code.</p> <pre><code>Require: the polynomial to invert a(x), N, and q. 1: k = 0 2: b = 1 3: c = 0 4: f = a 5: g = 0 {Steps 5-7 set g(x) = x^N - 1.} 6: g[0] = -1 7: g[N] = 1 8: loop 9: while f[0] = 0 do 10: for i = 1 to N do 11: f[i - 1] = f[i] {f(x) = f(x)/x} 12: c[N + 1 - i] = c[N - i] {c(x) = c(x) * x} 13: end for 14: f[N] = 0 15: c[0] = 0 16: k = k + 1 17: end while 18: if deg(f) = 0 then 19: goto Step 32 20: end if 21: if deg(f) &lt; deg(g) then 22: temp = f {Exchange f and g} 23: f = g 24: g = temp 25: temp = b {Exchange b and c} 26: b = c 27: c = temp 28: end if 29: f = f XOR g 30: b = b XOR c 31: end loop 32: j = 0 33: k = k mod N 34: for i = N - 1 downto 0 do 35: j = i - k 36: if j &lt; 0 then 37: j = j + N 38: end if 39: Fq[j] = b[i] 40: end for 41: v = 2 42: while v &lt; q do 43: v = v * 2 44: StarMultiply(a; Fq; temp;N; v) 45: temp = 2 - temp mod v 46: StarMultiply(Fq; temp; Fq;N; v) 47: end while 48: for i = N - 1 downto 0 do 49: if Fq[i] &lt; 0 then 50: Fq[i] = Fq[i] + q 51: end if 52: end for 53: {Inverse Poly Fq returns the inverse polynomial, Fq, through the argument list.} </code></pre> <p>The function <code>StarMultiply</code> returns a polynomial (array) stored in the variable <code>temp</code>. Basically temp is a polynomial (I'm representing it as an array) and v is an integer (say 4 or 8), so what exactly does <code>temp = 2-temp mod v</code> equate to in normal language? How should i implement that line in my code. Can someone give me an example.</p> <p>The above algorithm is for computing Inverse polynomials for NTRUEncrypt key generation. The pseudo-code can be found on page 28 of <a href="http://www.wpi.edu/Pubs/ETD/Available/etd-0430102-111906/unrestricted/corourke.pdf" rel="nofollow noreferrer">this document</a>. Thanks in advance.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMohammad Sepahvand
    1. USMohammad Sepahvand
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PONTRU Pseudo-code for computing Polynomial Inverses
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PONTRU Pseudo-code for computing Polynomial Inverses
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI'm trying to implement NTRUEncrypt also and since you've done this and considering your method of storing the coefficients is quite similar to mine, I'd really appreciate it if you can give me a hand with the inverse function. Any chance I can contact you by email?
      singulars
      1. PONTRU Pseudo-code for computing Polynomial Inverses
      1. USFljpFl0p
    2. COThanks so much, I'll try my best to implement this for now. I downloaded the document you posted and am going through with it. Might have to bother you in the next few days.
      singulars
      1. PONTRU Pseudo-code for computing Polynomial Inverses
      1. USFljpFl0p
    3. COI sent you an email. Just wanna know if you've received it in case I got the address wrong.
      singulars
      1. PONTRU Pseudo-code for computing Polynomial Inverses
      1. USFljpFl0p
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload