binaryquadraticform

package
v1.0.3 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 23, 2023 License: Apache-2.0 Imports: 7 Imported by: 1

README

Binary Quadratic Forms for Imaginary Quadratic Fields

This library implemented class groups of imaginary quadratic fields by the operations of binary quadratic forms[1].

Guildline

The main public functions in this Library are: Exp, Composition.

Example
package binaryquadraticform

import (
    "math/big"
    "testing"
)

// Composition
func TestComposition(t *testing.T) {
    form1, _ := NewBQuadraticForm(big.NewInt(1), big.NewInt(1), big.NewInt(6))
    form2, _ := NewBQuadraticForm(big.NewInt(1), big.NewInt(1), big.NewInt(6))

    got, _ := form1.Composition(form2)

    // output: a=1, b=1, c=6
}

// Exp
func TestExp(t *testing.T) {
    form1, _ := NewBQuadraticForm(big.NewInt(31), big.NewInt(24), big.NewInt(15951))

    got, _ := form1.Exp(big.NewInt(200))
    // output: a=517, b=-276, c=993
}

More examples can be found in binaryquadraticform_test.

Experiment

Our benchmarks were in local computation and ran on an Intel qualcore-i5 CPU 2.3 GHz and 16GB of RAM.

Note that we improve the efficiency of this library. The following benchmarks are out of date.

Benchmark

We use a particular binary quadratic form Q := ax^2+bxy+cy^2 form to benchmark, where
a=2
b=1
c=38270086293509404933867071895401019019366095470206334878396235822253000046664893060272814 4885376377736899019811788016480970822740602470345900972511577261040787881052139208590201529 5545562523958711866779371531088132889638114041946661849770572154226710985917599916457066302 6821483359097065850719591509598145462062654351033736734969435747887449357951781277325201275 3107597915953828936546637318213715877938209264724667965717193550712672887897192948921266890 8199079072163111583975633638661816714659180109107951783005735418950482497851235754121794548 776139119565032459702128377126838952995785769100706778680652441494512278

Discriminant = 2048 bit

+---------------+--------------------+-------------------+--------------------+--------------------+
|  Operation    |                                                                                  |
+---------------+--------------------+-------------------+--------------------+--------------------+
| Exponential   |  100 bit           | 200 bit           | 300 bit            | 400 bit            |
| Exp           |  5.6179 ms/op      | 11.2084 ms/op     | 23.4616 ms/op      | 21.5768 ms/op      |
+---------------+--------------------+-------------------+--------------------+--------------------+

We benchmark square, cube, composition for Q^100.

+---------------+--------------------+
|  Operation    |                    |                                                              
+---------------+--------------------+
| Reduction     |  89 ns/op          |
| square        |  6734 ns/op        | 
| cube          |  10787 ns/op       | 
| composition   |  7737 ns/op        | 
+---------------+--------------------+

Reference

  1. Cohen's book:A Course in Computational Algebraic Number Theory
  2. Maxwell Sayles

Other Library

  1. Class Groups
  2. Cryptographic accumulators in Rust

Documentation

Overview

Copyright © 2020 AMIS Technologies

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at 

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Index

Constants

This section is empty.

Variables

View Source 
var (

	// ErrPositiveDiscriminant is returned if the discriminant is negative.
	ErrPositiveDiscriminant = errors.New("not a negative discriminant")
	// ErrDifferentDiscriminant is returned if the discriminants are different.
	ErrDifferentDiscriminant = errors.New("different discriminant")
	// ErrEmptySlice is returned if the slice is empty.
	ErrEmptySlice = errors.New("slice is empty")
	// ErrZero is returned if the integer is zero.
	ErrZero = errors.New("the integer is zero")
)
View Source 
var (
	ErrInvalidMessage = errors.New("invalid message")
)
View Source 
var File_github_com_getamis_alice_crypto_binaryquadraticform_message_proto protoreflect.FileDescriptor

Functions

func NewCacheExp 

func NewCacheExp(bq *BQuadraticForm) *cacheExp

NewCacheExp initiates a cache BQ exp. In this struct, we calculate exp by cached values

Types

type BQForm 

type BQForm struct {

	// a, b, c may be negative, so we use string type.
	A string `protobuf:"bytes,1,opt,name=a,proto3" json:"a,omitempty"`
	B string `protobuf:"bytes,2,opt,name=b,proto3" json:"b,omitempty"`
	C string `protobuf:"bytes,3,opt,name=c,proto3" json:"c,omitempty"`
	// contains filtered or unexported fields
}

