評価多項式

Question

^（K-1）MOD P kは整数である

は、pは大きな素数およびc（0）、...、C（p）は1とpの間です。 私のアプリケーションでは、k = 10、pは1000より大きい必要があります。

これはPythonでできるだけ早く行うことをお勧めします。私はこれを効率的に実装するためにPythonのモジュロ算術について十分に分かりません（例えば、メルセンヌの素数p = 2^q-1を使うことができるようにするにはどうすればよいでしょうか？その乗算はレジスタシフトです。異なる大きさの整数、...）。

動機：K-独立したハッシュ、https://en.wikipedia.org/wiki/K-independent_hashingを参照してください。これは非常に一般的な学問のようですが、私はk> 2の実装を見つけることができませんでした。一般的に

Answer 1

あなたは次のような構成使用して多項式の値を計算することができ、このモジュロ値を評価するために

def value(poly, x): 
    """Evaluates a polynomial POLY for a given x. 

    The polynomial is expressed as a list of coefficients, with 
    the coefficient for x ** N at poly[N]. 

    This means that x ** 2 + 2*x + 3 is expressed as [3, 2, 1]. 
    """ 
    v = 0 

    # Bit messy, but we're basically generating the indexes of 
    # our polynomial coefficients from highest to lowest 
    for coeff in reverse(poly): 
    v = v * x + coeff 

    return v 

を、我々は単にv = v * x + poly[ix] % pに内部ループを変更（およびとして私達のモジュラスを渡すことができますパラメータp）。

ループを巻き戻して、われわれが持っているものが(((1) * x + 2) * x + 3)（各カッコのレベルはループを通した1回の反復）であることを見て、ポリノームの例（x^2 + 2x + 3）が正しく計算されることを示すことができます。 1 * x * x + 2 * x + 3に単純化されます。これは明らかに期待される多項式です。

これを使用することにより、我々はp * xよりも大きな中間値で終わることはありません。