On Polynomial Modular Number Systems over $\mathbb{Z}/p\mathbb{Z}$
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911906465316864 |
|---|---|
| author | Bajard, Jean Claude Marrez, Jérémy Plantard, Thomas Véron, Pascal |
| author_facet | Bajard, Jean Claude Marrez, Jérémy Plantard, Thomas Véron, Pascal |
| contents | Since their introduction in 2004, Polynomial Modular Number Systems (PMNS) have become a very interesting tool for implementing cryptosystems relying on modular arithmetic in a secure and efficient way. However, while their implementation is simple, their parameterization is not trivial and relies on a suitable choice of the polynomial on which the PMNS operates. The initial proposals were based on particular binomials and trinomials. But these polynomials do not always provide systems with interesting characteristics such as small digits, fast reduction, etc.
In this work, we study a larger family of polynomials that can be exploited to design a safe and efficient PMNS. To do so, we first state a complete existence theorem for PMNS which provides bounds on the size of the digits for a generic polynomial, significantly improving previous bounds. Then, we present classes of suitable polynomials which provide numerous PMNS for safe and efficient arithmetic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2001_03741 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | On Polynomial Modular Number Systems over $\mathbb{Z}/p\mathbb{Z}$ Bajard, Jean Claude Marrez, Jérémy Plantard, Thomas Véron, Pascal Data Structures and Algorithms Number Theory Since their introduction in 2004, Polynomial Modular Number Systems (PMNS) have become a very interesting tool for implementing cryptosystems relying on modular arithmetic in a secure and efficient way. However, while their implementation is simple, their parameterization is not trivial and relies on a suitable choice of the polynomial on which the PMNS operates. The initial proposals were based on particular binomials and trinomials. But these polynomials do not always provide systems with interesting characteristics such as small digits, fast reduction, etc. In this work, we study a larger family of polynomials that can be exploited to design a safe and efficient PMNS. To do so, we first state a complete existence theorem for PMNS which provides bounds on the size of the digits for a generic polynomial, significantly improving previous bounds. Then, we present classes of suitable polynomials which provide numerous PMNS for safe and efficient arithmetic. |
| title | On Polynomial Modular Number Systems over $\mathbb{Z}/p\mathbb{Z}$ |
| topic | Data Structures and Algorithms Number Theory |
| url | https://arxiv.org/abs/2001.03741 |