mirror of
https://github.com/luxfi/lattice.git
synced 2026-09-24 00:25:44 +00:00
zeekay
eaf864890e
- Update module path to github.com/luxfi/lattice/v7 - Add GPU acceleration with Metal (macOS) and CUDA backends - Enhance threshold FHE operations - Revert to vanilla Apache 2.0 license (remove tfhe) - Update Go version to 1.25.5 - Merge upstream lattigo improvements
53 lines
1.4 KiB
Go
53 lines
1.4 KiB
Go
package factorization_test
|
|
|
|
import (
|
|
"math/big"
|
|
"testing"
|
|
|
|
"github.com/luxfi/lattice/v7/utils/factorization"
|
|
"github.com/stretchr/testify/require"
|
|
)
|
|
|
|
const (
|
|
prime uint64 = 0x1fffffffffe00001
|
|
)
|
|
|
|
func TestIsPrime(t *testing.T) {
|
|
// 2^64 - 59 is prime
|
|
require.True(t, factorization.IsPrime(new(big.Int).SetUint64(0xffffffffffffffc5)))
|
|
// 2^64 + 13 is prime
|
|
bigPrime, _ := new(big.Int).SetString("18446744073709551629", 10)
|
|
require.True(t, factorization.IsPrime(bigPrime))
|
|
// 2^64 is not prime
|
|
require.False(t, factorization.IsPrime(new(big.Int).SetUint64(0xffffffffffffffff)))
|
|
}
|
|
|
|
func TestGetFactors(t *testing.T) {
|
|
|
|
t.Run("GetFactors", func(t *testing.T) {
|
|
m := new(big.Int).SetUint64(prime - 1)
|
|
require.True(t, checkFactorization(new(big.Int).Set(m), factorization.GetFactors(m)))
|
|
})
|
|
|
|
t.Run("ECM", func(t *testing.T) {
|
|
m := new(big.Int).SetUint64(prime - 1)
|
|
require.True(t, m.Mod(m, factorization.GetFactorECM(m)).Cmp(new(big.Int)) == 0)
|
|
})
|
|
|
|
t.Run("PollardRho", func(t *testing.T) {
|
|
m := new(big.Int).SetUint64(prime - 1)
|
|
require.True(t, m.Mod(m, factorization.GetFactorPollardRho(m)).Cmp(new(big.Int)) == 0)
|
|
})
|
|
}
|
|
|
|
func checkFactorization(p *big.Int, factors []*big.Int) bool {
|
|
zero := new(big.Int)
|
|
for _, factor := range factors {
|
|
for new(big.Int).Mod(p, factor).Cmp(zero) == 0 {
|
|
p.Quo(p, factor)
|
|
}
|
|
}
|
|
|
|
return p.Cmp(new(big.Int).SetUint64(1)) == 0
|
|
}
|