https://www.binius.xyz/assets/types-CJYLWmSd.js

1import{u as l,j as s}from"./index-Bpb9-9J-.js";const t={title:"Data Types",description:"The fundamental objects in our arithmetization scheme"};function n(a){const e={a:"a",annotation:"annotation",aside:"aside",code:"code",div:"div",em:"em",h1:"h1",h2:"h2",header:"header",math:"math",mi:"mi",mn:"mn",mo:"mo",mrow:"mrow",msub:"msub",msup:"msup",p:"p",semantics:"semantics",span:"span",...l(),...a.components};return s.jsxs(s.Fragment,{children:[s.jsxs(e.header,{children:[s.jsxs(e.h1,{id:"data-types",children:["Data Types",s.jsx(e.a,{"aria-hidden":"true",tabIndex:"-1",href:"#data-types",children:s.jsx(e.div,{"data-autolink-icon":!0})})]}),s.jsx(e.div,{role:"doc-subtitle",children:"The fundamental objects in our arithmetization scheme"})]}),`
2`,s.jsxs(e.p,{children:["Before we can explain ",s.jsx(e.a,{href:"/basics/binius-v0/m3",children:"M3"}),", we need to explain the fundamental data types that it works with. Here, we take a bit of time to do this, even though the story is pretty simple."]}),`
3`,s.jsx(e.p,{children:"Roughly, our fundamental datatypes are bitstrings of power-of-two width. Thus, we allow 128-bit binary strings, 64-bit strings, 32-bit strings, 16-bit strings, and 8-bit bytes. We also allow 1-bit values. For technical reasons, we skip the 4-bit and 2-bit widths."}),`
4`,s.jsx(e.aside,{"data-callout":"info",children:s.jsxs(e.p,{children:["For example, a 128-bit string looks something like ",s.jsx(e.code,{children:"732dda5087d5a846519178069246d7ea"}),", provided that it is hex encoded. A 64-bit string looks like ",s.jsx(e.code,{children:"0fb52f64e0b53e23"}),". An 8-bit string looks like ",s.jsx(e.code,{children:"a2"}),". A ",s.jsx(e.em,{children:"bit"})," is of course just 0 or 1!"]})}),`
5`,s.jsxs(e.p,{children:["For notational convenience, we will use the script-T symbols ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsxs(e.mrow,{children:[s.jsxs(e.msub,{children:[s.jsx(e.mi,{mathvariant:"script",children:"T"}),s.jsx(e.mn,{children:"0"})]}),s.jsx(e.mo,{separator:"true",children:","}),s.jsx(e.mo,{children:"…"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsxs(e.msub,{children:[s.jsx(e.mi,{mathvariant:"script",children:"T"}),s.jsx(e.mn,{children:"7"})]})]}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\mathcal{T}_0, \\ldots , \\mathcal{T}_7"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.8778em",verticalAlign:"-0.1944em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord mathcal",style:{marginRight:"0.25417em"},children:"T"}),s.jsx(e.span,{className:"msupsub",children:s.jsxs(e.span,{className:"vlist-t vlist-t2",children:[s.jsxs(e.span,{className:"vlist-r",children:[s.jsx(e.span,{className:"vlist",style:{height:"0.3011em"},children:s.jsxs(e.span,{style:{top:"-2.55em",marginLeft:"-0.2542em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mtight",children:"0"})})]})}),s.jsx(e.span,{className:"vlist-s",children:"​"})]}),s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.15em"},children:s.jsx(e.span,{})})})]})})]}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"minner",children:"…"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord mathcal",style:{marginRight:"0.25417em"},children:"T"}),s.jsx(e.span,{className:"msupsub",children:s.jsxs(e.span,{className:"vlist-t vlist-t2",children:[s.jsxs(e.span,{className:"vlist-r",children:[s.jsx(e.span,{className:"vlist",style:{height:"0.3011em"}

