标签: finite-field

一般

我正在寻找一个能够在大型有限域上进行精确计算的库,例如GF(2 ¹²⁸)/ _{2 ¹²⁸}和GF(2 ²⁵⁶)/ _{2 ²⁵⁶}.我列出了我需要的功能以及下面很酷的功能.显然,图书馆应尽可能快:-).啊,因为我不是C++主人(可能大多数库是C++),所以示例代码生成一个随机元素/一个常量并将其乘以它的乘法逆

必备功能

• 增加了田野元素
• 场元素的乘法
• 找到字段元素的乘法逆

很高兴有特色

• 矢量/矩阵支持
• 随机元素支持

我已经看过的图书馆可能不会起作用

• FFLAS/FFPACK似乎不适用于如此大的有限域
• Givaro似乎没有在如此大的有限领域工作

我已经看过的图书馆可以工作(但我无法使用)

• NTL,我无法反转一个元素,但它应该真的有效,因为SAGE似乎在定义GF(2 ^ 256)时使用这个库,并且可以使用它来反转元素x^(-1)
• PARI/GP,我无法在文档中找到我需要的所有内容,但是SAGE文档有点说它应该可以工作

其他说明

• 我正在编写一个Haskell程序,稍后将接口该库,因此更容易Haskell接口更好:-)

我正在开发一个涉及Koblitz曲线加密目的的项目

在python中需要一个库来实现有限域操作,如Galois Field中的乘法和逆(GF(2 ^ n))

已经尝试过以下库:BitVector https://engineering.purdue.edu/kak/dist/BitVector-3.3.2.html 不幸的是,即使对于大小为2 ^ 163的字段,模数逆操作也工作得太慢.

我有兴趣在有限域上n解析大(最多10 ^ 5甚至10 ^ 6)矩形(可能比行多10%的列)稀疏(每行<10非零)系统(可能是1000附近的素数或者所以).从文献来看,看起来块Lanczos方法可能是最合适的.Ax = bGF(q)q

我有Linbox应该有这样的方法,但是无法让BlockLanczos求解器在那里工作,并且有一份报告称自2003年以来已经破坏了.该SparseElimination方法确实有效,但似乎这不会很好n因为矩阵的填充而变大.

那么,有什么可用于解决这些问题呢？

我正在自学matplotlib和Python,我很难绘制椭圆曲线的方程.我有等式,但我没有做y^2

这和我到目前为止所遇到的一样麻烦:

from mpl_toolkits.axes_grid.axislines import SubplotZero
import matplotlib.pyplot as plt
import numpy as np
from pylab import *


def plotGraph():
    fig = plt.figure(1)
    ax = SubplotZero(fig, 111)
    fig.add_subplot(ax)

    for direction in ["xzero", "yzero"]:
        ax.axis[direction].set_axisline_style("-|>")
        ax.axis[direction].set_visible(True)

    a = 5; b = 25
    x = np.arange(-50.0, 50.0, 1.0)
    y = pow(x,3) + a*x + b

    xmin = -50; xmax = 50; ymin = -50; ymax = 50
    v = [xmin, xmax, ymin, ymax]
    ax.axis(v)

    ax.plot(x, pow(y,2))

    #grid()
    #ax.grid(color='r', linestyle='-', linewidth=2)

    show() …

我正在为Haskell寻找有限域线性代数库.

像Haskell的FFLAS-FFPACK之类的东西会很棒:-).

当然,我检查了hmatrix,似乎对任意矩阵元素类型有一些支持,但我找不到任何与hmatrix一起使用的有限域库.当然,我很欣赏一个高性能的解决方案:-)

特别地,我希望能够将_p ^n×1和_p ^1×m矩阵(向量)乘以_p ^n×m矩阵.

你知道C++ 中Galois域算法的实现吗？至少应包括GF(2 ¹⁶)和GF(2 ³²)等案例.性能是一个问题,因此实现应该考虑优化其操作.

我更喜欢一个通用的计算库或一个专门用于此任务的小型库.缺乏这些,我也欢迎一些可读的源代码.

我想用NTT实现多项式的乘法.我遵循数论变换(整数DFT),它似乎工作.

现在我想在有限域Z_p[x]上实现多项式的乘法,其中有限域p是任意素数.

p与之前的无界情况相比,它是否会改变系数现在受限制的任何东西？

特别是,原始NTT需要找到素数N作为工作模数,该工作模数大于(magnitude of largest element of input vector)^2 * (length of input vector) + 1结果永不溢出.如果结果将受到该p素数的限制,那么模数可以有多小？请注意,p - 1不必是形式(some positive integer) * (length of input vector).

编辑:我从上面的链接复制粘贴源来说明问题:

# 
# Number-theoretic transform library (Python 2, 3)
# 
# Copyright (c) 2017 Project Nayuki
# All rights reserved. Contact Nayuki for licensing.
# https://www.nayuki.io/page/number-theoretic-transform-integer-dft
#

import itertools, numbers

def find_params_and_transform(invec, minmod):
    check_int(minmod)
    mod = find_modulus(len(invec), …

我正在为C 搜索有限域/ galois域精确线性代数库(C++是不可接受的,因为我需要能够编写一个Haskell绑定到它,这对C++来说显然很难).

我找到了类似FFLAS-FFPACK和Givaro的库,但这些是C++ - 模板库:-(

特别地,我希望能够将_p ^n×1和_p ^1×m矩阵(向量)乘以_p ^n×m矩阵.

那么,有没有人知道C或"extern C"库是否合适？

PS:这是关于同一事项的我的Haskell问题.

这两个函数执行扩展欧几里德算法,然后找到乘法逆.这个顺序似乎是正确的,但它并没有按照悉尼大学的这个工具回复http://magma.maths.usyd.edu.au/calc/,因为这是在GF(2)完成的. )有限域,我想我错过了从基数10转换到这个字段的一些关键步骤.

这在基数10上进行了测试和处理,但是在这里可能无法接收具有二进制系数的多项式.所以我的问题是我错误地应用于这个算法的Python的哪些部分,例如// floor,可能无法承载基本10中的函数能够在GF(2)中执行此操作.

上面的工具可以像这样测试:

R<x>:=PolynomialRing(GF(2));
p:=x^13+x+1; q:=x^12+x;
g,r,s:=XGCD(p,q);

g eq r*p+s*q;

g,r,s;

功能:

def extendedEuclideanGF2(self,a,b): # extended euclidean. a,b are values 10110011... in integer form
    inita,initb=a,b;  x,prevx=0,1;  y,prevy = 1,0
    while b != 0:
        q = int("{0:b}".format(a//b),2)
        a,b = b,int("{0:b}".format(a%b),2);
        x,prevx = (int("{0:b}".format(prevx-q*x)), int("{0:b}".format(x,2)));  y,prevy=(prevy-q*y, y)
    print("Euclidean  %d * %d + %d * %d = %d" % (inita,prevx,initb,prevy,a))
    return a,prevx,prevy  # returns gcd of (a,b), and factors s and t

def modular_inverse(self,a,mod): # a,mod are integer values …

有没有一种方法可以使用 python 求解域 F2 上的线性方程组（即加法和乘法模 2 - 二进制域）？我已经尝试寻找有用的软件包有一段时间了，但没有找到任何结果......

谢谢，