Curve25519-dalek-ng

https://github.com/zkcrypto/curve25519-dalek-ng
Admin
A pure-Rust implementation of group operations on Ristretto and Curve25519, providing a safe...
Tokens:12,874
Snippets:33
Trust Score:6.7
Update:1 year ago
Show doc for...
Tokens:
Raw
### Select Arithmetic Backend

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/README.md

Examples of how to select a specific arithmetic backend for curve25519-dalek-ng using Cargo build commands and feature flags. Requires `--no-default-features`.

```sh
# Build with u32 backend
CARGO_PROFILE_DEV_OVERRIDE_DEBUG=true cargo build --no-default-features --features "std u32_backend"

# Build with u64 backend (default)
CARGO_PROFILE_DEV_OVERRIDE_DEBUG=true cargo build --no-default-features --features "std u64_backend"

# Build with AVX2 backend (requires nightly and target feature)
CARGO_PROFILE_DEV_OVERRIDE_DEBUG=true RUSTFLAGS="-C target_feature=+avx2" cargo build --no-default-features --features "std simd_backend"

# Build with IFMA backend (requires nightly and target feature)
CARGO_PROFILE_DEV_OVERRIDE_DEBUG=true RUSTFLAGS="-C target_feature=+avx512ifma" cargo build --no-default-features --features "std simd_backend"
```

--------------------------------

### Build Documentation

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/README.md

Commands to build the project's documentation, including internal implementation details. Requires a custom HTML header for math support (KaTeX).

```sh
make doc
make doc-internal
```

--------------------------------

### Benchmarking curve25519-dalek-ng

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/README.md

Commands to run benchmarks for curve25519-dalek-ng using different backends and features. It demonstrates how to enable specific features like 'std', 'u32_backend', 'u64_backend', and 'simd_backend', and how to set RUSTFLAGS for CPU-specific optimizations.

```sh
cargo bench --no-default-features --features "std u32_backend"
cargo bench --no-default-features --features "std u64_backend"
# Uses avx2 or ifma only if compiled for an appropriate target.
export RUSTFLAGS="-C target_cpu=native"
cargo bench --no-default-features --features "std simd_backend"
```

--------------------------------

### Switch to curve25519-dalek-ng from curve25519-dalek

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/README.md

How to use the curve25519-dalek-ng crate with the same package name as the previous curve25519-dalek crate, ensuring compatibility.

```toml
curve25519-dalek = { package = "curve25519-dalek-ng", version = "4" }
```

--------------------------------

### Performance Considerations for Additions/Subtractions and Doubling

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Discusses the diminishing returns of optimizations when additions and subtractions are not accelerated. It notes that doubling is slower than readdition due to formula complications, suggesting a need for different strategies for larger vector sizes.

```math
No speedup to additions and subtractions leads to diminishing returns.
Doubling is slower than readdition due to formula complications.
Moving to 512-bit vectors requires a parallel-friendly multiscalar multiplication algorithm for performance gains.
```

--------------------------------

### Potential LLVM Optimizations

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Highlights potential performance improvements by leveraging LLVM features, specifically mentioning the omission of blend instructions once LLVM supports blend operations on 256-bit vectors.

```rust
// LLVM won't use blend operations on [256-bit vectors] yet
// so there's a bunch of blend instructions that could be omitted.
```

--------------------------------

### Dependency Management for Parallelism

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Discusses the design choice to compute contributions independently to maximize Instruction-Level Parallelism (ILP), contrasting it with a method that would introduce dependencies between terms, potentially reducing performance.

```design
// Strategy: Compute all contributions to all terms independently.
// Benefit: Maximizes ILP and allows flexible scheduling by the processor.
// Alternative: Carrying high parts of z_i to z_{i+1} creates dependencies,
//              reducing parallelism but potentially reducing multiplications.
```

--------------------------------

### Optimization using IFMA and vpmullq

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Compares the use of Intel Fused Multiply-Add (IFMA) operations versus the vpmullq instruction for multiplying by 19 during modular reduction. IFMA offers better latency and throughput for this specific task.