func (*BQForm) Descriptor deprecated 

func (*BQForm) Descriptor() ([]byte, []int)

Deprecated: Use BQForm.ProtoReflect.Descriptor instead.

func (*BQForm) GetA 

func (x *BQForm) GetA() string

func (*BQForm) GetB 

func (x *BQForm) GetB() string

func (*BQForm) GetC 

func (x *BQForm) GetC() string

func (*BQForm) ProtoMessage 

func (*BQForm) ProtoMessage()

func (*BQForm) ProtoReflect added in v1.0.2 

func (x *BQForm) ProtoReflect() protoreflect.Message

func (*BQForm) Reset 

func (x *BQForm) Reset()

func (*BQForm) String 

func (x *BQForm) String() string

func (*BQForm) ToBQuadraticForm 

func (bf *BQForm) ToBQuadraticForm() (*BQuadraticForm, error)

func (*BQForm) ToCacheExp 

func (bf *BQForm) ToCacheExp() (*cacheExp, error)

type BQuadraticForm 

type BQuadraticForm struct {
	// contains filtered or unexported fields
}

In this library, we only consider positive definite quadratic forms 

This Library only supports some operations of "primitives positive definite binary quadratic forms" (i.e.
* corresponding to ideal operations over imaginary quadratic fields).
* A Quadratic form is given by: (a,b,c) := ax^2+bxy+cy^2 with discriminant = b^2 - 4ac < 0

func NewBQuadraticForm 

func NewBQuadraticForm(a *big.Int, b *big.Int, c *big.Int) (*BQuadraticForm, error)

Give a, b, c to construct quadratic forms.

func NewBQuadraticFormByDiscriminant 

func NewBQuadraticFormByDiscriminant(a *big.Int, b *big.Int, discriminant *big.Int) (*BQuadraticForm, error)

Give a, b, discriminant to construct quadratic forms.

func (*BQuadraticForm) Composition 

func (bqForm *BQuadraticForm) Composition(inputForm *BQuadraticForm) (*BQuadraticForm, error)

The composition operation of binary quadratic forms * NUCOMP algorithm. Adapted from "Solving the Pell Equation" * by Michael J. Jacobson, Jr. and Hugh C. Williams. * http://www.springer.com/mathematics/numbers/book/978-0-387-84922-5 * The code original author: Maxwell Sayles. * Code: https://github.com/maxwellsayles/libqform/blob/master/mpz_qform.c

func (*BQuadraticForm) Copy 

func (bqForm *BQuadraticForm) Copy() *BQuadraticForm

copy the binary quadratic form

func (*BQuadraticForm) Equal 

func (bqForm *BQuadraticForm) Equal(bqForm1 *BQuadraticForm) bool

func (*BQuadraticForm) Exp 

func (bqForm *BQuadraticForm) Exp(power *big.Int) (*BQuadraticForm, error)

The output is bqForm ^ power. Ref: Algorithm 3.2, page 30, * Improved Arithmetic in the Ideal Class Group of Imaginary * Quadratic Number Fields, Maxwell Sayles.

func (*BQuadraticForm) GetA 

func (bqForm *BQuadraticForm) GetA() *big.Int

Get the coefficient of a binary quadratic form: ax^2 + bxy + cy^2 Get a

func (*BQuadraticForm) GetB 

func (bqForm *BQuadraticForm) GetB() *big.Int

Get b

func (*BQuadraticForm) GetC 

func (bqForm *BQuadraticForm) GetC() *big.Int

Get c

func (*BQuadraticForm) GetDiscriminant 

func (bqForm *BQuadraticForm) GetDiscriminant() *big.Int

Get discriminant

func (*BQuadraticForm) Identity 

func (bqForm *BQuadraticForm) Identity() *BQuadraticForm

Identity element := bqForm * bqForm.Inverse()

func (*BQuadraticForm) Inverse 

func (bqForm *BQuadraticForm) Inverse() *BQuadraticForm

The inverse quadratic Form of [a,b,c] is [a,-b,c]

func (*BQuadraticForm) IsReducedForm 

func (bqForm *BQuadraticForm) IsReducedForm() bool

Note that: D < 0. (a,b,c) is reduced if |b| <= a <= c and if b >= 0 whenever a = |b| or a = c

func (*BQuadraticForm) ToMessage 

func (b *BQuadraticForm) ToMessage() *BQForm

type Exper 

type Exper interface {
	Exp(power *big.Int) (*BQuadraticForm, error)
	ToMessage() *BQForm
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.