模块化算术。如何解决以下等式？

Question

如何解决以下等式？

我对解决方案的方法很感兴趣。

n = 3对P =（n + 1）^ 3对P

P-素数

答案的简短例子。你能为我的例子提供逐步的解决方案吗？

n ^ 3对61 =（n + 1）^ 3对61

整数解决方案：

n = 61米+4，

n = 61米+ 56，

m元素Z.

Z - 是整数集。

Answer 1

陈述n^3 ≡ (n+1)^3的另一种方式是n^3 ≡ n^3 + 3 n^2 + 3 n + 1（只是计算出n + 1的立方体）然后立方项取消给出更好的二次3 n^2 + 3 n + 1 ≡ 0

然后应用通常的二次公式，尽管它的所有运算现在都是模P，并且行列式并不总是二次余数，在这种情况下原始方程没有解（这种情况发生在大约一半的时间）。这涉及找到以模数为模的平方根，这对于计算机来说并不难以用例如Tonelli-Shanks算法进行，尽管实现起来并不容易。

顺便说一句，3 n^2 + 3 n + 1 = 0有一个属性，如果n是一个解决方案，那么-n - 1也是。

例如，对于一些Python，一旦所有支持函数都存在，它就非常简单：

def solve(p):
  # solve 3 n^2 + 3 n + 1 ≡ 0
  D = -3 % p
  sqrtD = modular_sqrt(D, p)
  if sqrtD == 0:
    return None
  else:
    n = (sqrtD - 3) * inverse(6, p) % p
    return (n, -(n+1) % p)

反模数素数非常简单，

def inverse(x, p):
  return pow(x, p - 2, p)

我将this implementation of Tonelli-Shanks改编为Python3（//而不是/用于整数除法）

def modular_sqrt(a, p):
    """ Find a quadratic residue (mod p) of 'a'. p
        must be an odd prime.

        Solve the congruence of the form:
            x^2 = a (mod p)
        And returns x. Note that p - x is also a root.

        0 is returned is no square root exists for
        these a and p.

        The Tonelli-Shanks algorithm is used (except
        for some simple cases in which the solution
        is known from an identity). This algorithm
        runs in polynomial time (unless the
        generalized Riemann hypothesis is false).
    """
    # Simple cases
    #
    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return 0
    elif p % 4 == 3:
        return pow(a, (p + 1) // 4, p)

    # Partition p-1 to s * 2^e for an odd s (i.e.
    # reduce all the powers of 2 from p-1)
    #
    s = p - 1
    e = 0
    while s % 2 == 0:
        s //= 2
        e += 1

    # Find some 'n' with a legendre symbol n|p = -1.
    # Shouldn't take long.
    #
    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1

    # Here be dragons!
    # Read the paper "Square roots from 1; 24, 51,
    # 10 to Dan Shanks" by Ezra Brown for more
    # information
    #

    # x is a guess of the square root that gets better
    # with each iteration.
    # b is the "fudge factor" - by how much we're off
    # with the guess. The invariant x^2 = ab (mod p)
    # is maintained throughout the loop.
    # g is used for successive powers of n to update
    # both a and b
    # r is the exponent - decreases with each update
    #
    x = pow(a, (s + 1) // 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e

    while True:
        t = b
        m = 0
        for m in range(r):
            if t == 1:
                break
            t = pow(t, 2, p)

        if m == 0:
            return x

        gs = pow(g, 2 ** (r - m - 1), p)
        g = (gs * gs) % p
        x = (x * gs) % p
        b = (b * g) % p
        r = m


def legendre_symbol(a, p):
    """ Compute the Legendre symbol a|p using
        Euler's criterion. p is a prime, a is
        relatively prime to p (if p divides
        a, then a|p = 0)

        Returns 1 if a has a square root modulo
        p, -1 otherwise.
    """
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls

你可以在ideone上看到一些结果