Fast decomposition of small integers into sums of squares#

Implement fast version of decomposition of (small) integers into sum of squares by direct method not relying on factorisation.

AUTHORS:

Vincent Delecroix (2014): first implementation (github issue #16374)

sage.rings.sum_of_squares.four_squares_pyx(n)#

Return a 4-tuple of non-negative integers (i,j,k,l) such that \(i^2 + j^2 + k^2 + l^2 = n\) and \(i \leq j \leq k \leq l\).

The input must be lesser than \(2^{32}=4294967296\), otherwise an OverflowError is raised.

See also

four_squares() is much more suited for large input

EXAMPLES:

sage: from sage.rings.sum_of_squares import four_squares_pyx
sage: four_squares_pyx(15447)
(2, 5, 17, 123)
sage: 2^2 + 5^2 + 17^2 + 123^2
15447

sage: four_squares_pyx(523439)
(3, 5, 26, 723)
sage: 3^2 + 5^2 + 26^2 + 723^2
523439

sage: four_squares_pyx(2**32)
Traceback (most recent call last):
...
OverflowError: ...

sage.rings.sum_of_squares.is_sum_of_two_squares_pyx(n)#

Return True if n is a sum of two squares and False otherwise.

The input must be smaller than \(2^{32} = 4294967296\), otherwise an OverflowError is raised.

EXAMPLES:

sage: from sage.rings.sum_of_squares import is_sum_of_two_squares_pyx
sage: [x for x in range(30) if is_sum_of_two_squares_pyx(x)]
[0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29]

sage: is_sum_of_two_squares_pyx(2**32)
Traceback (most recent call last):
...
OverflowError: ...

sage.rings.sum_of_squares.three_squares_pyx(n)#

If n is a sum of three squares return a 3-tuple (i,j,k) of Sage integers such that \(i^2 + j^2 + k^2 = n\) and \(i \leq j \leq k\). Otherwise raise a ValueError.

The input must be lesser than \(2^{32}=4294967296\), otherwise an OverflowError is raised.

EXAMPLES:

sage: from sage.rings.sum_of_squares import three_squares_pyx
sage: three_squares_pyx(0)
(0, 0, 0)
sage: three_squares_pyx(1)
(0, 0, 1)
sage: three_squares_pyx(2)
(0, 1, 1)
sage: three_squares_pyx(3)
(1, 1, 1)
sage: three_squares_pyx(4)
(0, 0, 2)
sage: three_squares_pyx(5)
(0, 1, 2)
sage: three_squares_pyx(6)
(1, 1, 2)
sage: three_squares_pyx(7)
Traceback (most recent call last):
...
ValueError: 7 is not a sum of 3 squares
sage: three_squares_pyx(107)
(1, 5, 9)

sage: three_squares_pyx(2**32)
Traceback (most recent call last):
...
OverflowError: ...

sage.rings.sum_of_squares.two_squares_pyx(n)#

Return a pair of non-negative integers (i,j) such that \(i^2 + j^2 = n\).

If n is not a sum of two squares, a ValueError is raised. The input must be lesser than \(2^{32}=4294967296\), otherwise an OverflowError is raised.