On the computation of rational solutions of underdetermined systems over a finite field

Nardo Gimenez; Guillermo Matera; Mariana PerezMelina Privitelli

首页> 外文期刊>Journal of complexity >On the computation of rational solutions of underdetermined systems over a finite field

【24h】

On the computation of rational solutions of underdetermined systems over a finite field

机译：On the computation of rational solutions of underdetermined systems over a finite field

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相关主题

摘要

We design and analyze an algorithm for computing solutions with coefficients in a finite field W_q of underdetermined systems defined over W_q . The algorithm is based on reductions to zero-dimensional searches. The searches are performed on "vertical strips", namely parallel linear spaces of suitable dimension in a given direction. Our results show that, on average, less than three searches suffice to obtain a solution of the original system, with a probability of success which grows exponentially with the number of searches. The analysis of our algorithm relies on results on the probability that the solution set (over the algebraic closure of W_q ) of a random system with coefficients in W_q satisfies certain geometric and algebraic properties which is of independent interest.

著录项

来源
《Journal of complexity》 |2023年第4期|101712.1-101712.31|共31页
作者
Nardo Gimenez; Guillermo Matera; Mariana PerezMelina Privitelli;
展开▼
作者单位

Universidad National de Hurlingham, Institute de Tecnologia e Ingenieria, Av. Gdor. Vergara 2222 (B1688GEZ), Villa Tesei, Buenos Aires, Argentina;

Instituto del Desarrollo Humano, Universidad National de General Sarmiento, J.M. Gutierrez 1150 (B1613GSX), Los Polvorines, Buenos Aires, Argentina,National Council of Stience and Technology (CONICET), Argentina;

Universidad National de Hurlingham, Institute de Tecnologia e Ingenieria, Av. Gdor. Vergara 2222 (B1688GEZ), Villa Tesei, Buenos Aires, Argentina,National Council of Stience and Technology (CONICET), ArgentinaNational Council of Stience and Technology (CONICET), Argentina,Instituto de Ciencias, Universidad National de General SarmientoJ.M. Gutierrez 1150(B1613GSX), Los Polvorines, Buenos Aires, Argentina;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类
关键词
Finite fields; Underdetermined systems; Rational solutions; Reduced regular sequences; Average-case complexity; Probability of success;

On the computation of rational solutions of underdetermined systems over a finite field

摘要

著录项

相关主题

期刊订阅