java - Calculating Inverse of Polynomial Rings -

-

i try understand ntru-pkcs , wanted implement simple version in java, therefore used self-implemented method (extend euclid) calculating inverse of polynomial in ring.

most of times algorithm works, when try example ntru-pkcs-tutorial pkcs-tutorial fails , dont know why.

the example is:

f: -x^10+1x^9+0x^8+0x^7+1x^6+0x^5-x^4+0x^3+1x^2+1x^1-x^0 f^-1 mod 32: 30x^10+18x^9+20x^8+22x^7+16x^6+15x^5+4x^4+16x^3+6x^2+9x^1+5x^0 ring: x^11-1

my code is:

public polynomialmod inverse(int n, int mod) {     int loop = 0;     polynomialmod g = polynomialmod.zero.clone();     g.setnmod(n, mod);     polynomialmod newg = (polynomialmod) polynomialmod.one.clone();     newg.setnmod(n, mod);     int[] coeffr = { 1, 1, 0, 1, 1, 0, 0, 0, 1 };      polynomialmod quotient = null;     polynomialmod newr = this.clone();     polynomialmod r = this.getring(n, mod);     r.setnmod(n, mod);     newr.setnmod(n, mod);      while (!newr.equalszero()) {         if (debug && loop != 0)             system.out.println("loop: " + loop);         if (debug && loop == 0)             system.out.println("========initial values========");         if (debug)             system.out.println("r   : " + r);         if (debug)             system.out.println("newr: " + newr);         if (debug)             system.out.println("quotient: " + quotient);         if (debug)             system.out.println("g   : " + g);         if (debug)             system.out.println("newg: " + newg);         if (debug && loop == 0)             system.out.println("========initial values========");         if (debug)             system.out.println("\n");          quotient = r.div(newr)[0];         polynomialmod = r.clone();         r = newr.clone();         polynomialmod times = quotient.times(newr);         times.reducebetweenzeroandq();         newr = help.sub(times);         newr.deleteleadingzeros();         newr.degree = newr.values.size() - 1;         = g.clone();         g = newg.clone();         polynomialmod times2 = quotient.times(newg);         times2.reducebetweenzeroandq();         newg = help.sub(times2);         loop++;      }     if (r.getdegree() > 0)         throw new arithmeticexception("irreducible or multiple");      return g.div(r)[0]; }

the output like:

========initial values======== r   : [ -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ] newr: [ -1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1 ] quotient: null g   : [ 0 ] newg: [ 1 ] ========initial values========   loop: 1 r   : [ -1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1 ] newr: [ 30, 0, 2, 1, 31, 31, 1, 1, 0, 1 ] quotient: [ 31, 31 ] g   : [ 1 ] newg: [ 1, 1 ]   loop: 2 r   : [ 30, 0, 2, 1, 31, 31, 1, 1, 0, 1 ] newr: [ 1, 31, 31, 1, 1, 0, 31, 0, 1 ] quotient: [ 1, 31 ] g   : [ 1, 1 ] newg: [ 0, 0, 1 ]   loop: 3 r   : [ 1, 31, 31, 1, 1, 0, 31, 0, 1 ] newr: [ 30, 31, 3, 2, 30, 30, 1, 2 ] quotient: [ 0, 1 ] g   : [ 0, 0, 1 ] newg: [ 1, 1, 0, 31 ]

the problem is: if calculate r/newr have find inverse of 2 mod 32 since greatest common divisor of 32 , 2 2 not 1, there no inverse...

have implemented algorithm wrong?

problem solved: wasnt euclidean ring, had calculate inverse mod 2 , lift mod 32...

how works


Comments

Post a Comment

Popular posts from this blog

wordpress - (T_ENDFOREACH) php error -

-
creating wordpress website , i'm getting following php error: parse error: syntax error, unexpected 'endforeach' (t_endforeach) in /home/soralmedia/public_html/wp-content/themes/soral media/woocommerce/myaccount/my-orders.php on line 98 here's code file: <?php /** * orders * * shows recent orders on account page. * * template can overridden copying yourtheme/woocommerce/myaccount/my-orders.php. * * however, on occasion woocommerce need update template files , (the theme developer). * need copy new files theme maintain compatibility. try this. * little possible, happen. when occurs version of template file will. * bumped , readme list important changes. * * @see http://docs.woothemes.com/document/template-structure/ * @author woothemes * @package woocommerce/templates * @version 2.5.0 */ if ( ! defined( 'abspath' ) ) { exit; } $my_orders_columns = apply_filters( 'woocommerce_my_account_my_orders_columns', array( ...
Read more

Export Excel workseet into txt file using vba - (text and numbers with formulas) -

-
i new vba have developed code use in excel move text/numbers txt file. issue have 3 functions need go same txt file. when run first function has set fs = createobject("scripting.filesystemobject") set = fs.createtextfile(module1.nys45uploadfilename, true) a.writeline (str) a.close. the other 2 functions had save. set fs = createobject("scripting.filesystemobject") set = fs.savetextfile(module1.nys45uploadfilename, true) a.writeline (str) a.close. the first function go txt file, other 2 error object doesn't support property or method. when changed 3 create last function goes txt file. can not figure out word use in order make other 2 functions follow txt file in order keyed. the entire code follows private sub addrecord_click() on error goto errhandler module1.nys45uploadfilename = application.getsaveasfilename(filefilter:="textfiles (*.txt), *.txt") if module1.nys45uploadfilename = "false" exit sub ...
Read more

Using django-mptt to get only the categories that have items -

-
sample structure: all uppercase: category mixed case: item root ├── books │   ├── fiction │   │   └── classics │   └── non-fiction ├── clothing └── electronics ├── laptops ├── phones │   ├── apple │   │   ├── iphone 6 │   │   ├── iphone 6 plus │   │   ├── iphone 6s │   │   └── iphone 6s plus │   ├── motorola │   │   ├── moto g4 │   │   ├── moto g4 play │   │   ├── moto g4 plus │   │   └── moto x │   └── samsung └── tablets └── apple i'm trying have index page show "electronics" category. "clothing" category shouldn't show since it's empty , "books" category shouldn't show either since, although has child categories, child categories don't have items. similarly, "electronics" page should show "phones" category. "laptops" category shouldn't show since it's empty , "tablets" category shouldn't show either since...
Read more