de.flexiprovider.common.math.ellipticcurves
Class ScalarMult

java.lang.Object
  |
  +--de.flexiprovider.common.math.ellipticcurves.ScalarMult

public final class ScalarMult

extends java.lang.Object

Method Summary

static int[][]	determineJsf(FlexiBigInt[] d) Returns the Joint Sparse Form of d0 to dk using algorithm 3 [PRO03].
static int[]	determineLtrFSSW(FlexiBigInt e, int w) Left to Right Fixed Size Sliding Window Recoding.
static int[]	determineLtrSFW(FlexiBigInt e, int m) Left to Right Signed Fractional Window Method proposed in [Moe04].
static int[]	determineMof(FlexiBigInt d) Returns the Mutual Opposite Form (MOF) of d proposed in [OSST04, Alg.
static int[]	determineMof(FlexiBigInt d, int w) Returns the Width-w Mutual Opposite Form (wMOF) of d proposed in [OSST04, Appendix B].
static int[]	determineNaf(FlexiBigInt e, int w) Returns e as int-array in non-adjacent-form (Naf).
static int[]	determineNaf(FlexiBigInt e, int w, int b) Returns e as int-array in non-adjacent-form (Naf).
static int[]	determineRtlFSSW(FlexiBigInt e, int w) Right to Left Fixed Size Sliding Window Recoding.
static int[]	determineRtlSFW(FlexiBigInt e, int m) Right to Left Signed Fractional Window Method proposed in [Moe04].
static int[][]	determineSimultaneous2w_ltr(FlexiBigInt d1, FlexiBigInt d2, int w) Returns the simultaneous2w recoding (Left to Right).
static int[][]	determineSimultaneous2w_rtl(FlexiBigInt d1, FlexiBigInt d2, int w) Returns the simultaneous2w recoding (Right to Left).
static int[][]	determineSimultaneousNaf(FlexiBigInt[] e, int[] w) returns the Naf-representations of the FlexiBigInts stored in e in one matrix.
static int[][]	determineSimultaneousSW(FlexiBigInt d1, FlexiBigInt d2, int w) Returns the simultaneous sliding window recoding.
static int[]	determineSW(FlexiBigInt e, int w) Sliding Window Recoding.
static int[][]	determineW3Jsf(FlexiBigInt e0, FlexiBigInt e1) Returns the w3-Joint Sparse Form (w3-JSF) of e0 and e1 using Algorithm 3 [DOT07]. The scalars e0 and e1 must have the same bitlength! Occuring digits are {0, 1, -1, 3, -3}.
static Point	eval_interleaving(int[][] N, Point[][] P) Interleave evaluation for n-time simultaneous multiplications with recoding
static Point	eval_shamir_all(int[][] N, Point[][] P) Shamir (= simultExpo) evaluation for simultaneous multiplications with recoding.
static Point	eval_shamir(int[][] N, Point[][] P) Shamir evaluation with 2 base points (e0*P0 + e1*P1).
static Point	eval_shamir(int[][] N, Point[][][] P) Shamir evaluation with 3 base points (e0*P0 + e1*P1 + e2*P2).
static Point	eval_shamir(int[][] N, Point[][][][] P) Shamir evaluation with 4 base points (e0*P0 + e1*P1 + e2*P2 + e3*P3).
static Point	eval_shamir(Point P, Point Q, FlexiBigInt e1, FlexiBigInt e2) Shamir (= simultExpo) evaluation for simultaneous multiplications without recoding.
static Point	eval_SquareMultiply_all(int[] N, Point[] P) Square and multiply evaluation with recoding.
static Point	eval_SquareMultiply(FlexiBigInt m, Point p) Square and multiply evaluation without recoding.
static Point	eval_SquareMultiply(int[] N, Point[] P) Square and multiply evaluation with recoding.
static Point	multiply(FlexiBigInt[] b, Point[] p) Returns the result of the simultaneous scalarmultiplication b0*P0 + b1*P1 + ...
static Point	multiply(FlexiBigInt b, Point p) Multiplies this point with the scalar b.
static Point	multiply2(FlexiBigInt[] b, Point[] p)
static Point	multiply2(FlexiBigInt b, Point p)
static Point	multiply3(FlexiBigInt[] b, Point[] p)
static Point	multiply3(FlexiBigInt b, Point p)
static Point	multiply4(FlexiBigInt[] b, PointGFP[] p)
static Point	multiply4(FlexiBigInt b, PointGFP p)
static Point[]	pre_allpowers(Point p, int w) This method computes all positive powers which are smaller than 2w.
static Point[]	pre_limlee(Point p, FlexiBigInt m, int n) LimLee precomputation.
static Point[]	pre_limleeAffine(Point p, FlexiBigInt m, int n) LimLee affine precomputation.
static Point[][]	pre_oddpowers(Point[] Q, int[] W) This method computes all positive odd powers of all points given in array Q.
static Point[]	pre_oddpowers(Point p, int w) This method computes all positive odd powers which are smaller than 2w.
static Point[][]	pre_shamir(Point Q0, Point Q1, int w) This method computes the simultaneous powers i*Q0 + j*Q1, (i,j odd) required by the Shamir evaluation.
static Point[][][]	pre_shamir(Point Q0, Point Q1, Point Q2, int w) This method computes the simultaneous powers i*Q0 + j*Q1 + k*Q2, (i,j,k odd) required by the Shamir evaluation.
static Point[][][][]	pre_shamir(Point Q0, Point Q1, Point Q2, Point Q3, int w) This method computes the simultaneous powers i*Q0 + j*Q1 + k*Q2 + m*Q3, (i,j,k,m odd) required by the Shamir evaluation.
static Point[][]	pre_shamirGFP(PointGFP q0, PointGFP q1, int w) Precomputation in affine coordinates using the Montgomery trick to invert the denominators of all lambdas. This method computes the simultaneous powers i*Q0 + j*Q1 required by the Shamir evaluation.
static Point[][]	pre_simultaneous2w(Point P, Point Q, int w) This method computes the simultaneous powers i*P + j*Q required by the simultaneous 2w-ary-method.
static Point[][]	pre_simultaneousSlidingWindow(Point P, Point Q, int w) This method computes the simultaneous powers i*P + j*Q required by the simultaneous sliding window method.
static Point[]	precomputation(Point p, int w, int k)
static Point[]	precomputationCMO(PointGF2n p, int w) If k = 0 and w != 0 this method precomputes all odd points 3P, 5P, 7P,..., (2w-1 -1)P in affine coordinates, whereas P = point.
static Point[]	precomputationCMO(PointGFP p, int w, int k) If k = 0 and w != 0 this method precomputes all odd points 3P, 5P, 7P,..., (2w-1 -1)P in affine coordinates, whereas P = point.
static Point[]	precomputationCMO(Point p, int w, int k)
static PointGFP[]	precomputationDOS(PointGFP point, int k)
static FlexiBigInt[]	split_limlee(FlexiBigInt m, int n) LimLee splitting.

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

multiply

public static Point multiply(FlexiBigInt b,
                             Point p)

Multiplies this point with the scalar b. Naf-recoding (w = 4) and CMO-Precomputation will be used.

Parameters:

b - FlexiBigInt

p - base point

Returns:

b*p

multiply2

public static Point multiply2(FlexiBigInt b,
                              Point p)

multiply3

public static Point multiply3(FlexiBigInt b,
                              Point p)

multiply4

public static Point multiply4(FlexiBigInt b,
                              PointGFP p)

multiply

public static Point multiply(FlexiBigInt[] b,
                             Point[] p)

Returns the result of the simultaneous scalarmultiplication b₀*P₀ + b₁*P₁ + ... + b_n-1*P_n-1.
This method uses Naf-recoding (w = 4), CMO-Precomputation and the interleaving method.

Parameters:

p - Array of base points

b - Array of FlexiBigInt

Returns:

b₀*P₀ + b₁*P₁ + ... + b_n-1*P_n-1

multiply2

public static Point multiply2(FlexiBigInt[] b,
                              Point[] p)

multiply3

public static Point multiply3(FlexiBigInt[] b,
                              Point[] p)

multiply4

public static Point multiply4(FlexiBigInt[] b,
                              PointGFP[] p)

pre_allpowers

public static Point[] pre_allpowers(Point p,
                                    int w)

This method computes all positive powers which are smaller than 2^w. This precomputation is used by representations which have positive, arbitrary digits. An Example is Fixed Size Sliding Window.

Parameters:

p - base point

w - upper bound/ window width

Returns:

i*p for i = 0, 1, 2,..., 2^w - 1;
P[i] = (i + 1)*p

pre_oddpowers

public static Point[] pre_oddpowers(Point p,
                                    int w)

This method computes all positive odd powers which are smaller than 2^w. It is useful for representations which use odd digits. Examples are Naf, Sliding Window or Mof.

Parameters:

p - base point

w - upper bound/ window width

Returns:

i*p for i = 0, 1, 3,..., 2^w - 1;
P[i] = (2i + 1)*p

pre_oddpowers

public static Point[][] pre_oddpowers(Point[] Q,
                                      int[] W)

This method computes all positive odd powers of all points given in array Q. The corresponding window widthes must be provided by an array W. For every Point P[i], all odd powers are computed which are smaller than 2^W[i].
Note that (W.length = Q.length) is required.
This method returns a matrix Pre[][]. A certain precomputation of P[i] is found in Pre[i].

Parameters:

Q - base point array. All points must be on the same elliptic curve.

W - upper bound array. W[i] is the upper bound for P[i].

Returns:

Point matrix with e.length lines and 2^w columns.
The odd powers of Q[i] are stored in line i;

precomputation

public static Point[] precomputation(Point p,
                                     int w,
                                     int k)

precomputationCMO

public static Point[] precomputationCMO(Point p,
                                        int w,
                                        int k)

precomputationCMO

public static Point[] precomputationCMO(PointGFP p,
                                        int w,
                                        int k)

If k = 0 and w != 0 this method precomputes all odd points 3P, 5P, 7P,..., (2^w-1 -1)P in affine coordinates, whereas P = point.

If k != 0 and w = 0 this method precomputes all odd points 3P, 5P, 7P,..., (2k-1)P in affine coordinates, whereas P = point.

This method computes these points with the algorithm thas was proposed in Cohen, H., Miyaji, A., and Ono, T. Efficient Elliptic Curve Exponentiation Using Mixed Coordinates. 1998

The elements of the returned array are as followed:

w != 0, k = 0		w = 0, k != 0		w != 0, k != 0
array[0] = P		array[0] = P		array[0] = P
array[1] = 3P		array[1] = 3P
array[2] = 5P		array[2] = 5P
...		...
array[(2w-2)-1] = (2w-1 -1)P		array[k-1] = (2k-1)P

Parameters:

p - the point of the scalar multiplication

w - window size

k - the number of points to compute

Returns:

Returns an array with the precomputed points in affine coordinates

precomputationCMO

public static Point[] precomputationCMO(PointGF2n p,
                                        int w)

If k = 0 and w != 0 this method precomputes all odd points 3P, 5P, 7P,..., (2^w-1 -1)P in affine coordinates, whereas P = point.

If k != 0 and w = 0 this method precomputes all odd points 3P, 5P, 7P,..., (2k-1)P in affine coordinates, whereas P = point.

This method computes these points with the algorithm thas was proposed in Cohen, H., Miyaji, A., and Ono, T. Efficient Elliptic Curve Exponentiation Using Mixed Coordinates. 1998

The elements of the returned array are as followed:

w != 0, k = 0		w = 0, k != 0		w != 0, k != 0
array[0] = P		array[0] = P		array[0] = P
array[1] = 3P		array[1] = 3P
array[2] = 5P		array[2] = 5P
...		...
array[(2w-2)-1] = (2w-1 -1)P		array[k-1] = (2k-1)P

Parameters:

p - the point of the scalar multiplication

w - window size

Returns:

Returns an array with the precomputed points in affine coordinates

precomputationDOS

public static PointGFP[] precomputationDOS(PointGFP point,
                                           int k)

pre_simultaneous2w

public static Point[][] pre_simultaneous2w(Point P,
                                           Point Q,
                                           int w)

This method computes the simultaneous powers i*P + j*Q required by the simultaneous 2^w-ary-method. Since this method uses digits in {0,1,2,...,2^w-1}, all those simultanteous powers are needed.

Parameters:

P - base point

Q - base point

w - window size (parameter of the simultaneous 2^w-ary-method)

Returns:

Point matrix with p[i][j] = i*P + j*Q for i,j = 0,1,2,...,2^w-1

pre_simultaneousSlidingWindow

public static Point[][] pre_simultaneousSlidingWindow(Point P,
                                                      Point Q,
                                                      int w)

This method computes the simultaneous powers i*P + j*Q required by the simultaneous sliding window method. Only those powers are computed, where i and j are not even on the same time. The returned matrix is a subset of the matrix computed by pre_simultaneous2w.

Parameters:

P - base point

Q - base point

w - window size (parameter of the simultaneous sliding window method)

Returns:

Point matrix p[i][j] = i*P + j*Q for i,j not both even and i,j < 2^w

pre_shamir

public static Point[][] pre_shamir(Point Q0,
                                   Point Q1,
                                   int w)

This method computes the simultaneous powers i*Q₀ + j*Q₁, (i,j odd) required by the Shamir evaluation. In this method, only the use of representations with odd (positive and negative) digits is supported.

Parameters:

Q0 - base point

Q1 - base point

w - recoding parameter / upper bound. This parameter will be used for all points.

Returns:

2-dimensional point matrix P[i][j].
P[i][.] = i*Q₀ + ... if i is odd;
P[i][.] = (-i + 1)Q₀ + ... if i is even;
P[0][.] = 0*Q₀ + ...
Example 1: P[3][4] = 3*Q₀ - 3*Q₁
Example 2: P[7][5] = 7*Q₀ + 5*Q₁
The scalars i, j are restricted to i, j = 0,+1,-1,...,2^w-1,-2^w+1.

pre_shamirGFP

public static Point[][] pre_shamirGFP(PointGFP q0,
                                      PointGFP q1,
                                      int w)

Precomputation in affine coordinates using the Montgomery trick to invert the denominators of all lambdas.
This method computes the simultaneous powers i*Q₀ + j*Q₁ required by the Shamir evaluation. In this method, only the use of representations with odd (positive and negative) digits is supported.

Parameters:

q0 - base point

q1 - base point

w - recoding parameter / upper bound

Returns:

2-dimensional point matrix P[i][j].
P[i][.] = i*Q₀ + ... if i is odd;
P[i][.] = (-i + 1)*Q₀ + ... if i is even;
P[0][.] = 0*Q₀ + ...
Example 1: P[3][4] = 3*Q₀ - 3*Q₁
Example 2: P[7][5] = 7*Q₀ + 5*Q₁
The scalars i, j are restricted to i, j = 0,+1,-1,...,2^w-1,-2^w+1.

pre_shamir

public static Point[][][] pre_shamir(Point Q0,
                                     Point Q1,
                                     Point Q2,
                                     int w)

This method computes the simultaneous powers i*Q₀ + j*Q₁ + k*Q₂, (i,j,k odd) required by the Shamir evaluation. In this method, only the use of representations with odd (positive and negative) digits is supported.

Parameters:

Q0 - base point

Q1 - base point

Q2 - base point

w - recoding parameter / upper bound. This parameter will be used for all points.

Returns:

3-dimensional point matrix P[i][j][k].
P[i][.][.] = i*Q₀ + ... if i is odd;
P[i][.][.] = (-i + 1)Q₀ + ... if i is even;
P[0][.][.] = 0*Q₀ + ...
Example 1: P[3][4][5] = 3*Q₀ - 3*Q₁ + 5*Q₂
Example 2: 7*Q₀ + 5*Q₁ - 3*Q₂ is stored in P[7][5][4].
The scalars i, j, k are restricted to i, j, k = 0,+1,-1,...,2^w-1,-2^w+1.

pre_shamir

public static Point[][][][] pre_shamir(Point Q0,
                                       Point Q1,
                                       Point Q2,
                                       Point Q3,
                                       int w)

This method computes the simultaneous powers i*Q₀ + j*Q₁ + k*Q₂ + m*Q₃, (i,j,k,m odd) required by the Shamir evaluation. In this method, only the use of representations with odd (positive and negative) digits is supported.

Parameters:

Q0 - base point

Q1 - base point

Q2 - base point

Q3 - base point

w - recoding parameter / upper bound. This parameter will be used for all points.

Returns:

4-dimensional point matrix P[i][j][k][m].
P[i][.][.][.] = i*Q₀ + ... if i is odd;
P[i][.][.][.] = (-i + 1)Q₀ + ... if i is even;
P[0][.][.][.] = 0*Q₀ + ...
Example: P[3][4][5][6] = 3*Q₀ - 3*Q₁ + 5*Q₂ - 5*Q₃
The scalars i, j, k, m are restricted to i, j, k, m = 0,+1,-1,...,2^w-1,-2^w+1.

pre_limlee

public static Point[] pre_limlee(Point p,
                                 FlexiBigInt m,
                                 int n)

LimLee precomputation. Compute the powers 2^l*i*p (i=0, 1,...,n-1).

Parameters:

p - base point

m - FlexiBigInt

n - LimLee parameter (number of the splitted pieces)

Returns:

point array. P[i] = 2^l*i*p

pre_limleeAffine

public static Point[] pre_limleeAffine(Point p,
                                       FlexiBigInt m,
                                       int n)

LimLee affine precomputation. This method computes the powers 2^l*i*p (i=0, 1,...,n-1).

Parameters:

p - base point

m - FlexiBigInt

n - LimLee parameter (number of the splitted pieces)

Returns:

point array. P[i] = 2^l*i*p

split_limlee

public static FlexiBigInt[] split_limlee(FlexiBigInt m,
                                         int n)

LimLee splitting. This method divides the scalar into n pieces of length l. if needed, some zeros will be padded on m.

Parameters:

m - FlexiBigInt

n - LimLee parameter (number of the splitted pieces)

Returns:

array of FlexiBigInts s.t. m = P[n - 1] ||...||P[1]||P[0]

determineNaf

public static int[] determineNaf(FlexiBigInt e,
                                 int w,
                                 int b)

Returns e as int-array in non-adjacent-form (Naf).

Parameters:

e - the FlexiBigInt that is to be converted

w - the entries n of the Nafs are smaller than 2^w

b - BitLength of e

Returns:

e in non-adjacent-form as int-array

determineNaf

public static int[] determineNaf(FlexiBigInt e,
                                 int w)

Returns e as int-array in non-adjacent-form (Naf).

Parameters:

e - the FlexiBigInt that is to be converted

w - the entries n of the Nafs are smaller than 2^w

Returns:

e in non-adjacent-form as int-array

determineRtlFSSW

public static int[] determineRtlFSSW(FlexiBigInt e,
                                     int w)

Right to Left Fixed Size Sliding Window Recoding. This recoding uses digits in {0,1,2,...,2^w-1} and runs from the LSB to the MSB (Right-to-Left).

Parameters:

e - FlexiBigInt to be recoded

w - window size.

Returns:

int-array representing the recoding

determineLtrFSSW

public static int[] determineLtrFSSW(FlexiBigInt e,
                                     int w)

Left to Right Fixed Size Sliding Window Recoding. This recoding uses digits in {0,1,2,...,2^w-1} and runs from the MSB to the LSB (Left-to-Right).

Parameters:

e - FlexiBigInt to be recoded

w - window size

Returns:

int-array representing the recoding

determineSW

public static int[] determineSW(FlexiBigInt e,
                                int w)

Sliding Window Recoding. This is a Left-to-Right method using the digits {0, 1, 3,..., 2^w - 1}.

Parameters:

e - FlexiBigInt to be recoded

w - window size

Returns:

int-array representing the recoding

determineRtlSFW

public static int[] determineRtlSFW(FlexiBigInt e,
                                    int m)

Right to Left Signed Fractional Window Method proposed in [Moe04]. The occuring digits are {0, 1, -1, 3, -3,..., m, -m} (m must be odd!).

Parameters:

e - FlexiBigInt to be recoded

m - odd integer

Returns:

int-array representing the recoding

determineLtrSFW

public static int[] determineLtrSFW(FlexiBigInt e,
                                    int m)

Left to Right Signed Fractional Window Method proposed in [Moe04]. The occuring digits are {0, 1, -1, 3, -3,..., m, -m} (m must be odd!).

Parameters:

e - FlexiBigInt to be recoded

m - odd integer

Returns:

int-array representing the recoding

determineMof

public static int[] determineMof(FlexiBigInt d,
                                 int w)

Returns the Width-w Mutual Opposite Form (wMOF) of d proposed in [OSST04, Appendix B]. This recoding uses digits in {0, 1, -1, 3, -3,..., 2^{w - 1} - 1}.

Parameters:

d - FlexiBigInt to be recoded

w - window width (parameter of wMOF)

Returns:

int-array representing the recoding

determineMof

public static int[] determineMof(FlexiBigInt d)

Returns the Mutual Opposite Form (MOF) of d proposed in [OSST04, Alg. 2]. All digits are in {0, 1, -1}.

Parameters:

d - FlexiBigInt to be recoded

Returns:

int-array representing the recoding

determineJsf

public static int[][] determineJsf(FlexiBigInt[] d)

Returns the Joint Sparse Form of d₀ to d_k using algorithm 3 [PRO03]. This recoding uses digits in {0, 1, -1}.

Parameters:

d - Array of FlexiBigInt

Returns:

int-matrix.
line i contains the recoded representation of d_i.

determineW3Jsf

public static int[][] determineW3Jsf(FlexiBigInt e0,
                                     FlexiBigInt e1)

Returns the w3-Joint Sparse Form (w3-JSF) of e₀ and e₁ using Algorithm 3 [DOT07].
The scalars e₀ and e₁ must have the same bitlength!
Occuring digits are {0, 1, -1, 3, -3}.

Parameters:

e0 - FlexiBigInt

e1 - FlexiBigInt

Returns:

2-lined matrix.
line 0 contains the recoded representation of e₀;
line 1 contains the recoded representation of e₁.

determineSimultaneous2w_rtl

public static int[][] determineSimultaneous2w_rtl(FlexiBigInt d1,
                                                  FlexiBigInt d2,
                                                  int w)

Returns the simultaneous2w recoding (Right to Left). The separate recodings are equal to determineRtlFSSW.

Parameters:

d1 - FlexiBigInt

d2 - FlexiBigInt

w - window size

Returns:

2-lined matrix.
line 0 contains the recoded representation of d₁;
line 1 contains the recoded representation of d₂.

determineSimultaneous2w_ltr

public static int[][] determineSimultaneous2w_ltr(FlexiBigInt d1,
                                                  FlexiBigInt d2,
                                                  int w)

Returns the simultaneous2w recoding (Left to Right). If d₁ and d₂ have the same bitlength, the separate recodings are equal to determineLtrFSSW.

Parameters:

d1 - FlexiBigInt

d2 - FlexiBigInt

w - window size

Returns:

2-lined matrix.
line 0 contains the recoded representation of d₁;
line 1 contains the recoded representation of d₂.

determineSimultaneousSW

public static int[][] determineSimultaneousSW(FlexiBigInt d1,
                                              FlexiBigInt d2,
                                              int w)

Returns the simultaneous sliding window recoding. Attention: The result does not coincide with the classical sliding window method. Even digits may occur.
A special precomputation can be found here.

Parameters:

d1 - FlexiBigInt

d2 - FlexiBigInt

w - window size

Returns:

2-lined matrix.
line 0 contains the recoded representation of d₁;
line 1 contains the recoded representation of d₂.

determineSimultaneousNaf

public static int[][] determineSimultaneousNaf(FlexiBigInt[] e,
                                               int[] w)

returns the Naf-representations of the FlexiBigInts stored in e in one matrix.

Parameters:

e - array of FlexiBigInts to be recoded

w - wNaf parameters. For the recoding of e[i], w[i] will be used.

Returns:

matrix. Line i contains the wNaf-representation of e_i.

eval_SquareMultiply

public static Point eval_SquareMultiply(FlexiBigInt m,
                                        Point p)

Square and multiply evaluation without recoding. This is also known by binary method or fast exponentiation. This method returns m*p.

Parameters:

m - FlexiBigInt

p - base point

Returns:

m*p

eval_SquareMultiply

public static Point eval_SquareMultiply(int[] N,
                                        Point[] P)

Square and multiply evaluation with recoding. This is also known by binary method or fast exponentiation. This method returns m*p. This variant requires a recoding that uses only odd digits. The corresponding positive powers must be stored in P.

Parameters:

N - the recoded scalar as int-array

P - array with the precomputed positive odd powers.
P[i] = (2i + 1)*p

Returns:

m*p

eval_SquareMultiply_all

public static Point eval_SquareMultiply_all(int[] N,
                                            Point[] P)

Square and multiply evaluation with recoding. This is also known by binary method or fast exponentiation. This method returns m*p. This variant requires a recoding that uses only positive digits. It needs to have all positive powers of p stored in P.

Parameters:

N - the recoded scalar as int-array

P - array with the precomputed positive powers.
P[i] = (i + 1)*p

Returns:

m*p

eval_shamir

public static Point eval_shamir(Point P,
                                Point Q,
                                FlexiBigInt e1,
                                FlexiBigInt e2)

Shamir (= simultExpo) evaluation for simultaneous multiplications without recoding. This method returns e1*P + e2*Q.

Parameters:

P - base point

Q - base point

e1 - FlexiBigInt

e2 - FlexiBigInt

Returns:

e1*P + e2*Q

eval_shamir_all

public static Point eval_shamir_all(int[][] N,
                                    Point[][] P)

Shamir (= simultExpo) evaluation for simultaneous multiplications with recoding. The representations of the scalars must have positive digits.

Parameters:

N - 2-lined matrix.
line 0 contains the recoded representation of e₁;
line 1 contains the recoded representation of e₂.

P - matrix with the precomputed powers.
p[i][j] = i*P + j*Q for i,j = 0,1,2,...,2^w-1 or similar

Returns:

e1*P + e2*Q

eval_shamir

public static Point eval_shamir(int[][] N,
                                Point[][] P)

Shamir evaluation with 2 base points (e0*P₀ + e1*P₁). In this method, only the use of representations with odd (positive and negative) digits is supported.

Parameters:

N - 2-lined matrix.
line i contains the recoded representation of e_i;

P - matrix with the precomputed powers. Use the Shamir precomputation.

Returns:

e0*P₀ + e1*P₁

eval_shamir

public static Point eval_shamir(int[][] N,
                                Point[][][] P)

Shamir evaluation with 3 base points (e0*P₀ + e1*P₁ + e2*P₂). In this method, only the use of representations with odd (positive and negative) digits is supported.

Parameters:

N - 3-lined matrix.
line i contains the recoded representation of e_i;

P - matrix with the precomputed powers. Use the Shamir precomputation.

Returns:

e0*P₀ + e1*P₁ + e2*P₂

eval_shamir

public static Point eval_shamir(int[][] N,
                                Point[][][][] P)

Shamir evaluation with 4 base points (e0*P₀ + e1*P₁ + e2*P₂ + e3*P₃). In this method, only the use of representations with odd (positive and negative) digits is supported.

Parameters:

N - 4-lined matrix.
line i contains the recoded representation of e_i;

P - matrix with the precomputed powers. Use the Shamir precomputation.

Returns:

e0*P₀ + e1*P₁ + e2*P₂ + e3*P₃

eval_interleaving

public static Point eval_interleaving(int[][] N,
                                      Point[][] P)

Interleave evaluation for n-time simultaneous multiplications with recoding

Parameters:

N - matrix with the receoded representations.
Line i contains the wNaf-representation of e_i.

P - point matrix with the precomputed points.
The odd powers of P_i are stored in line i.

Returns:

e₀*P₀ + e₁*P₁ + ... + e_n-1*P_n-1