math

Documentation

Overview

Package math provides some utility functions for big integers.

Index

• func IsSafePrime(p *big.Int) bool
• func NextPow2(n uint) (N uint, k uint)
• func OmegaNAF(n *big.Int, w uint) (L []int32)
• func SafePrime(random io.Reader, bits int) (*big.Int, error)
• func SignedDigit(n *big.Int, w, l uint) []int32

Functions

func IsSafePrime

func IsSafePrime(p *big.Int) bool

IsSafePrime reports whether p is (probably) a safe prime. The prime p=2*q+1 is safe prime if both p and q are primes. Note that ProbablyPrime is not suitable for judging primes that an adversary may have crafted to fool the test.

func NextPow2

func NextPow2(n uint) (N uint, k uint)

NextPow2 finds the next power of two (N=2^k, k>=0) greater than n. If n is already a power of two, then this function returns n, and log2(n).

func OmegaNAF

func OmegaNAF(n *big.Int, w uint) (L []int32)

OmegaNAF obtains the window-w Non-Adjacent Form of a positive number n and 1 < w < 32. The returned slice L holds n = sum( L[i]*2^i ).

Reference:

• Alg.9 "Efficient arithmetic on Koblitz curves" by Solinas. http://doi.org/10.1023/A:1008306223194

func SafePrime

func SafePrime(random io.Reader, bits int) (*big.Int, error)

SafePrime returns a number of the given bit length that is a safe prime with high probability. The number returned p=2*q+1 is a safe prime if both p and q are primes. SafePrime will return error for any error returned by rand.Read or if bits < 2.

func SignedDigit

func SignedDigit(n *big.Int, w, l uint) []int32

SignedDigit obtains the signed-digit recoding of n and returns a list L of digits such that n = sum( L[i]*2^(i*(w-1)) ), and each L[i] is an odd number in the set {±1, ±3, ..., ±2^(w-1)-1}. The third parameter ensures that the output has ceil(l/(w-1)) digits.

Restrictions:

• n is odd and n > 0.
• 1 < w < 32.
• l >= bit length of n.

References:

• Alg.6 in "Exponent Recoding and Regular Exponentiation Algorithms" by Joye-Tunstall. http://doi.org/10.1007/978-3-642-02384-2_21
• Alg.6 in "Selecting Elliptic Curves for Cryptography: An Efficiency and Security Analysis" by Bos et al. http://doi.org/10.1007/s13389-015-0097-y