```assembly
; IFMA operation: 4c/0.5c latency/throughput
; vpmullq instruction: 15c/1.5c latency/throughput

; Example of IFMA usage for 19 * z_i' mod p:
; 19 * z_i' = lo(19, z_i') + 2 * hi(19, z_i') * 2^51
```

--------------------------------

### Modified Parallel Addition Formula (SIMD-friendly)

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/parallel-formulas.md

Presents a SIMD-friendly version of the parallel addition formula for elliptic curve points, adapted from HWCD'08. It details the steps using temporary variables S_i and the cost in terms of multiplications (M) and divisions/constant multiplications (D).

```APIDOC
Modified Parallel Addition Formula (SIMD-friendly):

To add points P1 = (X1 : Y1 : Z1 : T1) and P2 = (X2 : Y2 : Z2 : T2), compute:

1. (S_0, S_1, S_2, S_3) = (Y1 - X1, Y1 + X1, Y2 - X2, Y2 + X2)
2. (S_4, S_5, S_6, S_7) = (S_0 * S_2, S_1 * S_3, Z1 * Z2, T1 * T2)
3. (S_8, S_9, S_10, S_11) = (d2 * S_4, d2 * S_5, 2*d2 * S_6, 2*d1 * S_7)
   (where d = d1/d2 is the curve constant)
4. (S_12, S_13, S_14, S_15) = (S_9 - S_8, S_9 + S_8, S_10 - S_11, S_10 + S_11)
5. (X_3, Y_3, Z_3, T_3) = (S_12 * S_14, S_15 * S_13, S_15 * S_14, S_12 * S_13)

This results in P3 = P1 + P2 and costs 2*M + 1*D (where D is multiplication by a curve constant).
```

--------------------------------

### Add curve25519-dalek-ng to Cargo.toml

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/README.md

Instructions for adding the curve25519-dalek-ng crate as a dependency to your Rust project's Cargo.toml file.

```toml
curve25519-dalek-ng = "4.1"
```

--------------------------------

### Curve25519 Squaring Algorithm

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Details the schoolbook squaring algorithm for Curve25519, showing the expansion of the product terms and the substitution of lo/hi components. It outlines the grouping of terms by coefficient for efficient computation.

```math
x = x_0 + x_1 2^{51} + x_2 2^{102} + x_3 2^{153} + x_4 2^{204}

z = z_0 + z_1 2^{51} + z_2 2^{102} + z_3 2^{153} + z_4 2^{204} + z_5 2^{255} + z_6 2^{306} + z_7 2^{357} + z_8 2^{408} + z_9 2^{459}

z_0 =   x_0 x_0
z_1 = 2 x_1 x_0
z_2 = 2 x_2 x_0 +   x_1 x_1
z_3 = 2 x_3 x_0 + 2 x_2 x_1
z_4 = 2 x_4 x_0 + 2 x_3 x_1 + x_2 x_2
z_5 = 2 x_4 x_1 + 2 x_3 x_2
z_6 = 2 x_4 x_2 +   x_3 x_3
z_7 = 2 x_4 x_3
z_8 =   x_4 x_4
z_9 = 0

where x_i x_j = lo(x_i,x_j) + 2*hi(x_i,x_j)*2^{51}
```

--------------------------------

### Curve25519 Squaring Implementation Details

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Explains the strategy for implementing the squaring algorithm by grouping terms based on their coefficients (e.g., 2, 4) and processing them using IFMA chains and shifts. This approach aims to optimize the computation.

```math
Group terms by coefficient (2, 4, etc.).
Process coefficient-2 terms on IFMA chains.
Process coefficient-4 terms, then shift left, then process coefficient-1 terms.
Reduction strategy is the same as for multiplication.
```

--------------------------------

### HWCD'08 Unified Addition Formula

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/parallel-formulas.md

Details the unified addition algorithm for elliptic curve points as presented in the HWCD'08 paper, showing the parallel execution across four processors and the associated costs.

