dlubarov

# The idea is to track the current value of the kernel, and update it according to
#     kernel *= (1 + delta_i' y_i) / (1 - delta_i' y_i),
# which we verify with the constraint
#     kernel(g x) * (1 - delta_i(g x) y_i) = kernel(x) * (1 + delta_i(g x) y_i),
# where delta_i is a succinctly evaluable polynomial defined by bit_delta(i, n) below.

p = 2^31 - 2^27 + 1
F = GF(p)
g = F.multiplicative_generator()
R.<t> = F[]

dlubarov

p = 2^8 + 1
F = GF(p)
n = 32
k = 16

C = codes.ReedSolomonCode(F, n, k)
C_folded = codes.ReedSolomonCode(F, n//2, k//2)
D = C.decoder("BerlekampWelch")
D_folded = C_folded.decoder("BerlekampWelch")

dlubarov

3754 gates to root
| 367 gates to evaluate the vanishing polynomial at our challenge point, zeta.
| | 276 gates to evaluate gate constraints
| | | 2 gates to evaluate NoopGate constraints
| | | 0 gates to evaluate PublicInputGate constraints
| | | 15 gates to evaluate BaseSumGate { num_limbs: 63 } + Base: 2 constraints
| | | 27 gates to evaluate ReducingExtensionGate { num_coeffs: 32 } constraints
| | | 33 gates to evaluate ReducingGate { num_coeffs: 43 } constraints
| | | 11 gates to evaluate ArithmeticExtensionGate { num_ops: 10 } constraints
| | | 10 gates to evaluate ArithmeticGate { num_ops: 20 } constraints

dlubarov

def H(x):
    assert 0 < x < 1
    return -x * log(x)/log(2) - (1 - x) * log(1 - x)/log(2)

def D(a, p):
    assert 0 < a < 1
    assert 0 < p < 1
    return a*log(a/p) + (1 - a)*(log(1 - a) - log(1 - p))

def log_pr_exactly_c_cols(n, m, d, c):

dlubarov

use std::fmt::{Debug, Display, Formatter};
use std::fmt;
use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};

use num::Integer;

use crate::field::field::Field;

/// EPSILON = 9 * 2**28 - 1
const EPSILON: u64 = 2415919103;

dlubarov

MSMs with terms=2^14, threads=1, window_size=11: avg=0.1419s, avg*threads=0.1419s
MSMs with terms=2^14, threads=2, window_size=11: avg=0.0963s, avg*threads=0.1926s
MSMs with terms=2^14, threads=3, window_size=11: avg=0.0805s, avg*threads=0.2415s
MSMs with terms=2^14, threads=4, window_size=11: avg=0.0740s, avg*threads=0.2959s
MSMs with terms=2^14, threads=5, window_size=11: avg=0.0740s, avg*threads=0.3702s
MSMs with terms=2^14, threads=6, window_size=11: avg=0.0681s, avg*threads=0.4088s
MSMs with terms=2^14, threads=7, window_size=11: avg=0.0633s, avg*threads=0.4433s
MSMs with terms=2^14, threads=8, window_size=11: avg=0.0634s, avg*threads=0.5073s
MSMs with terms=2^14, threads=9, window_size=11: avg=0.0610s, avg*threads=0.5486s
MSMs with terms=2^14, threads=10, window_size=11: avg=0.0607s, avg*threads=0.6070s

dlubarov

Keybase proof

I hereby claim:

• I am dlubarov on github.
• I am dlubarov (https://keybase.io/dlubarov) on keybase.
• I have a public key whose fingerprint is 1112 9769 A62F 9827 0ABA 6DAF 5371 D442 573C 68EC

To claim this, I am signing this object:

dlubarov

interface NaturalNumber {}

class Zero implements NaturalNumber {
  @Override
  public String toString() {
    return "0";
  }
}

class Successor implements NaturalNumber {

dlubarov

def is_prime(n):
  if n in ('', '1'):
    return False

  d = '11'
  while difference(n, d):
    if is_divisible(n, d):
      return False
    d += '1'
  return True