On Sun, Feb 7, 2010 at 12:35 PM, Rolandb <[email protected]> wrote:
> Hi,
> Consider Euler’s famous expression x=a^2+n*b^2. I want to solve a and
> b, given x and n. Because solve_mod is totally broken, I tried to
> develop a clever method myself. Counterintuitively, I found that the
> most simple brute force method in SAGE is relatively fast.
>
> def bruteforce(number,n):
> out=[]
> for b in xrange(isqrt(number/n)):
> (bool,a)=is_square(number-n*b^2,True)
> if bool: out.append((a,b))
> return out
>
> My questions are:
> - Why is the brute force method relatively fast?
> - Is there a clever approach (not dependent on solve_mod)?
>
> Thanks in advance! Roland
We have
x=a^2+n*b^2 = (a-sqrt(n)*b)*(a+sqrt(n)*b) = Norm(a+sqrt(n)*b),
where the norm is in the quadratic field Q(sqrt(n)). Thus a solution
corresponds to a factorization of the ideal generated by x in the ring
of integers of Q(sqrt(n)). So here is some code related to your
question above, which you may or may not find relevant, depending on
whether you're making n big or x:
def eqn(x, n):
"""
Solve x = a^2+n*b^2 when x is prime, n is not a square, and there
is a solution.
EXAMPLES:
sage: a,b = eqn(13, -3); a,b
(4, 1)
sage: a^2 + -3*b^2
13
sage: a,b = eqn(113, 97); a,b
(-4, 1)
sage: a^2 + 97*b^2
113
"""
proof.number_field(False)
assert is_prime(x), "x must be prime"
assert not is_square(n), "n must not be a square"
R.<X> = QQ[]
K.<a> = NumberField(X^2 + n)
F = K.factor(x)
if len(F) == 1 and F[0][1] == 1:
raise ValueError, "no solution (x is inert)"
A = F[0][0].gens_reduced()
if len(A) > 1:
raise ValueError, "no solution (ideal isn't principal)"
return A[0][0], A[0][1]
--
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