```APIDOC
Unified Addition Formula (HWCD'08):

| Cost             | Processor 1                    | Processor 2                    | Processor 3                    | Processor 4                    |
|------------------|--------------------------------|--------------------------------|--------------------------------|--------------------------------|
|                  | \( R_1 \gets Y_1 - X_1 \) | \( R_2 \gets Y_2 - X_2 \) | \( R_3 \gets Y_1 + X_1 \) | \( R_4 \gets Y_2 + X_2 \) |
| \(1\mathbf M\) | \( R_5 \gets R_1 R_2 \)   | \( R_6 \gets R_3 R_4 \)   | \( R_7 \gets T_1 T_2 \)   | \( R_8 \gets Z_1 Z_2 \)   |
| \(1\mathbf D\) | idle                           | idle                           | \( R_7 \gets k R_7 \)      | \( R_8 \gets 2 R_8 \)      |
|                  | \( R_1 \gets R_6 - R_5 \) | \( R_2 \gets R_8 - R_7 \) | \( R_3 \gets R_8 + R_7 \) | \( R_4 \gets R_6 + R_5 \) |
| \(1\mathbf M\) | \( X_3 \gets R_1 R_2 \)   | \( Y_3 \gets R_3 R_4 \)   | \( T_3 \gets R_1 R_4 \)   | \( Z_3 \gets R_2 R_3 \)   |
```

--------------------------------

### Parallel Formulas for Edwards Curves

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/parallel-formulas.md

Explains the 4-way parallel formulas for point addition and doubling on Edwards curves as described in HWCD08. It covers a unified addition algorithm, a doubling algorithm, and a dedicated addition algorithm, comparing them to Montgomery ladder variants.

```APIDOC
Hisil, Wong, Carter, Dawson (HWCD) 4-way Parallel Formulas:

1. Unified Addition Algorithm:
   - Complexity: 2M + 1D (M=multiplication, D=squaring)
   - Description: Handles addition of two distinct points.

2. Doubling Algorithm:
   - Complexity: 1M + 1S (S=squaring)
   - Description: Efficiently doubles a point.

3. Dedicated Addition Algorithm:
   - Complexity: 2M
   - Description: Optimized for adding two distinct points.

Comparison:
- These parallel formulas are compared with a 2-way parallel Montgomery ladder.
- Unlike serial formulas, their software implementation was not common due to synchronization challenges.
- SIMD implementation strategy involves uniform execution of expensive steps (multiplication, squaring) and masking for divergence in cheaper steps (addition, subtraction).
```

--------------------------------

### Schoolbook Multiplication Strategy

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Details the 'schoolbook' multiplication strategy for big integers represented in a redundant 52-bit format. It shows how product coefficients \(z_k\) are formed by summing products of \(x_i\) and \(y_j\) where \(i+j=k\).

```mathematica
z = z_0 + z_1 2^{52} + z_2 2^{104} + \\cdots \\

&z_0   &&= x_0      &   y_0    &           &          &           &          &          &        &       \\ 
&z_1   &&= x_1      &   y_0    &+ x_0      &   y_1    &           &          &           &          &        &       \\ 
&z_2   &&= x_2      &   y_0    &+ x_1      &   y_1    &+ x_0      &   y_2    &           &          &        &       \\ 
&z_3   &&= x_3      &   y_0    &+ x_2      &   y_1    &+ x_1      &   y_2    &+ x_0      &   y_3    &        &       \\ 
&z_4   &&= \vdots\;&\;\vdots &+ x_3      &   y_1    &+ x_2      &   y_2    &+ x_1      &   y_3    &+ \cdots&       \\ 
&z_5   &&=          &          &  \vdots\;&\;\vdots &+ x_3      &   y_2    &+ x_2      &   y_3    &+ \cdots&       \\ 
&z_6   &&=          &          &           &          &  \vdots\;&\;\vdots &+ x_3      &   y_3    &+ \cdots&       \\ 
&z_7   &&=          &          &           &          &           &          &  \vdots\;&\;\vdots &+ \cdots&       \\ 
&\vdots&&=          &          &           &          &           &          &           &          &  \\ddots&       \\
```

--------------------------------

### IFMA Operation Breakdown

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Illustrates how each product term x_i * y_j can be represented using IFMA (Integer Fused Multiply-Add) operations, specifically lo() and hi() components, and how these are substituted back into the multiplication equations.

