~/bend-docscommunity

proofs/math/typed/u32mont.bend checks

raw source on the hub · import bend-collections-laws-math@1.0.0.0/proofs/math/typed/u32mont.bend as U32mont

27 imports
import Base
import ../../../spec/lib/common.bend as C
import ../../../spec/math/w64.bend as SW
import ../../../src/math/w64.bend as X
import ../../../src/math/u64.bend as WU
import ../../../src/math/natural.bend as M
import ../../lib/nat.bend as N
import ../../lib/logic.bend as L
import ../../lib/word.bend as WD
import ../../lib/u32div.bend as UD
import ../../lib/lemmas/spec/numeric.bend as S
import ../../lib/lemmas/proofs/nat_algebra.bend as NA
import ../natural/arith.bend as NR
import ../natural/sqrtn.bend as SQ2
import ../u64/u64.bend as P64
import ./width.bend as WW
import ./u32laws.bend as LW
import ./w64add.bend as WA
import ./w64mul.bend as W64M
import ./w64sqrt.bend as W64S
import ./w64sh.bend as SH
import ./w64m128.bend as M128
import ./w64div.bend as W64D
import ./w64dm.bend as DM
import ./natlight.bend as AQ
import ./montnat.bend as MN
import ./u64mont.bend as UM

Definitions

def v source · line 34 · raw

@+x:U32 -> Nat

def true_ne_false source · line 37 · raw

@+h:{True{} == False{} : Bool} -> Empty

def b32v source · line 40 · raw

@c:Bool -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(c)) == 0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(c) : Nat}

def cadd source · line 48 · raw

@+x:U32 -> @+y:U32 -> {Nat.add(v(x), v(y)) == Nat.add(v(U32.add(x, y)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, 0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(U32.is_lt(U32.add(x, y), x)))) : Nat}

x + y == (x + y mod 2^32) + 2^32 carry

def m32v source · line 53 · raw

@+a:U32 -> @+b:U32 -> {Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mul32(a, b))), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mul32(a, b))))) == Nat.mul(v(a), v(b)) : Nat}

the two words of a 32 x 32 product

def kv source · line 56 · raw

@c1:Bool -> @c2:Bool -> {v(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(c1), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(c2))) == Nat.add(0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(c1), 0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(c2)) : Nat}

def lo32 source · line 67 · raw

@+w:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+h:{0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.fits(32n, 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(w)) == True{} : Bool} -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(w)) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(w) : Nat}

def sif_c source · line 74 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+r:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hr:{Nat.is_lt(0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(r), Nat.add(1n+bp, 1n+bp)) == True{} : Bool} -> @+c:Bool -> @+hc:{0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.le(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64{m, 0}, r) == c : Bool} -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.sub_if32(r, m, c)) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(r), 1n+bp) : Nat}

sub_if32: r < 2 m gives r mod m

def sif source · line 97 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+r:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hr:{Nat.is_lt(0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(r), Nat.add(1n+bp, 1n+bp)) == True{} : Bool} -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.redc32_r(m, r)) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(r), 1n+bp) : Nat}

def rp_low source · line 101 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+t:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+p:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+eP:{Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)))) == Nat.mul(v(U32.mul(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), mp)), 1n+bp) : Nat} -> {Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)), v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, 0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)))) : Nat}

def rp_eq source · line 108 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+t:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+p:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+T:Nat -> @+eT:{Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t)))) == T : Nat} -> @+eP:{Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)))) == Nat.mul(v(U32.mul(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), mp)), 1n+bp) : Nat} -> {0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, Nat.add(v(U32.add(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t))))), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, Nat.add(0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t))), 0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(U32.is_lt(U32.add(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)))), U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)))))))) == Nat.add(T, Nat.mul(v(U32.mul(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), mp)), 1n+bp)) : Nat}

2^32 r' == t + u m for r' = s2 + 2^32 (c1 + c2)

def rp_lt_g source · line 116 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+b:Nat -> @+hb:{Nat.is_lt(0n, b) == True{} : Bool} -> @+hbf:{0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.fits(32n, b) == True{} : Bool} -> @+t:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+mp:U32 -> @+T:Nat -> @+hT:{Nat.is_lt(T, Nat.mul(b, b)) == True{} : Bool} -> @+R:Nat -> @+er:{0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, R) == Nat.add(T, Nat.mul(v(U32.mul(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), mp)), b)) : Nat} -> {Nat.is_lt(R, Nat.add(b, b)) == True{} : Bool}

r' < 2 m for t < m^2 and m < 2^32 over an open bound b (1 + bp at the use): a closed-width shift of 1 + bp would be unfolded into 2^32 successors

