common

Documentation

Index

• Variables
• func BigPow(a, b int) *big.Int
• func Pow(x, n int) (uint64, error)
• func PowBig(x, n int) *big.Int
• func PowMod(x, n, m int) int
• func ReadBits(bigint *big.Int, buf []byte)
• type StorageSize
  • func (s StorageSize) String() string
  • func (s StorageSize) TerminalString() string

Variables

var (
	Big0 = big.NewInt(0)

	// bigOne is 1 represented as a big.Int.  It is defined here to avoid
	// the overhead of creating it multiple times.
	Big1 = big.NewInt(1)

	Big2   = big.NewInt(2)
	Big256 = big.NewInt(0xff)

	MaxBig256 = new(big.Int).Set(tt256m1)

	MaxBig63 = new(big.Int).Sub(tt63, big.NewInt(1))
)

Functions

func BigPow

func BigPow(a, b int) *big.Int

BigPow returns a ** b as a big integer.

func Pow

func Pow(x, n int) (uint64, error)

Compute x^n by using the binary powering algorithm (aka. the repeated square-and-multiply algorithm) Reference: Knuth's The Art of Computer Programming, Volume 2, The Seminumerical Algorithms 4.6.3. Evaluation of Powers Suppose, for example, that we need to compute x^16; we could simply start with x and multiply by x fifteen times. But it is possible to obtain the same answer with only four multiplications, if we repeatedly take the square of each partial result, successively forming x^2, x^4, x^8, x^16. The same idea applies, in general, to any value of n, in the following way: Write n in the binary number system (suppressing zeros at the left). Then replace each “1” by the pair of letters SX, replace each “0” by S, and cross off the “SX” that now appears at the left. The result is a rule for computing x^n, if “S” is interpreted as the operation of squaring, and if “X” is interpreted as the operation of multiplying by x. For example, if n = 23, its binary representation is 10111; so we form the sequence SX S SX SX SX and remove the leading SX to obtain the rule SSXSXSX. This rule states that we should “square, square, multiply by x, square, multiply by x, square, and multiply by x”;

TODO : use Montgomery's ladder against side-channel attack Reference https://en.wikipedia.org/wiki/Exponentiation_by_squaring https://en.wikipedia.org/wiki/Exponentiation_by_squaring#Montgomery's_ladder_technique Montgomery, Peter L. (1987). "Speeding the Pollard and Elliptic Curve Methods of Factorization"

func PowBig

func PowBig(x, n int) *big.Int

only for showing algorithm compare to use BigPow 1000000 1621 ns/op BigPow 300000 4200 ns/op PowBig

func PowMod

func PowMod(x, n, m int) int

Compute x^n mod m by using the binary powering algorithm panic when m == 0

func ReadBits

func ReadBits(bigint *big.Int, buf []byte)

ReadBits encodes the absolute value of bigint as big-endian bytes. Callers must ensure that buf has enough space. If buf is too short the result will be incomplete.

Types

type StorageSize

type StorageSize float64

StorageSize is a wrapper around a float value that supports user friendly formatting.

func (StorageSize) String

func (s StorageSize) String() string

String implements the stringer interface.

func (StorageSize) TerminalString

func (s StorageSize) TerminalString() string

TerminalString implements log.TerminalStringer, formatting a string for console output during logging.