factorizer

Documentation

Index

• Constants
• Variables
• type EllipticCurve
  • func NewEllipticCurve(n *math.Int, g *Point) *EllipticCurve
• type FactorFinder
• type Factorizer
  • func NewFactorizer(algs ...int) *Factorizer
  • func (f *Factorizer) Decompose(n *math.Int) (list []*math.Int)
• type Lenstra_ECM
  • func (f *Lenstra_ECM) GetFactor(n *math.Int) *math.Int
• type Point
• type Pollard_Pminus1
  • func (f *Pollard_Pminus1) GetFactor(n *math.Int) *math.Int
• type Pollard_rho
  • func (f *Pollard_rho) GetFactor(n *math.Int) *math.Int
• type ProjPoint
  • func NewProjPoint(p *Point) *ProjPoint
• type QuadraticSieve
  • func (qsieve *QuadraticSieve) GetFactor(n *math.Int) *math.Int
• type William_Pplus1
  • func (f *William_Pplus1) GetFactor(n *math.Int) *math.Int

Constants

const (
	POLLARD_RHO = iota
	POLLARD_PMINUS1
	WILLIAM_PPLUS1
	LENSTRA_ECM
	QUADRATIC_SIEVE
)

list of known algorithms

const (
	PM1_RETRY = 100
	PM1_BMAX  = 10000
)

Algorithm constants

const (
	RHO_RETRY = 100
	RHO_LOOP  = 8192
)

Algorithm constants

const (
	PP1_MAXSTEP = 100
	PP1_AMAX    = 10000
)

Algorithm constants

const (
	INTERVAL_SIZE = 1000000
)

Variables

var MAX_SMALL = math.NewInt(25000)

MAX_SMALL is the number of small primes to be (always) checked

Types

type EllipticCurve

type EllipticCurve struct {
	// contains filtered or unexported fields
}

Simple elliptic curve in Montgomery representation: By^2= x^3 + Ax^2 + x"

func NewEllipticCurve

func NewEllipticCurve(n *math.Int, g *Point) *EllipticCurve

Instanciate a random elliptic curve over Fn through point P @param n - field generator (mod n) @param g Point - base point (generator)

type FactorFinder

type FactorFinder interface {
	GetFactor(n *math.Int) *math.Int
}

FactorFinder interface implement by different algorithms

type Factorizer

type Factorizer struct {
	// contains filtered or unexported fields
}

Factorizer uses various algorithm for integer factorization

func NewFactorizer

func NewFactorizer(algs ...int) *Factorizer

Instantiate new Factorizer with given algorithms. @param algs - list of algorithm identifiers

func (*Factorizer) Decompose

func (f *Factorizer) Decompose(n *math.Int) (list []*math.Int)

Decompose an integer value into its prime factors @param n - number to be factorized @return list - (unordered) list of prime factors

type Lenstra_ECM

type Lenstra_ECM struct{}

Lenstra_ECM algorithm

func (*Lenstra_ECM) GetFactor

func (f *Lenstra_ECM) GetFactor(n *math.Int) *math.Int

Find a factor using the Lenstra ECM algorithm @param n - number to be factorized @return - factor of n (or nil)

type Point

type Point struct {
	// contains filtered or unexported fields
}

Simple point in Montgomery representation (affine coordinates).

type Pollard_Pminus1

type Pollard_Pminus1 struct{}

Find a factor of number n using Pollards p-1 algorithm.

func (*Pollard_Pminus1) GetFactor

func (f *Pollard_Pminus1) GetFactor(n *math.Int) *math.Int

Pollards p-1 algorithm @param n - number to be factorized @return - found factor (or null)

type Pollard_rho

type Pollard_rho struct{}

Find a factor of number n using Pollards rho algorithm.

func (*Pollard_rho) GetFactor

func (f *Pollard_rho) GetFactor(n *math.Int) *math.Int

Pollards rho algorithm @param n - number to be factorized @return - found factor (or nil)

type ProjPoint

type ProjPoint struct {
	Point
	// contains filtered or unexported fields
}

Point in projective coordionates.

func NewProjPoint

func NewProjPoint(p *Point) *ProjPoint

Instanciate projective point from affine coordinates @param P - point in affine coordinates @return - projective point

type QuadraticSieve

type QuadraticSieve struct{}

Decompose integer into two (hopefully prime) factors using the quadratic

func (*QuadraticSieve) GetFactor

func (qsieve *QuadraticSieve) GetFactor(n *math.Int) *math.Int

Find a factor of n. @param n - number to be factorized @return - factor of n (or nil)

type William_Pplus1

type William_Pplus1 struct{}

Find a factor of number n using Williams p+1 algorithm.

func (*William_Pplus1) GetFactor

func (f *William_Pplus1) GetFactor(n *math.Int) *math.Int

Williams p+1 algorithm @param n - number to be factorized @return - found factor (or nil)