```mathematics
x_i y_j = lo(x_i,y_j) + 2*hi(x_i,y_j)*2^51

z_0 = lo(x_0, y_0)
z_1 = lo(x_1, y_0) + lo(x_0, y_1) + 2*( hi(x_0, y_0) )
z_2 = lo(x_2, y_0) + lo(x_1, y_1) + lo(x_0, y_2) + 2*( hi(x_1, y_0) + hi(x_0, y_1) )
z_3 = lo(x_3, y_0) + lo(x_2, y_1) + lo(x_1, y_2) + lo(x_0, y_3) + 2*( hi(x_2, y_0) + hi(x_1, y_1) + hi(x_0, y_2) )
z_4 = lo(x_4, y_0) + lo(x_3, y_1) + lo(x_2, y_2) + lo(x_1, y_3) + lo(x_0, y_4) + 2*( hi(x_3, y_0) + hi(x_2, y_1) + hi(x_1, y_2) + hi(x_0, y_3) )
z_5 =                         lo(x_4, y_1) + lo(x_3, y_2) + lo(x_2, y_3) + lo(x_1, y_4) + 2*( hi(x_4, y_0) + hi(x_3, y_1) + hi(x_2, y_2) + hi(x_1, y_3) + hi(x_0, y_4) )
z_6 =                                                 lo(x_4, y_2) + lo(x_3, y_3) + lo(x_2, y_4) + 2*(                         hi(x_4, y_1) + hi(x_3, y_2) + hi(x_2, y_3) + hi(x_1, y_4) )
z_7 =                                                                         lo(x_4, y_3) + lo(x_3, y_4) + 2*(                                                 hi(x_4, y_2) + hi(x_3, y_3) + hi(x_2, y_4) )
z_8 =                                                                                                 lo(x_4, y_4) + 2*(                                                                         hi(x_4, y_3) + hi(x_3, y_4) )
z_9 = 0 + 2*(                                                                                                 hi(x_4, y_4) )
```

--------------------------------

### Vectorized Square Root Computations

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Proposes implementing vectorized square root computations as a future improvement. This would enable an iterator adaptor for point decompression, allowing parallel execution of decompression operations and accelerating batch verification.

```rust
// Implement vectorized square root computations.
// Create an iterator adaptor for point decompression.
// Bunch decompression operations and execute them in parallel.
// Accelerate batch verification.
```

--------------------------------

### HWCD'08 Doubling Formula

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/parallel-formulas.md

Presents the doubling formula for elliptic curve points as described in the HWCD'08 paper, outlining the operations across four processors and their associated costs.

```APIDOC
Doubling Formula (HWCD'08):

| Cost             | Processor 1                    | Processor 2                    | Processor 3                    | Processor 4                    |
|------------------|--------------------------------|--------------------------------|--------------------------------|--------------------------------|
|                  | idle                           | idle                           | idle                           | \( R_1 \gets X_1 + Y_1 \) |
| \(1\mathbf S\) | \( R_2 \gets X_1^2 \)     | \( R_3 \gets Y_1^2   \)   | \( R_4 \gets Z_1^2   \)   | \( R_5 \gets R_1^2   \)   |
|                  | \( R_6 \gets R_2 + R_3 \) | \( R_7 \gets R_2 - R_3 \) | \( R_4 \gets 2 R_4 \)      | idle                           |
|                  | idle                           | \( R_1 \gets R_4 + R_7 \) | idle                           | \( R_2 \gets R_6 - R_5 \) |
| \(1\mathbf M\) | \( X_3 \gets R_1 R_2 \)   | \( Y_3 \gets R_6 R_7 \)   | \( T_3 \gets R_2 R_6 \)   | \( Z_3 \gets R_1 R_7 \)   |
```

--------------------------------

### Radix Choice and Product Accumulation

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

This section explains the implications of choosing a radix for multiprecision integer representation when using IFMA instructions. It contrasts the native radix (r=52) with a smaller radix (r=52-k), detailing how the product terms are handled and accumulated. The native radix allows direct accumulation, while a smaller radix requires additional shifting.

