factorization

Documentation

Overview

Package factorization implements various algorithms for efficient factoring integers of small to medium size.

Index

• func GetFactorECM(N *big.Int) (factor *big.Int)
• func GetFactorPollardRho(m *big.Int) (d *big.Int)
• func GetFactors(m *big.Int) (factors []*big.Int)
• func IsPrime(m *big.Int) bool
• func NewRandomWeierstrassCurve(N *big.Int) (Weierstrass, Point)
• func RandInt(max *big.Int) (n *big.Int)
• type Point
• type Weierstrass
  • func (w *Weierstrass) Add(P, Q Point) Point

Functions

func GetFactorECM

func GetFactorECM(N *big.Int) (factor *big.Int)

GetFactorECM finds a factor of N using ECM factorization.

func GetFactorPollardRho

func GetFactorPollardRho(m *big.Int) (d *big.Int)

GetFactorPollardRho implements Pollard's Rho algorithm for fast prime factorization, but this function only returns one factor per call This function can fail and return m.

func GetFactors

func GetFactors(m *big.Int) (factors []*big.Int)

GetFactors returns all the prime factors of m. Only the unique primes are returned, not their power.

func IsPrime

func IsPrime(m *big.Int) bool

func NewRandomWeierstrassCurve

func NewRandomWeierstrassCurve(N *big.Int) (Weierstrass, Point)

NewRandomWeierstrassCurve generates a new random Weierstrass curve modulo N, along with a random point that lies on the curve.

func RandInt

func RandInt(max *big.Int) (n *big.Int)

RandInt generates a random Int in [0, max-1].

Types

type Point

type Point struct {
	X, Y *big.Int
}

Point represents an elliptic curve point in standard coordinates.

type Weierstrass

type Weierstrass struct {
	A, B, N *big.Int
}

Weierstrass is an elliptic curve y^2 = x^3 + ax + b mod N.

func (*Weierstrass) Add

func (w *Weierstrass) Add(P, Q Point) Point

Add adds two Weierstrass points together with respect to the underlying Weierstrass curve. This method does not check if the points lie on the underlying curve.