def rp_lt source · line 132 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+t:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+p:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+T:Nat -> @+eT:{Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t)))) == T : Nat} -> @+hT:{Nat.is_lt(T, Nat.mul(1n+bp, 1n+bp)) == True{} : Bool} -> @+eP:{Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)))) == Nat.mul(v(U32.mul(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), mp)), 1n+bp) : Nat} -> {Nat.is_lt(Nat.add(v(U32.add(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t))))), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, Nat.add(0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t))), 0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(U32.is_lt(U32.add(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)))), U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p))))))), Nat.add(1n+bp, 1n+bp)) == True{} : Bool}

def r_v source · line 135 · raw

@+t:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+p:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> {0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64{U32.add(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)))), U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t))), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)))), U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)))))}) == Nat.add(v(U32.add(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t))))), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, Nat.add(0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t))), 0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(U32.is_lt(U32.add(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)))), U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p))))))) : Nat}

def rp_mod source · line 139 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+t:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+p:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+T:Nat -> @+eT:{Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t)))) == T : Nat} -> @+hT:{Nat.is_lt(T, Nat.mul(1n+bp, 1n+bp)) == True{} : Bool} -> @+eP:{Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)))) == Nat.mul(v(U32.mul(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), mp)), 1n+bp) : Nat} -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.redc32_p(m, t, p)) == Nat.mod(Nat.add(v(U32.add(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t))))), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, Nat.add(0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t))), 0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(U32.is_lt(U32.add(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.b32(U32.is_lt(U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)))), U32.add(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t), 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p))))))), 1n+bp) : Nat}

redc32_p is r' mod m

def rp_lt_m source · line 143 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+t:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+p:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+T:Nat -> @+eT:{Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t)))) == T : Nat} -> @+hT:{Nat.is_lt(T, Nat.mul(1n+bp, 1n+bp)) == True{} : Bool} -> @+eP:{Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)))) == Nat.mul(v(U32.mul(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), mp)), 1n+bp) : Nat} -> {Nat.is_lt(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.redc32_p(m, t, p)), 1n+bp) == True{} : Bool}

def rp_cong source · line 146 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+t:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+p:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> @+T:Nat -> @+eT:{Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(t)))) == T : Nat} -> @+hT:{Nat.is_lt(T, Nat.mul(1n+bp, 1n+bp)) == True{} : Bool} -> @+eP:{Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(p)), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(p)))) == Nat.mul(v(U32.mul(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(t), mp)), 1n+bp) : Nat} -> {Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.redc32_p(m, t, p))), 1n+bp) == Nat.mod(T, 1n+bp) : Nat}

def ep_m source · line 149 · raw

@+bp:Nat -> @+m:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+u:U32 -> {Nat.add(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.lo(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mul32(u, m))), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.hi(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mul32(u, m))))) == Nat.mul(v(u), 1n+bp) : Nat}

def ab_lt source · line 152 · raw

@+bp:Nat -> @+a:Nat -> @+b:Nat -> @+ha:{Nat.is_lt(a, 1n+bp) == True{} : Bool} -> @+hb:{Nat.is_lt(b, 1n+bp) == True{} : Bool} -> {Nat.is_lt(Nat.mul(a, b), Nat.mul(1n+bp, 1n+bp)) == True{} : Bool}

def mont_lt source · line 156 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+a:U32 -> @+b:U32 -> @+hT:{Nat.is_lt(Nat.mul(v(a), v(b)), Nat.mul(1n+bp, 1n+bp)) == True{} : Bool} -> {Nat.is_lt(v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mont32(m, mp, a, b)), 1n+bp) == True{} : Bool}

32-bit Montgomery multiplication: mont32(a, b) < m and mont32(a, b) 2^32 == a b (mod m)

def mont_cong source · line 159 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+a:U32 -> @+b:U32 -> @+hT:{Nat.is_lt(Nat.mul(v(a), v(b)), Nat.mul(1n+bp, 1n+bp)) == True{} : Bool} -> {Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mont32(m, mp, a, b))), 1n+bp) == Nat.mod(Nat.mul(v(a), v(b)), 1n+bp) : Nat}

def mlt source · line 163 · raw

@+bp:Nat -> @+x:Nat -> {Nat.is_lt(Nat.mod(x, 1n+bp), 1n+bp) == True{} : Bool}

def smul source · line 166 · raw

@+x:Nat -> @+y:Nat -> {Nat.mul(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, x), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, y)) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, Nat.mul(x, y))) : Nat}