```assembly
; Conceptual representation of product accumulation with native radix (r=52)
; Assume x_i and y_j are 52-bit values, stored in lower parts of registers.
; Product term: (x_i * 2^(52*i)) * (y_j * 2^(52*j))

; Calculation of lo(x_i, y_j) and hi(x_i, y_j)
; vmulx ymm_prod, ymm_xi, ymm_yj ; Hypothetical instruction for 52-bit multiplication
; vpsrlq ymm_lo, ymm_prod, 52    ; Extract low 52 bits (conceptual)
; vpsrlq ymm_hi, ymm_prod, 52    ; Extract high 52 bits (conceptual)

; Direct accumulation onto product limbs z_{i+j} and z_{i+j+1}
; add z[i+j], ymm_lo
; add z[i+j+1], ymm_hi

; Conceptual representation with smaller radix (r = 52 - k)
; Product term: (x_i * 2^(r*i)) * (y_j * 2^(r*j))

; Calculation of lo(x_i, y_j) and hi(x_i, y_j)
; ... (similar multiplication)

; Shift hi(x_i, y_j) by k bits before accumulation
; vpsllq ymm_hi_shifted, ymm_hi, k ; Hypothetical left shift

; Accumulation onto product limbs z_{i+j} and z_{i+j+1}
; add z[i+j], ymm_lo
; add z[i+j+1], ymm_hi_shifted
```

--------------------------------

### AVX2 and AVX512-IFMA Implementations

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/parallel-formulas.md

This section describes the two backend implementations for vectorized operations: one using AVX2 and the other using AVX512-IFMA. It details the strategy for applying modified parallel formulas from HWCD08 to SIMD operations, addressing instruction divergence with masking.

```rust
/// Backend for AVX2
pub struct Avx2Backend;

/// Backend for AVX512-IFMA
pub struct Avx512IfmaBackend;

// ... implementation details for field and point operations using these backends ...
```

--------------------------------

### Curve25519 Point Doubling Formulas

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/parallel-formulas.md

Mathematical formulas for doubling a point on the Curve25519. This section outlines the steps from initial point representation to the final doubled point, including intermediate calculations.

```mathematica
(* Initial step for doubling P = (X_1 : Y_1 : Z_1 : T_1) *)
(X_1, Y_1, Z_1, S_0) <- (X_1, Y_1, Z_1, X_1 + Y_1)

(* Squaring intermediate values *)
(S_1, S_2, S_3, S_4) <- (X_1^2, Y_1^2, Z_1^2, S_0^2)

(* Additions for intermediate calculations *)
(S_5, S_6, S_8, S_9) <- (S_1 + S_2, S_1 - S_2, S_1 + 2*S_3 - S_2, S_1 + S_2 - S_4)

(* Final point calculation for P_3 = [2]P_1 *)
(X_3, Y_3, Z_3, T_3) <- (S_8 * S_9, S_5 * S_6, S_8 * S_6, S_5 * S_9)
```

--------------------------------

### curve25519-dalek-ng Backend Implementation Strategy

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/parallel-formulas.md

Overview of how the curve25519-dalek-ng library handles point operations by abstracting field element vector implementations. It mentions the use of `ExtendedPoint` and `CachedPoint` types in `avx2` and `ifma` backends.

```rust
/// The `avx2` and `ifma` backends provide `ExtendedPoint` and `CachedPoint` types.
/// The `scalar_mul` code uses one of the backend types by a type alias.
///
/// Example usage might involve:
/// ```rust
/// use curve25519_dalek_ng::constants::X25519_BASEPOINT_MONTGOMERY;
/// use curve25519_dalek_ng::scalar_mul::Scalar;
/// use curve25519_dalek_ng::traits::IsIdentity;
///
/// let scalar = Scalar::from_bytes_mod_order(b"\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f\x00");
/// let point = X25519_BASEPOINT_MONTGOMERY;
///
/// // The actual multiplication would use a backend-specific point type
/// // let result = scalar * point; 
/// ```
```

--------------------------------

### AVX2 Field Element Representation

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/avx2-notes.md

Illustrates the data layout for a vector of four field elements in AVX2, using 32-bit lanes and pre-shuffling for efficient unpacking and multiplication. This layout is designed to leverage the vpmuludq instruction.

```text
(a1 ?? b1 ?? c1 ?? d1 ??)
(a2 ?? b2 ?? c2 ?? d2 ??)