5,children:s.jsxs(e.span,{style:{top:"-2.55em",marginLeft:"-0.2542em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mtight",children:"7"})})]})}),s.jsx(e.span,{className:"vlist-s",children:"​"})]}),s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.15em"},children:s.jsx(e.span,{})})})]})})]})]})})]})," to refer to these datatypes. That is, for each ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsxs(e.mrow,{children:[s.jsx(e.mi,{children:"ι"}),s.jsx(e.mo,{children:"∈"}),s.jsx(e.mo,{stretchy:"false",children:"{"}),s.jsx(e.mn,{children:"0"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsx(e.mn,{children:"3"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsx(e.mn,{children:"4"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsx(e.mn,{children:"5"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsx(e.mn,{children:"6"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsx(e.mn,{children:"7"}),s.jsx(e.mo,{stretchy:"false",children:"}"})]}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\iota \\in \\{0, 3, 4, 5, 6, 7\\}"})]})})}),s.jsxs(e.span,{className:"katex-html","aria-hidden":"true",children:[s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.5782em",verticalAlign:"-0.0391em"}}),s.jsx(e.span,{className:"mord mathnormal",children:"ι"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2778em"}}),s.jsx(e.span,{className:"mrel",children:"∈"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),s.jsx(e.span,{className:"mopen",children:"{"}),s.jsx(e.span,{className:"mord",children:"0"}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"mord",children:"3"}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"mord",children:"4"}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"mord",children:"5"}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"mord",children:"6"}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"mord",children:"7"}),s.jsx(e.span,{className:"mclose",children:"}"})]})]})]}),", we will write ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsx(e.mrow,{children:s.jsxs(e.msub,{children:[s.jsx(e.mi,{mathvariant:"script",children:"T"}),s.jsx(e.mi,{children:"ι"})]})}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\mathcal{T}_\\iota"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.8333em",verticalAlign:"-0.15em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord mathcal",style:{marginRight:"0.25417em"},children:"T"}),s.jsx(e.span,{className:"msupsub",children:s.jsxs(e.span,{className:"vlist-t vlist-t2",children:[s.jsxs(e.span,{className:"vlist-r",children:[s.jsx(e.span,{className:"vlist",style:{height:"0.1514em"},children:s.jsxs(e.span,{style:{top:"-2.55em",marginLeft:"-0.2542em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mathnormal mtight",children:"ι"})})]})}),s.jsx(e.span,{className:"vlist-s",children:"​"})]}),s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.15em"},children:s.jsx(e.span,{})})})]})})]})]})})]})," for the datatype consisting of binary strings of length ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsx(e.mrow,{children:s.jsxs(e.msup,{children:[s.jsx(e.mn,{children:"2"}),s.jsx(e.mi,{children:"ι"})]})}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"2^\\iota"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.6644em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord",children:"2"}),s.jsx(e.span,{className:"msupsub",children:s.jsx(e.span,{className:"vlist-t",children:s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.6644em"}

5,children:s.jsxs(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mathnormal mtight",children:"ι"})})]})})})})})]})]})})]}),"."]}),`
6`,s.jsx(e.aside,{"data-callout":"info",children:s.jsxs(e.p,{children:["For example, ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsx(e.mrow,{children:s.jsxs(e.msub,{children:[s.jsx(e.mi,{mathvariant:"script",children:"T"}),s.jsx(e.mn,{children:"7"})]})}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\mathcal{T}_7"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.8333em",verticalAlign:"-0.15em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord mathcal",style:{marginRight:"0.25417em"},children:"T"}),s.jsx(e.span,{className:"msupsub",children:s.jsxs(e.span,{className:"vlist-t vlist-t2",children:[s.jsxs(e.span,{className:"vlist-r",children:[s.jsx(e.span,{className:"vlist",style:{height:"0.3011em"},children:s.jsxs(e.span,{style:{top:"-2.55em",marginLeft:"-0.2542em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mtight",children:"7"})})]})}),s.jsx(e.span,{className:"vlist-s",children:"​"})]}),s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.15em"},children:s.jsx(e.span,{})})})]})})]})]})})]}),' is the datatype consisting of 128-bit binary strings. We will often refer to this as the "cryptographically large field" or the "huge field". ',s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsx(e.mrow,{children:s.jsxs(e.msub,{children:[s.jsx(e.mi,{mathvariant:"script",children:"T"}),s.jsx(e.mn,{children:"0"})]})}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\mathcal{T}_0"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.8333em",verticalAlign:"-0.15em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord mathcal",style:{marginRight:"0.25417em"},children:"T"}),s.jsx(e.span,{className:"msupsub",children:s.jsxs(e.span,{className:"vlist-t vlist-t2",children:[s.jsxs(e.span,{className:"vlist-r",children:[s.jsx(e.span,{className:"vlist",style:{height:"0.3011em"},children:s.jsxs(e.span,{style:{top:"-2.55em",marginLeft:"-0.2542em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mtight",children:"0"})})]})}),s.jsx(e.span,{className:"vlist-s",children:"​"})]}),s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.15em"},children:s.jsx(e.span,{})})})]})})]})]})})]})," is the datatype consisting of 1-bit values (bits). ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsx(e.mrow,{children:s.jsxs(e.msub,{children:[s.jsx(e.mi,{mathvariant:"script",children:"T"}),s.jsx(e.mn,{children:"3"})]})}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\mathcal{T}_3"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.8333em",verticalAlign:"-0.15em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord mathcal",style:{marginRight:"0.25417em"},children:"T"}),s.jsx(e.span,{className:"msupsub",children:s.jsxs(e.span,{className:"vlist-t vlist-t2",children:[s.jsxs(e.span,{className:"vlist-r",children:[s.jsx(e.span,{className:"vlist",style:{height:"0.3011em"}

6,children:s.jsxs(e.span,{style:{top:"-2.55em",marginLeft:"-0.2542em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mtight",children:"3"})})]})}),s.jsx(e.span,{className:"vlist-s",children:"​"})]}),s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.15em"},children:s.jsx(e.span,{})})})]})})]})]})})]})," is the datatype of bytes."]})}),`
7`,s.jsxs(e.h2,{id:"arithmetic-operations",children:["Arithmetic Operations",s.jsx(e.a,{"aria-hidden":"true",tabIndex:"-1",href:"#arithmetic-operations",children:s.jsx(e.div,{"data-autolink-icon":!0})})]}),`
8`,s.jsxs(e.p,{children:["We also need to be able to talk about ",s.jsx(e.em,{children:"adding"})," and ",s.jsx(e.em,{children:"multiplying"})," strings like these. For us, addition is just bitwise XOR. This is a basic operation that you can do on two bitstrings of equal length. You go position by position, and write a 1 if and only if exactly one of the two arguments is 1 at that position, and 0 otherwise."]}),`
9`,s.jsxs(e.p,{children:['As it turns out, we also have a way of "multiplying" our binary strings together. We will skip the full description now, and defer to our ',s.jsx(e.a,{href:"/basics/binius-v0/towers",children:"tower fields page"}),". But in the important 1-bit special case, we can say exactly what multiplication is: it's just AND. For example, ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsxs(e.mrow,{children:[s.jsx(e.mn,{children:"1"}),s.jsx(e.mo,{children:"×"}),s.jsx(e.mn,{children:"1"}),s.jsx(e.mo,{children:"="}),s.jsx(e.mn,{children:"1"})]}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"1 \\times 1 = 1"})]})})}),s.jsxs(e.span,{className:"katex-html","aria-hidden":"true",children:[s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.7278em",verticalAlign:"-0.0833em"}}),s.jsx(e.span,{className:"mord",children:"1"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),s.jsx(e.span,{className:"mbin",children:"×"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.6444em"}}),s.jsx(e.span,{className:"mord",children:"1"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2778em"}}),s.jsx(e.span,{className:"mrel",children:"="}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.6444em"}}),s.jsx(e.span,{className:"mord",children:"1"})]})]})]}),", and ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsxs(e.mrow,{children:[s.jsx(e.mn,{children:"1"}),s.jsx(e.mo,{children:"×"}),s.jsx(e.mn,{children:"0"}),s.jsx(e.mo,{children:"="}),s.jsx(e.mn,{children:"0"})]}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"1 \\times 0 = 0"})]})})}),s.jsxs(e.span,{className:"katex-html","aria-hidden":"true",children:[s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.7278em",verticalAlign:"-0.0833em"}}),s.jsx(e.span,{className:"mord",children:"1"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),s.jsx(e.span,{className:"mbin",children:"×"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.6444em"}}),s.jsx(e.span,{className:"mord",children:"0"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2778em"}}),s.jsx(e.span,{className:"mrel",children:"="}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.6444em"}}),s.jsx(e.span,{className:"mord",children:"0"})]})]})]}),"."]}),`
10`,s.jsxs(e.h2,{id:"comparison-to-prime-fields",children:["Comparison to Prime Fields",s.jsx(e.a,{"aria-hidden":"true",tabIndex:"-1",href:"#comparison-to-prime-fields",children:s.jsx(e.div,{"data-autolink-icon":!0})})]}),`
11`,s.jsxs(e.p,{children:["We note that our binary datatypes are arguably ",s.jsx(e.em,{children:"simpler"})," than those associated with prime fields, which are much more typical in SNARKs. For example, ",s.jsx(e.a,{href:"https://risczero.com/",children:"RISC Zero"}),"'s arithmetization uses the ",s.jsx(e.em,{children:"Baby Bear"})," prime field ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsx(e.mrow,{children:s.jsxs(e.msub,{children:[s.jsx(e.mi,{mathvariant:"double-struck",children:"F"}),s.jsx(e.mi,{children:"p"})]})}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\mathbb{F}_p"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.975em",verticalAlign:"-0.2861em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord mathbb",children:"F"}),s.jsx(e.span,{className:"msupsub",children:s.jsxs(e.span,{className:"vlist-t vlist-t2",children:[s.jsxs(e.span,{className:"vlist-r",children:[s.jsx(e.span,{className:"vlist",style:{height:"0.1514em"}

11,children:s.jsxs(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mathnormal mtight",children:"p"})})]})}),s.jsx(e.span,{className:"vlist-s",children:"​"})]}),s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.2861em"},children:s.jsx(e.span,{})})})]})})]})]})})]}),", where ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsxs(e.mrow,{children:[s.jsx(e.mi,{children:"p"}),s.jsx(e.mo,{children:"="}),s.jsxs(e.msup,{children:[s.jsx(e.mn,{children:"2"}),s.jsx(e.mn,{children:"31"})]}),s.jsx(e.mo,{children:"−"}),s.jsxs(e.msup,{children:[s.jsx(e.mn,{children:"2"}),s.jsx(e.mn,{children:"27"})]}),s.jsx(e.mo,{children:"+"}),s.jsx(e.mn,{children:"1"})]}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"p = 2^{31} - 2^{27} + 1"})]})})}),s.jsxs(e.span,{className:"katex-html","aria-hidden":"true",children:[s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),s.jsx(e.span,{className:"mord mathnormal",children:"p"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2778em"}}),s.jsx(e.span,{className:"mrel",children:"="}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.8974em",verticalAlign:"-0.0833em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord",children:"2"}),s.jsx(e.span,{className:"msupsub",children:s.jsx(e.span,{className:"vlist-t",children:s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.8141em"},children:s.jsxs(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mtight",children:s.jsx(e.span,{className:"mord mtight",children:"31"})})})]})})})})})]}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),s.jsx(e.span,{className:"mbin",children:"−"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.8974em",verticalAlign:"-0.0833em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord",children:"2"}),s.jsx(e.span,{className:"msupsub",children:s.jsx(e.span,{className:"vlist-t",children:s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.8141em"},children:s.jsxs(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mtight",children:s.jsx(e.span,{className:"mord mtight",children:"27"})})})]})})})})})]}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),s.jsx(e.span,{className:"mbin",children:"+"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.6444em"}}),s.jsx(e.span,{className:"mord",children:"1"})]})]})]}),". Concretely, element of ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsx(e.mrow,{children:s.jsxs(e.msub,{children:[s.jsx(e.mi,{mathvariant:"double-struck",children:"F"}),s.jsx(e.mi,{children:"p"})]})}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\mathbb{F}_p"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.975em",verticalAlign:"-0.2861em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord mathbb",children:"F"}),s.jsx(e.span,{className:"msupsub",children:s.jsxs(e.span,{className:"vlist-t vlist-t2",children:[s.jsxs(e.span,{className:"vlist-r",children:[s.jsx(e.span,{className:"vlist",style:{height:"0.1514em"}

11,children:s.jsxs(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mathnormal mtight",children:"p"})})]})}),s.jsx(e.span,{className:"vlist-s",children:"​"})]}),s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.2861em"},children:s.jsx(e.span,{})})})]})})]})]})})]})," look like integers in the range ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsxs(e.mrow,{children:[s.jsx(e.mo,{stretchy:"false",children:"{"}),s.jsx(e.mn,{children:"0"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsx(e.mo,{children:"…"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsx(e.mi,{children:"p"}),s.jsx(e.mo,{children:"−"}),s.jsx(e.mn,{children:"1"}),s.jsx(e.mo,{stretchy:"false",children:"}"})]}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\{0, \\ldots , p - 1\\}"})]})})}),s.jsxs(e.span,{className:"katex-html","aria-hidden":"true",children:[s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),s.jsx(e.span,{className:"mopen",children:"{"}),s.jsx(e.span,{className:"mord",children:"0"}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"minner",children:"…"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"mord mathnormal",children:"p"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),s.jsx(e.span,{className:"mbin",children:"−"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),s.jsx(e.span,{className:"mord",children:"1"}),s.jsx(e.span,{className:"mclose",children:"}"})]})]})]}),"; arithmetic is done modulo ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsx(e.mrow,{children:s.jsx(e.mi,{children:"p"})}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"p"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),s.jsx(e.span,{className:"mord mathnormal",children:"p"})]})})]}),"."]}),`
12`,s.jsxs(e.p,{children:["These integers take ",s.jsx(e.em,{children:"almost"})," 32 bits to represent—but not quite. Indeed, at the level of bits, these integers look essentially like 32-bit binary strings—with the caveat that strings representing integers in the upper range ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsxs(e.mrow,{children:[s.jsx(e.mo,{stretchy:"false",children:"{"}),s.jsx(e.mi,{children:"p"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsx(e.mo,{children:"…"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsxs(e.msup,{children:[s.jsx(e.mn,{children:"2"}),s.jsx(e.mn,{children:"32"})]}),s.jsx(e.mo,{children:"−"}),s.jsx(e.mn,{children:"1"}),s.jsx(e.mo,{stretchy:"false",children:"}"})]}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\{p, \\ldots , 2^{32} - 1\\}"})]})})}),s.jsxs(e.span,{className:"katex-html","aria-hidden":"true",children:[s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"1.0641em",verticalAlign:"-0.25em"}}),s.jsx(e.span,{className:"mopen",children:"{"}),s.jsx(e.span,{className:"mord mathnormal",children:"p"}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"minner",children:"…"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord",children:"2"}),s.jsx(e.span,{className:"msupsub",children:s.jsx(e.span,{className:"vlist-t",children:s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.8141em"}

12,children:s.jsxs(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mtight",children:s.jsx(e.span,{className:"mord mtight",children:"32"})})})]})})})})})]}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),s.jsx(e.span,{className:"mbin",children:"−"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),s.jsx(e.span,{className:"mord",children:"1"}),s.jsx(e.span,{className:"mclose",children:"}"})]})]})]}),' are not allowed. Elements in this range are called "non-canonical", since by subtracting off some multiples of ',s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsx(e.mrow,{children:s.jsx(e.mi,{children:"p"})}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"p"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),s.jsx(e.span,{className:"mord mathnormal",children:"p"})]})})]}),", we can replace them with elements of the canonical range ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsxs(e.mrow,{children:[s.jsx(e.mo,{stretchy:"false",children:"{"}),s.jsx(e.mn,{children:"0"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsx(e.mo,{children:"…"}),s.jsx(e.mo,{separator:"true",children:","}),s.jsx(e.mi,{children:"p"}),s.jsx(e.mo,{children:"−"}),s.jsx(e.mn,{children:"1"}),s.jsx(e.mo,{stretchy:"false",children:"}"})]}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\{0, \\ldots , p - 1\\}"})]})})}),s.jsxs(e.span,{className:"katex-html","aria-hidden":"true",children:[s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),s.jsx(e.span,{className:"mopen",children:"{"}),s.jsx(e.span,{className:"mord",children:"0"}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"minner",children:"…"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"mpunct",children:","}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.1667em"}}),s.jsx(e.span,{className:"mord mathnormal",children:"p"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),s.jsx(e.span,{className:"mbin",children:"−"}),s.jsx(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),s.jsx(e.span,{className:"mord",children:"1"}),s.jsx(e.span,{className:"mclose",children:"}"})]})]})]}),"."]}),`
13`,s.jsxs(e.p,{children:["In Binius, the field ",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsx(e.mrow,{children:s.jsxs(e.msub,{children:[s.jsx(e.mi,{mathvariant:"script",children:"T"}),s.jsx(e.mi,{children:"ι"})]})}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"\\mathcal{T}_\\iota"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.8333em",verticalAlign:"-0.15em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord mathcal",style:{marginRight:"0.25417em"},children:"T"}),s.jsx(e.span,{className:"msupsub",children:s.jsxs(e.span,{className:"vlist-t vlist-t2",children:[s.jsxs(e.span,{className:"vlist-r",children:[s.jsx(e.span,{className:"vlist",style:{height:"0.1514em"}

13,children:s.jsxs(e.span,{style:{top:"-2.55em",marginLeft:"-0.2542em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mathnormal mtight",children:"ι"})})]})}),s.jsx(e.span,{className:"vlist-s",children:"​"})]}),s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.15em"},children:s.jsx(e.span,{})})})]})})]})]})})]}),"'s elements map ",s.jsx(e.em,{children:"exactly"})," to the set of length-",s.jsxs(e.span,{className:"katex",children:[s.jsx(e.span,{className:"katex-mathml",children:s.jsx(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:s.jsxs(e.semantics,{children:[s.jsx(e.mrow,{children:s.jsxs(e.msup,{children:[s.jsx(e.mn,{children:"2"}),s.jsx(e.mi,{children:"ι"})]})}),s.jsx(e.annotation,{encoding:"application/x-tex",children:"2^\\iota"})]})})}),s.jsx(e.span,{className:"katex-html","aria-hidden":"true",children:s.jsxs(e.span,{className:"base",children:[s.jsx(e.span,{className:"strut",style:{height:"0.6644em"}}),s.jsxs(e.span,{className:"mord",children:[s.jsx(e.span,{className:"mord",children:"2"}),s.jsx(e.span,{className:"msupsub",children:s.jsx(e.span,{className:"vlist-t",children:s.jsx(e.span,{className:"vlist-r",children:s.jsx(e.span,{className:"vlist",style:{height:"0.6644em"},children:s.jsxs(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[s.jsx(e.span,{className:"pstrut",style:{height:"2.7em"}}),s.jsx(e.span,{className:"sizing reset-size6 size3 mtight",children:s.jsx(e.span,{className:"mord mathnormal mtight",children:"ι"})})]})})})})})]})]})})]}),' bitstrings, in a perfect one-to-one correspondence. There are no "forbidden" or "non-canonical" bitstrings.']})]})}function m(a={}){const{wrapper:e}={...l(),...a.components};return e?s.jsx(e,{...a,children:s.jsx(n,{...a})}):n(a)}export{m as default,t as frontmatter};