class BLS::ProjectivePoint
Abstract Point class that consist of projective coordinates.
Attributes
m_precomputes[RW]
x[R]
y[R]
z[R]
Public Class Methods
new(x, y, z)
click to toggle source
# File lib/bls/point.rb, line 15 def initialize(x, y, z) @x = x @y = y @z = z @m_precomputes = nil end
Public Instance Methods
==(other)
click to toggle source
Compare one point to another. @param [ProjectivePoint] other another point. @return [Boolean] whether same point or not.
# File lib/bls/point.rb, line 38 def ==(other) raise PointError, "ProjectivePoint#==: this is #{self.class}, but other is #{other.class}" unless self.class == other.class (x * other.z) == (other.x * z) && (y * other.z) == (other.y * z) end
add(other)
click to toggle source
hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#addition-add-1998-cmo-2
# File lib/bls/point.rb, line 63 def add(other) raise PointError, "ProjectivePoint#add: this is #{self.class}, but other is #{other.class}" unless self.class == other.class return other if zero? return self if other.zero? x1 = self.x y1 = self.y z1 = self.z x2 = other.x y2 = other.y z2 = other.z u1 = y2 * z1 u2 = y1 * z2 v1 = x2 * z1 v2 = x1 * z2 return double if v1 == v2 && u1 == u2 return zero if v1 == v2 u = u1 - u2 v = v1 - v2 vv = v * v vvv = vv * v v2vv = v2 * vv w = z1 * z2 a = u * u * w - vvv - v2vv * 2 x3 = v * a y3 = u * (v2vv - a) - vvv * u2 z3 = vvv * w new_point(x3, y3, z3) end
Also aliased as: +
calc_multiply_precomputes(w)
click to toggle source
# File lib/bls/point.rb, line 187 def calc_multiply_precomputes(w) raise PointError, 'This point already has precomputes.' if m_precomputes self.m_precomputes = [w, normalize_z(precomputes_window(w))] end
clear_multiply_precomputes()
click to toggle source
# File lib/bls/point.rb, line 193 def clear_multiply_precomputes self.m_precomputes = nil end
double()
click to toggle source
hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#doubling-dbl-1998-cmo-2
# File lib/bls/point.rb, line 49 def double w = x * x * 3 s = y * z ss = s * s sss = ss * s b = x * y * s h = w * w - ( b * 8) x3 = h * s * 2 y3 = w * (b * 4 - h) - (y * y * 8 * ss) # W * (4 * B - H) - 8 * y * y * S_squared z3 = sss * 8 new_point(x3, y3, z3) end
from_affine_tuple(xy)
click to toggle source
# File lib/bls/point.rb, line 126 def from_affine_tuple(xy) new_point(xy[0], xy[1], x.class.const_get(:ONE)) end
gen_invert_batch(nums)
click to toggle source
# File lib/bls/point.rb, line 130 def gen_invert_batch(nums) len = nums.length scratch = Array.new(len) acc = x.class::ONE len.times do |i| next if nums[i].zero? scratch[i] = acc acc *= nums[i] end acc = acc.invert len.times do |t| i = len - t - 1 next if nums[i].zero? tmp = acc * nums[i] nums[i] = acc * scratch[i] acc = tmp end nums end
max_bits()
click to toggle source
# File lib/bls/point.rb, line 179 def max_bits self.class.const_get(:MAX_BITS) end
multiply(scalar)
click to toggle source
Constant time multiplication. Uses wNAF.
# File lib/bls/point.rb, line 153 def multiply(scalar) n = scalar.is_a?(Fq) ? scalar.value : scalar raise PointError, 'Invalid scalar, expected positive integer' if n <= 0 raise PointError, "Scalar has more bits than maxBits, shouldn't happen" if n.bit_length > max_bits wNAF(n).first end
Also aliased as: *
multiply_unsafe(scalar)
click to toggle source
# File lib/bls/point.rb, line 103 def multiply_unsafe(scalar) n = scalar.is_a?(Fq) ? scalar.value : scalar raise PointError, 'Point#multiply: invalid scalar, expected positive integer' if n <= 0 p = zero d = self while n.positive? p += d unless (n & 1).zero? d = d.double n >>= 1 end p end
negate()
click to toggle source
# File lib/bls/point.rb, line 44 def negate new_point(x, y.negate, z) end
new_point(x, y, z)
click to toggle source
# File lib/bls/point.rb, line 31 def new_point(x, y, z) self.class.new(x, y, z) end
normalize_z(points)
click to toggle source
# File lib/bls/point.rb, line 183 def normalize_z(points) to_affine_batch(points).map{ |p| from_affine_tuple(p) } end
precomputes_window(w)
click to toggle source
# File lib/bls/point.rb, line 162 def precomputes_window(w) windows = (BigDecimal(max_bits) / w).ceil window_size = 2**(w - 1) points = [] p = self windows.times do base = p points << base (1...window_size).each do base += p points << base end p = base.double end points end
subtract(other)
click to toggle source
# File lib/bls/point.rb, line 96 def subtract(other) raise PointError, "ProjectivePoint#subtract: this is #{self.class}, but other is #{other.class}" unless self.class == other.class add(other.negate) end
Also aliased as: -
to_affine(inv_z = z.invert)
click to toggle source
# File lib/bls/point.rb, line 117 def to_affine(inv_z = z.invert) [x * inv_z, y * inv_z] end
to_affine_batch(points)
click to toggle source
# File lib/bls/point.rb, line 121 def to_affine_batch(points) to_inv = gen_invert_batch(points.map(&:z)) points.map.with_index { |p, i| p.to_affine(to_inv[i]) } end
zero()
click to toggle source
# File lib/bls/point.rb, line 26 def zero one = x.class.const_get(:ONE) new_point(one, one, x.class.const_get(:ZERO)) end
zero?()
click to toggle source
# File lib/bls/point.rb, line 22 def zero? z.zero? end
Private Instance Methods
wNAF(n)
click to toggle source
# File lib/bls/point.rb, line 199 def wNAF(n) w, precomputes = m_precomputes || [1, precomputes_window(1)] p = zero f = zero windows = (BigDecimal(max_bits) / w).ceil window_size = 2**(w - 1) mask = (2**w - 1) max_number = 2**w shift_by = w windows.times do |window| offset = window * window_size wbits = n & mask n >>= shift_by if wbits > window_size wbits -= max_number n += 1 end if wbits.zero? f += (window % 2 ? precomputes[offset].negate : precomputes[offset]) else cached = precomputes[offset + wbits.abs - 1] p += (wbits.negative? ? cached.negate : cached) end end [p, f] end