(a1*a2 b1*b2 c1*c2 d1*d2)
```

```text
(a0 00 b0 00 a1 00 b1 00)
(a1 00 b1 00 c1 00 d1 00)
```

```text
(a0 b0 a1 b1 c0 d0 c1 d1)
(a2 b2 a3 b3 c2 d2 c3 d3)
(a4 b4 a5 b5 c4 d4 c5 d5)
(a6 b6 a7 b7 c6 d6 c7 d7)
(a8 b8 a9 b9 c8 d8 c9 d9)
```

--------------------------------

### AVX512-IFMA Instructions

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Details the AVX512-IFMA instructions, vpmadd52luq and vpmadd52huq, used for vectorized integer operations. These instructions perform 52-bit integer multiplications and add the results to 64-bit accumulators, leveraging AVX512VL for variable vector lengths.

```APIDOC
IFMA Instructions:

vpmadd52luq: packed multiply of unsigned 52-bit integers and add the low 52 product bits to 64-bit accumulators.
  - Operates on 64-bit lanes.
  - Computes 104-bit products.
  - Adds low 52 bits of product to destination vector lanes.

vpmadd52huq: packed multiply of unsigned 52-bit integers and add the high 52 product bits to 64-bit accumulators.
  - Operates on 64-bit lanes.
  - Computes 104-bit products.
  - Adds high 52 bits of product to destination vector lanes.

Usage Context:
  - Part of AVX-512 extension.
  - AVX512VL allows usage with 512, 256, or 128-bit operands.
  - Provides advantage for vectorized integer operations by enabling 64x64 -> 128-bit multiplication, unlike previous 32x32 -> 64-bit multipliers.
```

--------------------------------

### Avoiding Overflow in Doubling: Intermediate Calculations

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/avx2-notes.md

Demonstrates the intermediate calculations for doubling field elements and the resulting bit-excesses. It highlights the issue where direct computation leads to values too large for efficient multiplication.

```text
(S_5 &&,&& S_6 &&,&& S_8 &&,&& S_9 )
gets
(S_1 + S_2 &&,&& S_1 - S_2 &&,&& S_1 + 2S_3 - S_2 &&,&& S_1 + S_2 - S_4)
```

```text
      S_1  S_1  S_1  S_1
+     S_2       S_2
+          S_3
+          S_3
+     2p   2p   2p
-     S_2  S_2
-               S_4
= S_5  S_6  S_8  S_9
```

```text
X_3  gets S_8 S_9  (2.33, 2.01)
Y_3  gets S_5 S_6  (1.01, 1.60)
Z_3  gets S_8 S_6  (2.33, 1.60)
T_3  gets S_5 S_9  (1.01, 2.01)
```

--------------------------------

### Modular Reduction Strategy

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Explains the mathematical approach to reducing large numbers modulo p = 2^255 - 19 by rewriting the number in a different radix and combining terms. This is crucial for cryptographic operations where numbers must stay within a specific range.

```mathematics
z = z_0 + z_1 2^{51} + z_2 2^{102} + z_3 2^{153} + z_4 2^{204} + z_5 2^{255} + z_6 2^{306} + z_7 2^{357} + z_8 2^{408} + z_9 2^{459}

Modulo p, this can be rewritten as:

z = (z_0 + 19z_5) + (z_1 + 19z_6) 2^{51} + (z_2 + 19z_7) 2^{102} + (z_3 + 19z_8) 2^{153} + (z_4 + 19z_9) 2^{204}
```

--------------------------------

### Handling High Terms in Reduction

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Details how the high terms (z_5 to z_9) are processed, including splitting them into smaller parts and applying multiplication by 19. It addresses the specific case of z_9's contribution to avoid extra shifts.

```mathematics
z_{5+i} = z_{5+i}' + z_{5+i}'' 2^{52}, where z_{5+i}' < 2^{52}.

Contribution modulo p:

