On solving sparse algebraic equations over finite fields

Igor Semaev

首页> 外文期刊>Designs, Codes and Crytography >On solving sparse algebraic equations over finite fields

【24h】

On solving sparse algebraic equations over finite fields

机译：关于有限域上的稀疏代数方程组的求解

获取原文

获取原文并翻译 | 示例

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

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

A system of algebraic equations over a finite field is called sparse if each equation depends on a small number of variables. In this paper new deterministic algorithms for solving such equations are presented. The mathematical expectation of their running time is estimated. These estimates are at present the best theoretical bounds on the complexity of solving average instances of the above problem. In characteristic 2 the estimates are significantly lower the worst case bounds provided by SAT solvers.

机译：如果每个方程依赖少量变量，则一个有限域上的代数方程组称为稀疏方程组。在本文中，提出了求解此类方程式的新确定性算法。估算了其运行时间的数学期望。目前，这些估计值是解决上述问题的平均情况的复杂性的最佳理论界限。在特征2中，估计值明显低于SAT解算器提供的最坏情况范围。

著录项

来源
《Designs, Codes and Crytography》 |2008年第3期|p.47-60|共14页
作者
Igor Semaev;
展开▼
作者单位

Department of Informatics, University of Bergen, Bergen, Norway;

展开▼
收录信息美国《科学引文索引》(SCI);美国《工程索引》(EI);
原文格式 PDF
正文语种 eng
中图分类
关键词
sparse algebraic equations over finite fields; constraint satisfaction problem; gluing; random allocations;

机译：有限域上的稀疏代数方程;约束满足问题胶合;随机分配;

相似文献

外文文献
中文文献
专利

1. SPARSE ALGEBRAIC EQUATIONS OVER FINITE FIELDS [J] . Semaev I SIAM Journal on Computing . 2010,第2期

机译：有限域上的稀疏代数方程
2. Solving sparse linear systems of equations over finite fields using bit-flipping algorithm [J] . Mofrad A.A., Sadeghi M.-R., Panario D. Linear Algebra and its Applications . 2013,第7期

机译：使用位翻转算法求解有限域上的稀疏线性方程组
3. ITERATIVE METHODS FOR SOLVING LARGE SPARSE LYAPUNOV EQUATIONS AND APPLICATION TO MODEL REDUCTION OF INDEX 1 DIFFERENTIAL-ALGEBRAIC-EQUATIONS [J] . M. Sumon Hossain, M. Monir Uddin Numerical Algebra, Control and Optimization . 2019,第2期

机译：求解大型稀疏Lyapunov方程的迭代方法及应用于指数1差分代数方程的模型减少
4. Efficient procedure for solving circuit algebraic-differential equations with modified sparse LU factorization improving fill-in suppression [C] . Dobes Josef, Cerny David, Biolek Dalibor 2011 20th European Conference on Circuit Theory and Design . 2011

机译：改进的稀疏LU分解改进填充抑制的求解电路代数-微分方程的有效程序
5. Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis. [D] . Bard, Gregory V. 2007

机译：用于求解有限域上方程的线性和多项式系统的算法，并应用于密码分析。
6. Algebraic complexities and algebraic curves over finite fields [O] . D. V. Chudnovsky, G. V. Chudnovsky 1987

机译：有限域上的代数复杂度和代数曲线
7. Iterative methods for solving large sparse Lyapunov equations and application to model reduction of index 1 differential-algebraic-equations [O] . M. Sumon Hossain, M. Monir Uddin 2019

机译：求解大型稀疏Lyapunov方程的迭代方法及应用于指标1差分代数方程的模型减少
8. Secant/Finite Difference Algorithm for Solving Sparse Nonlinear Systems of Equations. [R] . Li, G. 1986

机译：求解稀疏非线性方程组的正割/差分算法。

On solving sparse algebraic equations over finite fields

摘要

著录项

相似文献

相关主题

期刊订阅