Другой способ указать 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, и определитель не всегда является квадратичным вычетом, и в этом случае нет решений для исходного уравнения (это происходит примерно в половине случаев).Это включает в себя поиск квадратного корня по модулю простого числа, что не сложно для компьютера сделать, например, с помощью алгоритма Тонелли-Шенкса, хотя это не тривиально для реализации.
Кстати, 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)
Inverse moduloпростое число действительно легко,
def inverse(x, p):
return pow(x, p - 2, p)
Я адаптировал эту реализацию 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