19 * z_{5+i} * 2^{51*i} = lo(19, z_{5+i}') 2^{51 i} + 2*hi(19, z_{5+i}') 2^{51 (i+1)} + 2*lo(19, z_{5+i}'') 2^{51 (i+1)}

For i=4 (z_9):

z_9 * 2^{255} * 2^{204} = lo(19, z_9) 2^{204} + 2*hi(19, z_9) * 19 + 2*lo(19, z_9/2^{52}) * 19
```

--------------------------------

### Field Element Multiplication

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Details the mathematical representation of field elements x and y, and their product z, using limbs and powers of 2^51. It outlines the schoolbook multiplication process in product scanning form.

```mathematics
x = x_0 + x_1 2^51 + x_2 2^102} + x_3 2^153} + x_4 2^204}
y = y_0 + y_1 2^51 + y_2 2^102} + y_3 2^153} + y_4 2^204}

z = z_0 + z_1 2^51 + z_2 2^102} + z_3 2^153} + z_4 2^204}
  + z_5 2^255} + z_6 2^306} + z_7 2^357} + z_8 2^408} + z_9 2^459}

z_0 = x_0 y_0
z_1 = x_1 y_0 + x_0 y_1
z_2 = x_2 y_0 + x_1 y_1 + x_0 y_2
z_3 = x_3 y_0 + x_2 y_1 + x_1 y_2 + x_0 y_3
z_4 = x_4 y_0 + x_3 y_1 + x_2 y_2 + x_1 y_3 + x_0 y_4
z_5 =           x_4 y_1 + x_3 y_2 + x_2 y_3 + x_1 y_4
z_6 =                     x_4 y_2 + x_3 y_3 + x_2 y_4
z_7 =                               x_4 y_3 + x_3 y_4
z_8 =                                         x_4 y_4
z_9 = 0
```

--------------------------------

### Curve25519 Point Readdition Formulas

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/parallel-formulas.md

Mathematical formulas for re-adding two points on the Curve25519, including precomputation steps and the final addition. This optimized approach aims to reduce computational cost.

```mathematica
(* Precomputation step for P_2 = (X_2 : Y_2 : Z_2 : T_2) *)
(S_2', S_3', Z_2', T_2') <- (d_2 * (Y_2 - X_2), d_2 * (Y_1 + X_1), 2*d_2 * Z_2, 2*d_1 * T_2)

(* Addition formulas with precomputed values *)
(S_0, S_1, Z_1, T_1) <- (Y_1 - X_1, Y_1 + X_1, Z_1, T_1)
(S_8, S_9, S_10, S_11) <- (S_0 * S_2', S_1 * S_3', Z_1 * Z_2', T_1 * T_2')
(S_12, S_13, S_14, S_15) <- (S_9 - S_8, S_9 + S_8, S_10 - S_11, S_10 + S_11)
(X_3, Y_3, Z_3, T_3) <- (S_12 * S_14, S_15 * S_13, S_12 * S_14, S_15 * S_13)
```

--------------------------------

### IFMA Optimized Multiplication Strategy

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Demonstrates the optimized multiplication strategy using IFMA operators \(\mathrm{lo}(a,b)\) and \(\mathrm{hi}(a,b)\). This method accumulates the low half of \(x_i y_j\) onto \(z_{i+j}\) and the high half onto \(z_{i+j+1}\), reducing operations.

```mathematica
(x_i 2^{52 i}) (y_j 2^{52 j}) = 2^{52 (i+j)}(\\n\mathrm{lo}(x_i, y_j) + \
\mathrm{hi}(x_i, y_j) 2^{52}
)\\
= \mathrm{lo}(x_i, y_j) 2^{52 (i+j)} + \
\mathrm{hi}(x_i, y_j) 2^{52 (i+j+1)}.