def mform source · line 169 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+hh:Nat -> @+hH:{2n+bp == Nat.add(hh, hh) : Nat} -> @+a:U32 -> @+b:U32 -> @+an:Nat -> @+bn:Nat -> @+ha:{v(a) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, an), 1n+bp) : Nat} -> @+hb:{v(b) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, bn), 1n+bp) : Nat} -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mont32(m, mp, a, b)) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, Nat.mod(Nat.mul(an, bn), 1n+bp)), 1n+bp) : Nat}

def mbit_v source · line 179 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+hh:Nat -> @+hH:{2n+bp == Nat.add(hh, hh) : Nat} -> @+b:U32 -> @+acc:U32 -> @+bn:Nat -> @+an:Nat -> @+hb:{v(b) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, bn), 1n+bp) : Nat} -> @+ha:{v(acc) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, an), 1n+bp) : Nat} -> @+d:Nat -> @+o:Bool -> @+hd:{Nat.is_lt(d, 2n) == True{} : Bool} -> @+ho:{o == Nat.is_eq(d, 1n) : Bool} -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mbit32(o, m, mp, b, acc)) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/natural.pow_mod_odd(1n+bp, d, bn, an)), 1n+bp) : Nat}

def izv source · line 192 · raw

@+a:U32 -> @+n:Nat -> @+h:{v(a) == n : Nat} -> {U32.is_zero(a) == Nat.is_eq(n, 0n) : Bool}

def msim source · line 195 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+hh:Nat -> @+hH:{2n+bp == Nat.add(hh, hh) : Nat} -> @+f:Nat -> @+b:U32 -> @+acc:U32 -> @+e:U32 -> @+bn:Nat -> @+an:Nat -> @+hb:{v(b) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, bn), 1n+bp) : Nat} -> @+ha:{v(acc) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, an), 1n+bp) : Nat} -> @+ez:Bool -> @+ne:Nat -> @+hez:{U32.is_zero(e) == ez : Bool} -> @+hne:{v(e) == ne : Nat} -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mpow32_go(f, m, mp, b, acc, (e, ez))) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/natural.pow_mod_go(f, 1n+bp, ne, bn, an)), 1n+bp) : Nat}

def hdz source · line 217 · raw

@+bp:Nat -> @+m:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> {U32.is_zero(m) == False{} : Bool}

def to_mont_v source · line 221 · raw

@+bp:Nat -> @+m:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+x:U32 -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mod32(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64{0, x}, m)) == Nat.mod(0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, v(x)), 1n+bp) : Nat}

x 2^32 mod m by one 64 / 32 reduction

def g1_lt source · line 226 · raw

@+bp:Nat -> @+x:Nat -> @+h:{Nat.is_lt(x, 1n+bp) == True{} : Bool} -> {Nat.is_lt(Nat.mul(x, v(1)), Nat.mul(1n+bp, 1n+bp)) == True{} : Bool}

x 1 < m m for x < m

def mpow_v source · line 231 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+mp:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hinv:{1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(mp))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat} -> @+b:U32 -> @+hb:{Nat.is_lt(v(b), 1n+bp) == True{} : Bool} -> @+e:U32 -> @+hodd:{Nat.mod(1n+bp, 2n) == 1n : Nat} -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mpow32_m(b, e, m, mp)) == 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/natural.pow_mod_go(140n, 1n+bp, v(e), v(b), Nat.mod(1n, 1n+bp)) : Nat}

def mok_odd source · line 252 · raw

@+bp:Nat -> @+m:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hok:{0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mont32_ok(m) == True{} : Bool} -> {Nat.mod(1n+bp, 2n) == 1n : Nat}

def mok_inv_o source · line 257 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+o:U32 -> @+po:{o == U32{0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/word.mask(32n, 32n)} : U32} -> @+heq:{U32.is_eq(U32.mul(m, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.minv32(m)), o) == True{} : Bool} -> {1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.minv32(m)))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat}

over an open all-ones word o (a literal 2^32 - 1 is expanded in unary)

def mok_inv source · line 266 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hok:{0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mont32_ok(m) == True{} : Bool} -> {1n+0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(32n, Nat.mul(1n+bp, v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.minv32(m)))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, one) : Nat}

def mpow_top source · line 270 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+bp:Nat -> @+m:U32 -> @+hM:{v(m) == 1n+bp : Nat} -> @+hok:{0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mont32_ok(m) == True{} : Bool} -> @+b:U32 -> @+e:U32 -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.mpow32(U32.mod(b, m), e, m)) == 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/natural.pow_mod_go(140n, 1n+bp, v(e), Nat.mod(v(b), 1n+bp), Nat.mod(1n, 1n+bp)) : Nat}

pow_mod through 32-bit Montgomery multiplication when mont32_ok(m)