UMPC LIP6 Calcul Scientifique
Home
Publications

Software
Teaching
 


Polynomial Systems: Symmetric Benchmarks

Quadratic / Cubic Equations in n variables - G = Commutative Group Za x Zb

 

n Group Degree 2 / Original / G-degree (0,1) Degree 2 / Linear Change / G-degree (0,1) Degree 3 / Original / G-degree (0) Degree 3 / Linear Change / G-degree (0)
8 Z8 (2,2) (2,2) (3) (3)
8 Z6 x Z2 (2,2) (2,2) (3) (3)
8 Z4 x Z4 (2,2) (2,2) (3) (3)
10 Z10 (2,2) (2,2) (3) (3)
10 Z8 x Z2 (2,2) (2,2) (3) (3)
10 Z6 x Z4 (2,2) (2,2) (3) (3)
10 Z5 x Z5 (2,2) (2,2) (3) (3)

NTRU quadratic equations: 2n equations / n variables - Cyclic Group Zn

n 16 19 20 21 22 23 24 25 26 27 28 29 30
NTRU Original Equations Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs
NTRU Equations Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs Eqs

Implementation

An implementation (Jules Svartz) of an abelian version of FGLM, which performs a change of ordering of an ideal invariant under a diagonal matrix group:

> load "./abelian_fglm_systems.m";
Loading "./abelian_fglm_systems.m"
> load "./abelian_fglm.m";
Loading "./abelian_fglm.m"
> GBDRL,degreeG,degreeVar:=InitializationCyclicPb(5);
> GBLEX:=Abelian_FGLM(GBDRL,degreeG,degreeVar);
Changing Order on Polynomial ring of rank 4 over GF(65011)
Order: Graded Reverse Lexicographical
Variables: x1, x2, x3, x4.

Ideal invariant under the action of an Abelian Group isomorphic to Z/5 + Z/5
Defined on 2 generators
Relations:
5*degreeG.1 = 0
5*degreeG.2 = 0.

The global staircase has size : 70.
The sizes of the staircases indexed by each G-degree are : 6, 2, 2, 2, 2, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3.

The sizes of the multiplication matrices indexed by each G-degree and each variable are : 6*3, 6*3, 6*3, 6*3, 2*3, 2*3, 2*3, 2*2, 2*3, 2*3, 2*2, 2*3, 2*3, 2*2, 2*3, 2*3, 2*2, 2*3, 2*3, 2*3, 2*3, 2*3, 2*3, 2*3, 3*3, 3*3, 3*3, 3*2, 3*3, 3*3, 3*2, 3*3, 3*3, 3*2, 3*3, 3*3, 3*2, 3*3, 3*3, 3*3, 2*3, 2*3, 2*3, 2*3, 3*3, 3*3, 3*3, 3*2, 3*3, 3*3, 3*2, 3*3, 3*3, 3*2, 3*3, 3*3, 3*2, 3*3, 3*3, 3*3, 2*3, 2*3, 2*3, 2*3, 3*3, 3*3, 3*3, 3*2, 3*3, 3*3, 3*2, 3*3, 3*3, 3*2, 3*3, 3*3, 3*2, 3*3, 3*3, 3*3, 2*2, 2*2, 2*2, 2*2, 3*2, 3*2, 3*2, 3*6, 3*2, 3*2, 3*6, 3*2, 3*2, 3*6, 3*2, 3*2, 3*6, 3*2, 3*2, 3*2.

> GBLEX;
[
x4^16 + 65010*x4^11 + 1166*x4^6 + 63845*x4,
x3*x4^11 + 1166*x3*x4,
10150*x4^11 + x3^5*x4 + 51963*x4^6 + 2898*x4,
2509*x3*x4^10 + x3^6 + 51963*x3*x4^5 + 65010*x3,
32055*x3^2*x4^10 + 45437*x3^2*x4^5 + x2*x4,
32055*x3^3*x4^9 + 45437*x3^3*x4^4 + x2*x3,
6289*x3^2*x4^9 + x2^6 + 41687*x3^2*x4^4 + 65010*x2,
64914*x3^3*x4^9 + 19452*x3^3*x4^4 + x1*x4,
64914*x3^4*x4^8 + 19452*x3^4*x4^3 + x1*x3,
48615*x4^12 + 58600*x4^7 + x1*x2 + 22807*x4^2,
6070*x4^15 + 2509*x4^10 + x1^5 + x2^5 + x3^5 + 56433*x4^5 + 65010
]

 
 
Last Update: October 28, 2015