&z_0   &&= \mathrm{lo}(x_0,&y_0)      &                 &          &                 &          &                 &          &                 &          &        &     \\ 
&z_1   &&= \mathrm{lo}(x_1,&y_0)      &+\\mathrm{hi}(x_0,&y_0)      &+\\mathrm{lo}(x_0,&y_1)      &                 &          &                 &          &        &     \\ 
&z_2   &&= \mathrm{lo}(x_2,&y_0)      &+\\mathrm{hi}(x_1,&y_0)      &+\\mathrm{lo}(x_1,&y_1)      &+\\mathrm{hi}(x_0,&y_1)      &+\\mathrm{lo}(x_0,&y_2)      &        &     \\ 
&z_3   &&= \mathrm{lo}(x_3,&y_0)      &+\\mathrm{hi}(x_2,&y_0)      &+\\mathrm{lo}(x_2,&y_1)      &+\\mathrm{hi}(x_1,&y_1)      &+\\mathrm{lo}(x_1,&y_2)      &+ \cdots&     \\ 
&z_4   &&=        \\vdots\;&\\;\\vdots &+\\mathrm{hi}(x_3,&y_0)      &+\\mathrm{lo}(x_3,&y_1)      &+\\mathrm{hi}(x_2,&y_1)      &+\\mathrm{lo}(x_2,&y_2)      &+ \cdots&     \\ 
&z_5   &&=                 &          &        \\vdots\;&\\;\\vdots &        \\vdots\;&\\;\\vdots &+\\mathrm{hi}(x_3,&y_1)      &+\\mathrm{lo}(x_3,&y_2)      &+ \cdots&     \\ 
&z_6   &&=                 &          &                 &          &                 &          &        \\vdots\;&\\;\\vdots &        \\vdots\;&\\;\\vdots &+ \cdots&     \\ 
&\\vdots&&=                 &          &                 &          &                 &          &                 &          &                 &          &  \\ddots&     \\
```

--------------------------------

### Big Integer Representation Conversion

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

Illustrates the conversion of a packed 64-bit integer representation to a redundant 52-bit representation for big-integer multiplication. Each limb of the redundant representation fits within a 64-bit lane.

```mathematica
x = x'_0 + x'_1 2^{64} + x'_2 2^{128} + \\cdots \\
y = y'_0 + y'_1 2^{64} + y'_2 2^{128} + \\cdots

x = x_0 + x_1 2^{52} + x_2 2^{104} + \\cdots \\
y = y_0 + y_1 2^{52} + y_2 2^{104} + \\cdots
```

--------------------------------

### Parallel Edwards Formulas for ECC

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/ifma-notes.md

This section discusses the use of parallel Edwards formulas for elliptic curve cryptography operations. It explains how these formulas provide parallelism at the formula level, allowing computations to be parallelized across field elements rather than within a single field element. The implementation uses 256-bit vectors for 4-way parallelism.

```assembly
; Example of how 256-bit vectors might be used with IFMA instructions
; This is a conceptual representation and not actual executable code.

; Assume v1, v2 are 256-bit registers, each holding four 64-bit lanes.
; The following pseudo-assembly illustrates parallel operations across lanes.

; Operation: v1 * v2 (element-wise multiplication within 256-bit vector)
; This would involve multiple IFMA instructions operating on the 64-bit lanes.

; Example: Multiply lane 0 of v1 with lane 0 of v2, lane 1 with lane 1, etc.
; vmulps ymm0, ymm1, ymm2  ; Hypothetical instruction for 256-bit vector multiply

; Accumulation of products would follow, potentially using other vector instructions.
; vfmadd231ps ymm3, ymm4, ymm5 ; Hypothetical fused multiply-add
```

--------------------------------

### Avoiding Overflow in Doubling: Modified Calculation

Source: https://github.com/zkcrypto/curve25519-dalek-ng/blob/main/docs/avx2-notes.md

Presents the modified calculation for doubling field elements by flipping the sign of S4. This adjustment ensures that intermediate products remain within bounds, allowing for efficient multiplication without intermediate reductions.

```text
      S_1  S_1  S_1  S_1
+     S_2       S_2
+          S_3
+          S_3
+               S_4'
+     2p   2p
-     S_2  S_2
= S_5  S_6  S_8  S_9
```

```text
X_3  gets S_8 S_9  (2.33, 1.60)
Y_3  gets S_5 S_6  (1.01, 1.60)
Z_3  gets S_8 S_6  (2.33, 1.60)
T_3  gets S_5 S_9  (1.01, 1.60)
```
Tokens:
Raw