README
¶
LFS - Lagrange Four-Squares
LFS is a Go package that implements an optimized algorithm for solving the Lagrange four-squares problem, even for very large integers.
It computes a representation of any positive integer n as the sum of four squares:
$$ n = {w_0}^2 + {w_1}^2 + {w_2}^2 + {w_3}^2 $$
This implementation is highly optimized for very large integers (e.g., 1000 bits, 2000 bits, or more).
The underlying algorithms are based on Section 3 of the paper Finding the Four Squares in Lagrange's Theorem with additional improvements that significantly enhance performance.
Usage
Below is a simple example:
package main
import (
"crypto/rand"
"fmt"
"log"
"math/big"
"github.com/txaty/lfs"
)
func main() {
// Create a new solver with default options.
solver := lfs.NewSolver()
// Define a large integer.
limit := new(big.Int).Lsh(big.NewInt(1), 1200)
n, err := rand.Int(rand.Reader, limit)
if err != nil {
log.Fatal(err)
}
// Compute the four-square representation.
result := solver.Solve(n)
// Display the result.
fmt.Printf("Representation of n as sum of four squares: %s\n", result)
// Verify the representation.
if lfs.Verify(n, result) {
fmt.Println("Verification succeeded: The squares sum to n.")
} else {
log.Fatal("Verification failed: The computed squares do not sum to n.")
}
}
Configuration Options
The solver is configurable via functional options when creating a new instance. For example:
- WithFCMThreshold: Sets the threshold above which the advanced FCM algorithm is used.
Example:
solver := lfs.NewSolver( lfs.WithFCMThreshold(new(big.Int).Lsh(big1, 600)), // Use FCM for numbers ≥ 2^600 ) - WithNumRoutines: Sets the number of concurrent goroutines for the randomized search.
Example:
solver := lfs.NewSolver( lfs.WithNumRoutines(8), // Use 8 goroutines for parallel computation )
Dependencies
This project requires the following dependencies:
- txaty/go-bigcomplex: A big complex number library supporting big Gaussian and Hurwitz integers.
- lukechampine.com/frand: A fast randomness generation library.
License
This project is released under the MIT License.
Documentation
¶
Overview ¶
Package lfs provides functionality to compute Lagrange four-square representations of positive integers using different algorithms. Both a basic method and a more complicated Fermat-Christmas Method (FCM) are provided. Settings are configurable via functional options.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CacheGaussianInt ¶
func CacheGaussianInt(e int)
CacheGaussianInt precomputes and caches (1+i)^n for n <= e.
func ResetCacheGaussianInt ¶
func ResetCacheGaussianInt()
ResetCacheGaussianInt resets the Gaussian integer cache.
Types ¶
type FourInt ¶
FourInt represents a group of four big.Int values.
func NewFourInt ¶
NewFourInt creates a new FourInt with its components sorted in descending order.
type Option ¶ added in v0.1.0
type Option func(*Solver)
Option defines a functional option for configuring the Solver.
func WithFCMThreshold ¶ added in v0.1.0
WithFCMThreshold configures the FCM threshold.
func WithNumRoutines ¶ added in v0.1.0
WithNumRoutines configures the number of goroutines used in random search.
type Solver ¶ added in v0.1.0
type Solver struct {
// FCMThreshold determines when to use the FCM-based algorithm.
// If the input n is greater than or equal to FCMThreshold, the FCM algorithm is used.
FCMThreshold *big.Int
// NumRoutines specifies the number of goroutines to use for parallel randomized search.
NumRoutines int
}
Solver encapsulates configuration for computing the four-square representation.
func NewSolver ¶ added in v0.1.0
NewSolver creates a new Solver with the provided options. By default, FCMThreshold is set to 2^500 and NumRoutines to the number of available CPUs.
Source Files