12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412 |
- package bls12381
- import (
- "bytes"
- "crypto/rand"
- "math/big"
- "testing"
- )
- func TestFpSerialization(t *testing.T) {
- t.Run("zero", func(t *testing.T) {
- in := make([]byte, 48)
- fe, err := fromBytes(in)
- if err != nil {
- t.Fatal(err)
- }
- if !fe.isZero() {
- t.Fatal("bad serialization")
- }
- if !bytes.Equal(in, toBytes(fe)) {
- t.Fatal("bad serialization")
- }
- })
- t.Run("bytes", func(t *testing.T) {
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- b, err := fromBytes(toBytes(a))
- if err != nil {
- t.Fatal(err)
- }
- if !a.equal(b) {
- t.Fatal("bad serialization")
- }
- }
- })
- t.Run("string", func(t *testing.T) {
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- b, err := fromString(toString(a))
- if err != nil {
- t.Fatal(err)
- }
- if !a.equal(b) {
- t.Fatal("bad encoding or decoding")
- }
- }
- })
- t.Run("big", func(t *testing.T) {
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- b, err := fromBig(toBig(a))
- if err != nil {
- t.Fatal(err)
- }
- if !a.equal(b) {
- t.Fatal("bad encoding or decoding")
- }
- }
- })
- }
- func TestFpAdditionCrossAgainstBigInt(t *testing.T) {
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- b, _ := new(fe).rand(rand.Reader)
- c := new(fe)
- big_a := toBig(a)
- big_b := toBig(b)
- big_c := new(big.Int)
- add(c, a, b)
- out_1 := toBytes(c)
- out_2 := padBytes(big_c.Add(big_a, big_b).Mod(big_c, modulus.big()).Bytes(), 48)
- if !bytes.Equal(out_1, out_2) {
- t.Fatal("cross test against big.Int is not satisfied A")
- }
- double(c, a)
- out_1 = toBytes(c)
- out_2 = padBytes(big_c.Add(big_a, big_a).Mod(big_c, modulus.big()).Bytes(), 48)
- if !bytes.Equal(out_1, out_2) {
- t.Fatal("cross test against big.Int is not satisfied B")
- }
- sub(c, a, b)
- out_1 = toBytes(c)
- out_2 = padBytes(big_c.Sub(big_a, big_b).Mod(big_c, modulus.big()).Bytes(), 48)
- if !bytes.Equal(out_1, out_2) {
- t.Fatal("cross test against big.Int is not satisfied C")
- }
- neg(c, a)
- out_1 = toBytes(c)
- out_2 = padBytes(big_c.Neg(big_a).Mod(big_c, modulus.big()).Bytes(), 48)
- if !bytes.Equal(out_1, out_2) {
- t.Fatal("cross test against big.Int is not satisfied D")
- }
- }
- }
- func TestFpAdditionCrossAgainstBigIntAssigned(t *testing.T) {
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- b, _ := new(fe).rand(rand.Reader)
- big_a, big_b := toBig(a), toBig(b)
- addAssign(a, b)
- out_1 := toBytes(a)
- out_2 := padBytes(big_a.Add(big_a, big_b).Mod(big_a, modulus.big()).Bytes(), 48)
- if !bytes.Equal(out_1, out_2) {
- t.Fatal("cross test against big.Int is not satisfied A")
- }
- a, _ = new(fe).rand(rand.Reader)
- big_a = toBig(a)
- doubleAssign(a)
- out_1 = toBytes(a)
- out_2 = padBytes(big_a.Add(big_a, big_a).Mod(big_a, modulus.big()).Bytes(), 48)
- if !bytes.Equal(out_1, out_2) {
- t.Fatal("cross test against big.Int is not satisfied B")
- }
- a, _ = new(fe).rand(rand.Reader)
- b, _ = new(fe).rand(rand.Reader)
- big_a, big_b = toBig(a), toBig(b)
- subAssign(a, b)
- out_1 = toBytes(a)
- out_2 = padBytes(big_a.Sub(big_a, big_b).Mod(big_a, modulus.big()).Bytes(), 48)
- if !bytes.Equal(out_1, out_2) {
- t.Fatal("cross test against big.Int is not satisfied A")
- }
- }
- }
- func TestFpAdditionProperties(t *testing.T) {
- for i := 0; i < fuz; i++ {
- zero := new(fe).zero()
- a, _ := new(fe).rand(rand.Reader)
- b, _ := new(fe).rand(rand.Reader)
- c_1, c_2 := new(fe), new(fe)
- add(c_1, a, zero)
- if !c_1.equal(a) {
- t.Fatal("a + 0 == a")
- }
- sub(c_1, a, zero)
- if !c_1.equal(a) {
- t.Fatal("a - 0 == a")
- }
- double(c_1, zero)
- if !c_1.equal(zero) {
- t.Fatal("2 * 0 == 0")
- }
- neg(c_1, zero)
- if !c_1.equal(zero) {
- t.Fatal("-0 == 0")
- }
- sub(c_1, zero, a)
- neg(c_2, a)
- if !c_1.equal(c_2) {
- t.Fatal("0-a == -a")
- }
- double(c_1, a)
- add(c_2, a, a)
- if !c_1.equal(c_2) {
- t.Fatal("2 * a == a + a")
- }
- add(c_1, a, b)
- add(c_2, b, a)
- if !c_1.equal(c_2) {
- t.Fatal("a + b = b + a")
- }
- sub(c_1, a, b)
- sub(c_2, b, a)
- neg(c_2, c_2)
- if !c_1.equal(c_2) {
- t.Fatal("a - b = - ( b - a )")
- }
- c_x, _ := new(fe).rand(rand.Reader)
- add(c_1, a, b)
- add(c_1, c_1, c_x)
- add(c_2, a, c_x)
- add(c_2, c_2, b)
- if !c_1.equal(c_2) {
- t.Fatal("(a + b) + c == (a + c ) + b")
- }
- sub(c_1, a, b)
- sub(c_1, c_1, c_x)
- sub(c_2, a, c_x)
- sub(c_2, c_2, b)
- if !c_1.equal(c_2) {
- t.Fatal("(a - b) - c == (a - c ) -b")
- }
- }
- }
- func TestFpAdditionPropertiesAssigned(t *testing.T) {
- for i := 0; i < fuz; i++ {
- zero := new(fe).zero()
- a, b := new(fe), new(fe)
- _, _ = a.rand(rand.Reader)
- b.set(a)
- addAssign(a, zero)
- if !a.equal(b) {
- t.Fatal("a + 0 == a")
- }
- subAssign(a, zero)
- if !a.equal(b) {
- t.Fatal("a - 0 == a")
- }
- a.set(zero)
- doubleAssign(a)
- if !a.equal(zero) {
- t.Fatal("2 * 0 == 0")
- }
- a.set(zero)
- subAssign(a, b)
- neg(b, b)
- if !a.equal(b) {
- t.Fatal("0-a == -a")
- }
- _, _ = a.rand(rand.Reader)
- b.set(a)
- doubleAssign(a)
- addAssign(b, b)
- if !a.equal(b) {
- t.Fatal("2 * a == a + a")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- c_1, c_2 := new(fe).set(a), new(fe).set(b)
- addAssign(c_1, b)
- addAssign(c_2, a)
- if !c_1.equal(c_2) {
- t.Fatal("a + b = b + a")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- c_1.set(a)
- c_2.set(b)
- subAssign(c_1, b)
- subAssign(c_2, a)
- neg(c_2, c_2)
- if !c_1.equal(c_2) {
- t.Fatal("a - b = - ( b - a )")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- c, _ := new(fe).rand(rand.Reader)
- a0 := new(fe).set(a)
- addAssign(a, b)
- addAssign(a, c)
- addAssign(b, c)
- addAssign(b, a0)
- if !a.equal(b) {
- t.Fatal("(a + b) + c == (b + c) + a")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- _, _ = c.rand(rand.Reader)
- a0.set(a)
- subAssign(a, b)
- subAssign(a, c)
- subAssign(a0, c)
- subAssign(a0, b)
- if !a.equal(a0) {
- t.Fatal("(a - b) - c == (a - c) -b")
- }
- }
- }
- func TestFpLazyOperations(t *testing.T) {
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- b, _ := new(fe).rand(rand.Reader)
- c, _ := new(fe).rand(rand.Reader)
- c0 := new(fe)
- c1 := new(fe)
- ladd(c0, a, b)
- add(c1, a, b)
- mul(c0, c0, c)
- mul(c1, c1, c)
- if !c0.equal(c1) {
- // l+ operator stands for lazy addition
- t.Fatal("(a + b) * c == (a l+ b) * c")
- }
- _, _ = a.rand(rand.Reader)
- b.set(a)
- ldouble(a, a)
- ladd(b, b, b)
- if !a.equal(b) {
- t.Fatal("2 l* a = a l+ a")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- _, _ = c.rand(rand.Reader)
- a0 := new(fe).set(a)
- lsubAssign(a, b)
- laddAssign(a, &modulus)
- mul(a, a, c)
- subAssign(a0, b)
- mul(a0, a0, c)
- if !a.equal(a0) {
- t.Fatal("((a l- b) + p) * c = (a-b) * c")
- }
- }
- }
- func TestFpMultiplicationCrossAgainstBigInt(t *testing.T) {
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- b, _ := new(fe).rand(rand.Reader)
- c := new(fe)
- big_a := toBig(a)
- big_b := toBig(b)
- big_c := new(big.Int)
- mul(c, a, b)
- out_1 := toBytes(c)
- out_2 := padBytes(big_c.Mul(big_a, big_b).Mod(big_c, modulus.big()).Bytes(), 48)
- if !bytes.Equal(out_1, out_2) {
- t.Fatal("cross test against big.Int is not satisfied")
- }
- }
- }
- func TestFpMultiplicationProperties(t *testing.T) {
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- b, _ := new(fe).rand(rand.Reader)
- zero, one := new(fe).zero(), new(fe).one()
- c_1, c_2 := new(fe), new(fe)
- mul(c_1, a, zero)
- if !c_1.equal(zero) {
- t.Fatal("a * 0 == 0")
- }
- mul(c_1, a, one)
- if !c_1.equal(a) {
- t.Fatal("a * 1 == a")
- }
- mul(c_1, a, b)
- mul(c_2, b, a)
- if !c_1.equal(c_2) {
- t.Fatal("a * b == b * a")
- }
- c_x, _ := new(fe).rand(rand.Reader)
- mul(c_1, a, b)
- mul(c_1, c_1, c_x)
- mul(c_2, c_x, b)
- mul(c_2, c_2, a)
- if !c_1.equal(c_2) {
- t.Fatal("(a * b) * c == (a * c) * b")
- }
- square(a, zero)
- if !a.equal(zero) {
- t.Fatal("0^2 == 0")
- }
- square(a, one)
- if !a.equal(one) {
- t.Fatal("1^2 == 1")
- }
- _, _ = a.rand(rand.Reader)
- square(c_1, a)
- mul(c_2, a, a)
- if !c_1.equal(c_1) {
- t.Fatal("a^2 == a*a")
- }
- }
- }
- func TestFpExponentiation(t *testing.T) {
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- u := new(fe)
- exp(u, a, big.NewInt(0))
- if !u.isOne() {
- t.Fatal("a^0 == 1")
- }
- exp(u, a, big.NewInt(1))
- if !u.equal(a) {
- t.Fatal("a^1 == a")
- }
- v := new(fe)
- mul(u, a, a)
- mul(u, u, u)
- mul(u, u, u)
- exp(v, a, big.NewInt(8))
- if !u.equal(v) {
- t.Fatal("((a^2)^2)^2 == a^8")
- }
- p := modulus.big()
- exp(u, a, p)
- if !u.equal(a) {
- t.Fatal("a^p == a")
- }
- exp(u, a, p.Sub(p, big.NewInt(1)))
- if !u.isOne() {
- t.Fatal("a^(p-1) == 1")
- }
- }
- }
- func TestFpInversion(t *testing.T) {
- for i := 0; i < fuz; i++ {
- u := new(fe)
- zero, one := new(fe).zero(), new(fe).one()
- inverse(u, zero)
- if !u.equal(zero) {
- t.Fatal("(0^-1) == 0)")
- }
- inverse(u, one)
- if !u.equal(one) {
- t.Fatal("(1^-1) == 1)")
- }
- a, _ := new(fe).rand(rand.Reader)
- inverse(u, a)
- mul(u, u, a)
- if !u.equal(one) {
- t.Fatal("(r*a) * r*(a^-1) == r)")
- }
- v := new(fe)
- p := modulus.big()
- exp(u, a, p.Sub(p, big.NewInt(2)))
- inverse(v, a)
- if !v.equal(u) {
- t.Fatal("a^(p-2) == a^-1")
- }
- }
- }
- func TestFpSquareRoot(t *testing.T) {
- r := new(fe)
- if sqrt(r, nonResidue1) {
- t.Fatal("non residue cannot have a sqrt")
- }
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- aa, rr, r := &fe{}, &fe{}, &fe{}
- square(aa, a)
- if !sqrt(r, aa) {
- t.Fatal("bad sqrt 1")
- }
- square(rr, r)
- if !rr.equal(aa) {
- t.Fatal("bad sqrt 2")
- }
- }
- }
- func TestFpNonResidue(t *testing.T) {
- if !isQuadraticNonResidue(nonResidue1) {
- t.Fatal("element is quadratic non residue, 1")
- }
- if isQuadraticNonResidue(new(fe).one()) {
- t.Fatal("one is not quadratic non residue")
- }
- if !isQuadraticNonResidue(new(fe).zero()) {
- t.Fatal("should accept zero as quadratic non residue")
- }
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- square(a, a)
- if isQuadraticNonResidue(new(fe).one()) {
- t.Fatal("element is not quadratic non residue")
- }
- }
- for i := 0; i < fuz; i++ {
- a, _ := new(fe).rand(rand.Reader)
- if !sqrt(new(fe), a) {
- if !isQuadraticNonResidue(a) {
- t.Fatal("element is quadratic non residue, 2", i)
- }
- } else {
- i -= 1
- }
- }
- }
- func TestFp2Serialization(t *testing.T) {
- field := newFp2()
- for i := 0; i < fuz; i++ {
- a, _ := new(fe2).rand(rand.Reader)
- b, err := field.fromBytes(field.toBytes(a))
- if err != nil {
- t.Fatal(err)
- }
- if !a.equal(b) {
- t.Fatal("bad serialization")
- }
- }
- }
- func TestFp2AdditionProperties(t *testing.T) {
- field := newFp2()
- for i := 0; i < fuz; i++ {
- zero := field.zero()
- a, _ := new(fe2).rand(rand.Reader)
- b, _ := new(fe2).rand(rand.Reader)
- c_1 := field.new()
- c_2 := field.new()
- field.add(c_1, a, zero)
- if !c_1.equal(a) {
- t.Fatal("a + 0 == a")
- }
- field.sub(c_1, a, zero)
- if !c_1.equal(a) {
- t.Fatal("a - 0 == a")
- }
- field.double(c_1, zero)
- if !c_1.equal(zero) {
- t.Fatal("2 * 0 == 0")
- }
- field.neg(c_1, zero)
- if !c_1.equal(zero) {
- t.Fatal("-0 == 0")
- }
- field.sub(c_1, zero, a)
- field.neg(c_2, a)
- if !c_1.equal(c_2) {
- t.Fatal("0-a == -a")
- }
- field.double(c_1, a)
- field.add(c_2, a, a)
- if !c_1.equal(c_2) {
- t.Fatal("2 * a == a + a")
- }
- field.add(c_1, a, b)
- field.add(c_2, b, a)
- if !c_1.equal(c_2) {
- t.Fatal("a + b = b + a")
- }
- field.sub(c_1, a, b)
- field.sub(c_2, b, a)
- field.neg(c_2, c_2)
- if !c_1.equal(c_2) {
- t.Fatal("a - b = - ( b - a )")
- }
- c_x, _ := new(fe2).rand(rand.Reader)
- field.add(c_1, a, b)
- field.add(c_1, c_1, c_x)
- field.add(c_2, a, c_x)
- field.add(c_2, c_2, b)
- if !c_1.equal(c_2) {
- t.Fatal("(a + b) + c == (a + c ) + b")
- }
- field.sub(c_1, a, b)
- field.sub(c_1, c_1, c_x)
- field.sub(c_2, a, c_x)
- field.sub(c_2, c_2, b)
- if !c_1.equal(c_2) {
- t.Fatal("(a - b) - c == (a - c ) -b")
- }
- }
- }
- func TestFp2AdditionPropertiesAssigned(t *testing.T) {
- field := newFp2()
- for i := 0; i < fuz; i++ {
- zero := new(fe2).zero()
- a, b := new(fe2), new(fe2)
- _, _ = a.rand(rand.Reader)
- b.set(a)
- field.addAssign(a, zero)
- if !a.equal(b) {
- t.Fatal("a + 0 == a")
- }
- field.subAssign(a, zero)
- if !a.equal(b) {
- t.Fatal("a - 0 == a")
- }
- a.set(zero)
- field.doubleAssign(a)
- if !a.equal(zero) {
- t.Fatal("2 * 0 == 0")
- }
- a.set(zero)
- field.subAssign(a, b)
- field.neg(b, b)
- if !a.equal(b) {
- t.Fatal("0-a == -a")
- }
- _, _ = a.rand(rand.Reader)
- b.set(a)
- field.doubleAssign(a)
- field.addAssign(b, b)
- if !a.equal(b) {
- t.Fatal("2 * a == a + a")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- c_1, c_2 := new(fe2).set(a), new(fe2).set(b)
- field.addAssign(c_1, b)
- field.addAssign(c_2, a)
- if !c_1.equal(c_2) {
- t.Fatal("a + b = b + a")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- c_1.set(a)
- c_2.set(b)
- field.subAssign(c_1, b)
- field.subAssign(c_2, a)
- field.neg(c_2, c_2)
- if !c_1.equal(c_2) {
- t.Fatal("a - b = - ( b - a )")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- c, _ := new(fe2).rand(rand.Reader)
- a0 := new(fe2).set(a)
- field.addAssign(a, b)
- field.addAssign(a, c)
- field.addAssign(b, c)
- field.addAssign(b, a0)
- if !a.equal(b) {
- t.Fatal("(a + b) + c == (b + c) + a")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- _, _ = c.rand(rand.Reader)
- a0.set(a)
- field.subAssign(a, b)
- field.subAssign(a, c)
- field.subAssign(a0, c)
- field.subAssign(a0, b)
- if !a.equal(a0) {
- t.Fatal("(a - b) - c == (a - c) -b")
- }
- }
- }
- func TestFp2LazyOperations(t *testing.T) {
- field := newFp2()
- for i := 0; i < fuz; i++ {
- a, _ := new(fe2).rand(rand.Reader)
- b, _ := new(fe2).rand(rand.Reader)
- c, _ := new(fe2).rand(rand.Reader)
- c0 := new(fe2)
- c1 := new(fe2)
- field.ladd(c0, a, b)
- field.add(c1, a, b)
- field.mulAssign(c0, c)
- field.mulAssign(c1, c)
- if !c0.equal(c1) {
- // l+ operator stands for lazy addition
- t.Fatal("(a + b) * c == (a l+ b) * c")
- }
- _, _ = a.rand(rand.Reader)
- b.set(a)
- field.ldouble(a, a)
- field.ladd(b, b, b)
- if !a.equal(b) {
- t.Fatal("2 l* a = a l+ a")
- }
- }
- }
- func TestFp2MultiplicationProperties(t *testing.T) {
- field := newFp2()
- for i := 0; i < fuz; i++ {
- a, _ := new(fe2).rand(rand.Reader)
- b, _ := new(fe2).rand(rand.Reader)
- zero := field.zero()
- one := field.one()
- c_1, c_2 := field.new(), field.new()
- field.mul(c_1, a, zero)
- if !c_1.equal(zero) {
- t.Fatal("a * 0 == 0")
- }
- field.mul(c_1, a, one)
- if !c_1.equal(a) {
- t.Fatal("a * 1 == a")
- }
- field.mul(c_1, a, b)
- field.mul(c_2, b, a)
- if !c_1.equal(c_2) {
- t.Fatal("a * b == b * a")
- }
- c_x, _ := new(fe2).rand(rand.Reader)
- field.mul(c_1, a, b)
- field.mul(c_1, c_1, c_x)
- field.mul(c_2, c_x, b)
- field.mul(c_2, c_2, a)
- if !c_1.equal(c_2) {
- t.Fatal("(a * b) * c == (a * c) * b")
- }
- field.square(a, zero)
- if !a.equal(zero) {
- t.Fatal("0^2 == 0")
- }
- field.square(a, one)
- if !a.equal(one) {
- t.Fatal("1^2 == 1")
- }
- _, _ = a.rand(rand.Reader)
- field.square(c_1, a)
- field.mul(c_2, a, a)
- if !c_2.equal(c_1) {
- t.Fatal("a^2 == a*a")
- }
- }
- }
- func TestFp2MultiplicationPropertiesAssigned(t *testing.T) {
- field := newFp2()
- for i := 0; i < fuz; i++ {
- a, _ := new(fe2).rand(rand.Reader)
- zero, one := new(fe2).zero(), new(fe2).one()
- field.mulAssign(a, zero)
- if !a.equal(zero) {
- t.Fatal("a * 0 == 0")
- }
- _, _ = a.rand(rand.Reader)
- a0 := new(fe2).set(a)
- field.mulAssign(a, one)
- if !a.equal(a0) {
- t.Fatal("a * 1 == a")
- }
- _, _ = a.rand(rand.Reader)
- b, _ := new(fe2).rand(rand.Reader)
- a0.set(a)
- field.mulAssign(a, b)
- field.mulAssign(b, a0)
- if !a.equal(b) {
- t.Fatal("a * b == b * a")
- }
- c, _ := new(fe2).rand(rand.Reader)
- a0.set(a)
- field.mulAssign(a, b)
- field.mulAssign(a, c)
- field.mulAssign(a0, c)
- field.mulAssign(a0, b)
- if !a.equal(a0) {
- t.Fatal("(a * b) * c == (a * c) * b")
- }
- a0.set(a)
- field.squareAssign(a)
- field.mulAssign(a0, a0)
- if !a.equal(a0) {
- t.Fatal("a^2 == a*a")
- }
- }
- }
- func TestFp2Exponentiation(t *testing.T) {
- field := newFp2()
- for i := 0; i < fuz; i++ {
- a, _ := new(fe2).rand(rand.Reader)
- u := field.new()
- field.exp(u, a, big.NewInt(0))
- if !u.equal(field.one()) {
- t.Fatal("a^0 == 1")
- }
- field.exp(u, a, big.NewInt(1))
- if !u.equal(a) {
- t.Fatal("a^1 == a")
- }
- v := field.new()
- field.mul(u, a, a)
- field.mul(u, u, u)
- field.mul(u, u, u)
- field.exp(v, a, big.NewInt(8))
- if !u.equal(v) {
- t.Fatal("((a^2)^2)^2 == a^8")
- }
- }
- }
- func TestFp2Inversion(t *testing.T) {
- field := newFp2()
- u := field.new()
- zero := field.zero()
- one := field.one()
- field.inverse(u, zero)
- if !u.equal(zero) {
- t.Fatal("(0 ^ -1) == 0)")
- }
- field.inverse(u, one)
- if !u.equal(one) {
- t.Fatal("(1 ^ -1) == 1)")
- }
- for i := 0; i < fuz; i++ {
- a, _ := new(fe2).rand(rand.Reader)
- field.inverse(u, a)
- field.mul(u, u, a)
- if !u.equal(one) {
- t.Fatal("(r * a) * r * (a ^ -1) == r)")
- }
- }
- }
- func TestFp2SquareRoot(t *testing.T) {
- field := newFp2()
- for z := 0; z < 1000; z++ {
- zi := new(fe)
- sub(zi, &modulus, &fe{uint64(z * z)})
- // r = (-z*z, 0)
- r := &fe2{*zi, fe{0}}
- toMont(&r[0], &r[0])
- toMont(&r[1], &r[1])
- c := field.new()
- // sqrt((-z*z, 0)) = (0, z)
- if !field.sqrt(c, r) {
- t.Fatal("z*z does have a square root")
- }
- e := &fe2{fe{uint64(0)}, fe{uint64(z)}}
- toMont(&e[0], &e[0])
- toMont(&e[1], &e[1])
- field.square(e, e)
- field.square(c, c)
- if !e.equal(c) {
- t.Fatal("square root failed")
- }
- }
- if field.sqrt(field.new(), nonResidue2) {
- t.Fatal("non residue cannot have a sqrt")
- }
- for i := 0; i < fuz; i++ {
- a, _ := new(fe2).rand(rand.Reader)
- aa, rr, r := field.new(), field.new(), field.new()
- field.square(aa, a)
- if !field.sqrt(r, aa) {
- t.Fatal("bad sqrt 1")
- }
- field.square(rr, r)
- if !rr.equal(aa) {
- t.Fatal("bad sqrt 2")
- }
- }
- }
- func TestFp2NonResidue(t *testing.T) {
- field := newFp2()
- if !field.isQuadraticNonResidue(nonResidue2) {
- t.Fatal("element is quadratic non residue, 1")
- }
- if field.isQuadraticNonResidue(new(fe2).one()) {
- t.Fatal("one is not quadratic non residue")
- }
- if !field.isQuadraticNonResidue(new(fe2).zero()) {
- t.Fatal("should accept zero as quadratic non residue")
- }
- for i := 0; i < fuz; i++ {
- a, _ := new(fe2).rand(rand.Reader)
- field.squareAssign(a)
- if field.isQuadraticNonResidue(new(fe2).one()) {
- t.Fatal("element is not quadratic non residue")
- }
- }
- for i := 0; i < fuz; i++ {
- a, _ := new(fe2).rand(rand.Reader)
- if !field.sqrt(new(fe2), a) {
- if !field.isQuadraticNonResidue(a) {
- t.Fatal("element is quadratic non residue, 2", i)
- }
- } else {
- i -= 1
- }
- }
- }
- func TestFp6Serialization(t *testing.T) {
- field := newFp6(nil)
- for i := 0; i < fuz; i++ {
- a, _ := new(fe6).rand(rand.Reader)
- b, err := field.fromBytes(field.toBytes(a))
- if err != nil {
- t.Fatal(err)
- }
- if !a.equal(b) {
- t.Fatal("bad serialization")
- }
- }
- }
- func TestFp6AdditionProperties(t *testing.T) {
- field := newFp6(nil)
- for i := 0; i < fuz; i++ {
- zero := field.zero()
- a, _ := new(fe6).rand(rand.Reader)
- b, _ := new(fe6).rand(rand.Reader)
- c_1 := field.new()
- c_2 := field.new()
- field.add(c_1, a, zero)
- if !c_1.equal(a) {
- t.Fatal("a + 0 == a")
- }
- field.sub(c_1, a, zero)
- if !c_1.equal(a) {
- t.Fatal("a - 0 == a")
- }
- field.double(c_1, zero)
- if !c_1.equal(zero) {
- t.Fatal("2 * 0 == 0")
- }
- field.neg(c_1, zero)
- if !c_1.equal(zero) {
- t.Fatal("-0 == 0")
- }
- field.sub(c_1, zero, a)
- field.neg(c_2, a)
- if !c_1.equal(c_2) {
- t.Fatal("0-a == -a")
- }
- field.double(c_1, a)
- field.add(c_2, a, a)
- if !c_1.equal(c_2) {
- t.Fatal("2 * a == a + a")
- }
- field.add(c_1, a, b)
- field.add(c_2, b, a)
- if !c_1.equal(c_2) {
- t.Fatal("a + b = b + a")
- }
- field.sub(c_1, a, b)
- field.sub(c_2, b, a)
- field.neg(c_2, c_2)
- if !c_1.equal(c_2) {
- t.Fatal("a - b = - ( b - a )")
- }
- c_x, _ := new(fe6).rand(rand.Reader)
- field.add(c_1, a, b)
- field.add(c_1, c_1, c_x)
- field.add(c_2, a, c_x)
- field.add(c_2, c_2, b)
- if !c_1.equal(c_2) {
- t.Fatal("(a + b) + c == (a + c ) + b")
- }
- field.sub(c_1, a, b)
- field.sub(c_1, c_1, c_x)
- field.sub(c_2, a, c_x)
- field.sub(c_2, c_2, b)
- if !c_1.equal(c_2) {
- t.Fatal("(a - b) - c == (a - c ) -b")
- }
- }
- }
- func TestFp6AdditionPropertiesAssigned(t *testing.T) {
- field := newFp6(nil)
- for i := 0; i < fuz; i++ {
- zero := new(fe6).zero()
- a, b := new(fe6), new(fe6)
- _, _ = a.rand(rand.Reader)
- b.set(a)
- field.addAssign(a, zero)
- if !a.equal(b) {
- t.Fatal("a + 0 == a")
- }
- field.subAssign(a, zero)
- if !a.equal(b) {
- t.Fatal("a - 0 == a")
- }
- a.set(zero)
- field.doubleAssign(a)
- if !a.equal(zero) {
- t.Fatal("2 * 0 == 0")
- }
- a.set(zero)
- field.subAssign(a, b)
- field.neg(b, b)
- if !a.equal(b) {
- t.Fatal("0-a == -a")
- }
- _, _ = a.rand(rand.Reader)
- b.set(a)
- field.doubleAssign(a)
- field.addAssign(b, b)
- if !a.equal(b) {
- t.Fatal("2 * a == a + a")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- c_1, c_2 := new(fe6).set(a), new(fe6).set(b)
- field.addAssign(c_1, b)
- field.addAssign(c_2, a)
- if !c_1.equal(c_2) {
- t.Fatal("a + b = b + a")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- c_1.set(a)
- c_2.set(b)
- field.subAssign(c_1, b)
- field.subAssign(c_2, a)
- field.neg(c_2, c_2)
- if !c_1.equal(c_2) {
- t.Fatal("a - b = - ( b - a )")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- c, _ := new(fe6).rand(rand.Reader)
- a0 := new(fe6).set(a)
- field.addAssign(a, b)
- field.addAssign(a, c)
- field.addAssign(b, c)
- field.addAssign(b, a0)
- if !a.equal(b) {
- t.Fatal("(a + b) + c == (b + c) + a")
- }
- _, _ = a.rand(rand.Reader)
- _, _ = b.rand(rand.Reader)
- _, _ = c.rand(rand.Reader)
- a0.set(a)
- field.subAssign(a, b)
- field.subAssign(a, c)
- field.subAssign(a0, c)
- field.subAssign(a0, b)
- if !a.equal(a0) {
- t.Fatal("(a - b) - c == (a - c) -b")
- }
- }
- }
- func TestFp6SparseMultiplication(t *testing.T) {
- fp6 := newFp6(nil)
- var a, b, u *fe6
- for j := 0; j < fuz; j++ {
- a, _ = new(fe6).rand(rand.Reader)
- b, _ = new(fe6).rand(rand.Reader)
- u, _ = new(fe6).rand(rand.Reader)
- b[2].zero()
- fp6.mul(u, a, b)
- fp6.mulBy01(a, a, &b[0], &b[1])
- if !a.equal(u) {
- t.Fatal("bad mul by 01")
- }
- }
- for j := 0; j < fuz; j++ {
- a, _ = new(fe6).rand(rand.Reader)
- b, _ = new(fe6).rand(rand.Reader)
- u, _ = new(fe6).rand(rand.Reader)
- b[2].zero()
- b[0].zero()
- fp6.mul(u, a, b)
- fp6.mulBy1(a, a, &b[1])
- if !a.equal(u) {
- t.Fatal("bad mul by 1")
- }
- }
- }
- func TestFp6MultiplicationProperties(t *testing.T) {
- field := newFp6(nil)
- for i := 0; i < fuz; i++ {
- a, _ := new(fe6).rand(rand.Reader)
- b, _ := new(fe6).rand(rand.Reader)
- zero := field.zero()
- one := field.one()
- c_1, c_2 := field.new(), field.new()
- field.mul(c_1, a, zero)
- if !c_1.equal(zero) {
- t.Fatal("a * 0 == 0")
- }
- field.mul(c_1, a, one)
- if !c_1.equal(a) {
- t.Fatal("a * 1 == a")
- }
- field.mul(c_1, a, b)
- field.mul(c_2, b, a)
- if !c_1.equal(c_2) {
- t.Fatal("a * b == b * a")
- }
- c_x, _ := new(fe6).rand(rand.Reader)
- field.mul(c_1, a, b)
- field.mul(c_1, c_1, c_x)
- field.mul(c_2, c_x, b)
- field.mul(c_2, c_2, a)
- if !c_1.equal(c_2) {
- t.Fatal("(a * b) * c == (a * c) * b")
- }
- field.square(a, zero)
- if !a.equal(zero) {
- t.Fatal("0^2 == 0")
- }
- field.square(a, one)
- if !a.equal(one) {
- t.Fatal("1^2 == 1")
- }
- _, _ = a.rand(rand.Reader)
- field.square(c_1, a)
- field.mul(c_2, a, a)
- if !c_2.equal(c_1) {
- t.Fatal("a^2 == a*a")
- }
- }
- }
- func TestFp6MultiplicationPropertiesAssigned(t *testing.T) {
- field := newFp6(nil)
- for i := 0; i < fuz; i++ {
- a, _ := new(fe6).rand(rand.Reader)
- zero, one := new(fe6).zero(), new(fe6).one()
- field.mulAssign(a, zero)
- if !a.equal(zero) {
- t.Fatal("a * 0 == 0")
- }
- _, _ = a.rand(rand.Reader)
- a0 := new(fe6).set(a)
- field.mulAssign(a, one)
- if !a.equal(a0) {
- t.Fatal("a * 1 == a")
- }
- _, _ = a.rand(rand.Reader)
- b, _ := new(fe6).rand(rand.Reader)
- a0.set(a)
- field.mulAssign(a, b)
- field.mulAssign(b, a0)
- if !a.equal(b) {
- t.Fatal("a * b == b * a")
- }
- c, _ := new(fe6).rand(rand.Reader)
- a0.set(a)
- field.mulAssign(a, b)
- field.mulAssign(a, c)
- field.mulAssign(a0, c)
- field.mulAssign(a0, b)
- if !a.equal(a0) {
- t.Fatal("(a * b) * c == (a * c) * b")
- }
- }
- }
- func TestFp6Exponentiation(t *testing.T) {
- field := newFp6(nil)
- for i := 0; i < fuz; i++ {
- a, _ := new(fe6).rand(rand.Reader)
- u := field.new()
- field.exp(u, a, big.NewInt(0))
- if !u.equal(field.one()) {
- t.Fatal("a^0 == 1")
- }
- field.exp(u, a, big.NewInt(1))
- if !u.equal(a) {
- t.Fatal("a^1 == a")
- }
- v := field.new()
- field.mul(u, a, a)
- field.mul(u, u, u)
- field.mul(u, u, u)
- field.exp(v, a, big.NewInt(8))
- if !u.equal(v) {
- t.Fatal("((a^2)^2)^2 == a^8")
- }
- }
- }
- func TestFp6Inversion(t *testing.T) {
- field := newFp6(nil)
- for i := 0; i < fuz; i++ {
- u := field.new()
- zero := field.zero()
- one := field.one()
- field.inverse(u, zero)
- if !u.equal(zero) {
- t.Fatal("(0^-1) == 0)")
- }
- field.inverse(u, one)
- if !u.equal(one) {
- t.Fatal("(1^-1) == 1)")
- }
- a, _ := new(fe6).rand(rand.Reader)
- field.inverse(u, a)
- field.mul(u, u, a)
- if !u.equal(one) {
- t.Fatal("(r*a) * r*(a^-1) == r)")
- }
- }
- }
- func TestFp12Serialization(t *testing.T) {
- field := newFp12(nil)
- for i := 0; i < fuz; i++ {
- a, _ := new(fe12).rand(rand.Reader)
- b, err := field.fromBytes(field.toBytes(a))
- if err != nil {
- t.Fatal(err)
- }
- if !a.equal(b) {
- t.Fatal("bad serialization")
- }
- }
- }
- func TestFp12AdditionProperties(t *testing.T) {
- field := newFp12(nil)
- for i := 0; i < fuz; i++ {
- zero := field.zero()
- a, _ := new(fe12).rand(rand.Reader)
- b, _ := new(fe12).rand(rand.Reader)
- c_1 := field.new()
- c_2 := field.new()
- field.add(c_1, a, zero)
- if !c_1.equal(a) {
- t.Fatal("a + 0 == a")
- }
- field.sub(c_1, a, zero)
- if !c_1.equal(a) {
- t.Fatal("a - 0 == a")
- }
- field.double(c_1, zero)
- if !c_1.equal(zero) {
- t.Fatal("2 * 0 == 0")
- }
- field.neg(c_1, zero)
- if !c_1.equal(zero) {
- t.Fatal("-0 == 0")
- }
- field.sub(c_1, zero, a)
- field.neg(c_2, a)
- if !c_1.equal(c_2) {
- t.Fatal("0-a == -a")
- }
- field.double(c_1, a)
- field.add(c_2, a, a)
- if !c_1.equal(c_2) {
- t.Fatal("2 * a == a + a")
- }
- field.add(c_1, a, b)
- field.add(c_2, b, a)
- if !c_1.equal(c_2) {
- t.Fatal("a + b = b + a")
- }
- field.sub(c_1, a, b)
- field.sub(c_2, b, a)
- field.neg(c_2, c_2)
- if !c_1.equal(c_2) {
- t.Fatal("a - b = - ( b - a )")
- }
- c_x, _ := new(fe12).rand(rand.Reader)
- field.add(c_1, a, b)
- field.add(c_1, c_1, c_x)
- field.add(c_2, a, c_x)
- field.add(c_2, c_2, b)
- if !c_1.equal(c_2) {
- t.Fatal("(a + b) + c == (a + c ) + b")
- }
- field.sub(c_1, a, b)
- field.sub(c_1, c_1, c_x)
- field.sub(c_2, a, c_x)
- field.sub(c_2, c_2, b)
- if !c_1.equal(c_2) {
- t.Fatal("(a - b) - c == (a - c ) -b")
- }
- }
- }
- func TestFp12MultiplicationProperties(t *testing.T) {
- field := newFp12(nil)
- for i := 0; i < fuz; i++ {
- a, _ := new(fe12).rand(rand.Reader)
- b, _ := new(fe12).rand(rand.Reader)
- zero := field.zero()
- one := field.one()
- c_1, c_2 := field.new(), field.new()
- field.mul(c_1, a, zero)
- if !c_1.equal(zero) {
- t.Fatal("a * 0 == 0")
- }
- field.mul(c_1, a, one)
- if !c_1.equal(a) {
- t.Fatal("a * 1 == a")
- }
- field.mul(c_1, a, b)
- field.mul(c_2, b, a)
- if !c_1.equal(c_2) {
- t.Fatal("a * b == b * a")
- }
- c_x, _ := new(fe12).rand(rand.Reader)
- field.mul(c_1, a, b)
- field.mul(c_1, c_1, c_x)
- field.mul(c_2, c_x, b)
- field.mul(c_2, c_2, a)
- if !c_1.equal(c_2) {
- t.Fatal("(a * b) * c == (a * c) * b")
- }
- field.square(a, zero)
- if !a.equal(zero) {
- t.Fatal("0^2 == 0")
- }
- field.square(a, one)
- if !a.equal(one) {
- t.Fatal("1^2 == 1")
- }
- _, _ = a.rand(rand.Reader)
- field.square(c_1, a)
- field.mul(c_2, a, a)
- if !c_2.equal(c_1) {
- t.Fatal("a^2 == a*a")
- }
- }
- }
- func TestFp12MultiplicationPropertiesAssigned(t *testing.T) {
- field := newFp12(nil)
- for i := 0; i < fuz; i++ {
- a, _ := new(fe12).rand(rand.Reader)
- zero, one := new(fe12).zero(), new(fe12).one()
- field.mulAssign(a, zero)
- if !a.equal(zero) {
- t.Fatal("a * 0 == 0")
- }
- _, _ = a.rand(rand.Reader)
- a0 := new(fe12).set(a)
- field.mulAssign(a, one)
- if !a.equal(a0) {
- t.Fatal("a * 1 == a")
- }
- _, _ = a.rand(rand.Reader)
- b, _ := new(fe12).rand(rand.Reader)
- a0.set(a)
- field.mulAssign(a, b)
- field.mulAssign(b, a0)
- if !a.equal(b) {
- t.Fatal("a * b == b * a")
- }
- c, _ := new(fe12).rand(rand.Reader)
- a0.set(a)
- field.mulAssign(a, b)
- field.mulAssign(a, c)
- field.mulAssign(a0, c)
- field.mulAssign(a0, b)
- if !a.equal(a0) {
- t.Fatal("(a * b) * c == (a * c) * b")
- }
- }
- }
- func TestFp12SparseMultiplication(t *testing.T) {
- fp12 := newFp12(nil)
- var a, b, u *fe12
- for j := 0; j < fuz; j++ {
- a, _ = new(fe12).rand(rand.Reader)
- b, _ = new(fe12).rand(rand.Reader)
- u, _ = new(fe12).rand(rand.Reader)
- b[0][2].zero()
- b[1][0].zero()
- b[1][2].zero()
- fp12.mul(u, a, b)
- fp12.mulBy014Assign(a, &b[0][0], &b[0][1], &b[1][1])
- if !a.equal(u) {
- t.Fatal("bad mul by 01")
- }
- }
- }
- func TestFp12Exponentiation(t *testing.T) {
- field := newFp12(nil)
- for i := 0; i < fuz; i++ {
- a, _ := new(fe12).rand(rand.Reader)
- u := field.new()
- field.exp(u, a, big.NewInt(0))
- if !u.equal(field.one()) {
- t.Fatal("a^0 == 1")
- }
- field.exp(u, a, big.NewInt(1))
- if !u.equal(a) {
- t.Fatal("a^1 == a")
- }
- v := field.new()
- field.mul(u, a, a)
- field.mul(u, u, u)
- field.mul(u, u, u)
- field.exp(v, a, big.NewInt(8))
- if !u.equal(v) {
- t.Fatal("((a^2)^2)^2 == a^8")
- }
- }
- }
- func TestFp12Inversion(t *testing.T) {
- field := newFp12(nil)
- for i := 0; i < fuz; i++ {
- u := field.new()
- zero := field.zero()
- one := field.one()
- field.inverse(u, zero)
- if !u.equal(zero) {
- t.Fatal("(0^-1) == 0)")
- }
- field.inverse(u, one)
- if !u.equal(one) {
- t.Fatal("(1^-1) == 1)")
- }
- a, _ := new(fe12).rand(rand.Reader)
- field.inverse(u, a)
- field.mul(u, u, a)
- if !u.equal(one) {
- t.Fatal("(r*a) * r*(a^-1) == r)")
- }
- }
- }
- func BenchmarkMultiplication(t *testing.B) {
- a, _ := new(fe).rand(rand.Reader)
- b, _ := new(fe).rand(rand.Reader)
- c, _ := new(fe).rand(rand.Reader)
- t.ResetTimer()
- for i := 0; i < t.N; i++ {
- mul(c, a, b)
- }
- }
- func BenchmarkInverse(t *testing.B) {
- a, _ := new(fe).rand(rand.Reader)
- b, _ := new(fe).rand(rand.Reader)
- t.ResetTimer()
- for i := 0; i < t.N; i++ {
- inverse(a, b)
- }
- }
- func padBytes(in []byte, size int) []byte {
- out := make([]byte, size)
- if len(in) > size {
- panic("bad input for padding")
- }
- copy(out[size-len(in):], in)
- return out
- }
|