Class: BLS::ProjectivePoint

Inherits:
Object
  • Object
show all
Defined in:
lib/bls/point.rb

Overview

Abstract Point class that consist of projective coordinates.

Direct Known Subclasses

PointG1, PointG2

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(x, y, z) ⇒ ProjectivePoint

Returns a new instance of ProjectivePoint.



24
25
26
27
28
29
 
# File 'lib/bls/point.rb', line 24

def initialize(x, y, z)
  @x = x
  @y = y
  @z = z
  @m_precomputes = nil
end

Instance Attribute Details

#m_precomputes ⇒ Object

Returns the value of attribute m_precomputes.



22
23
24
 
# File 'lib/bls/point.rb', line 22

def m_precomputes
  @m_precomputes
end

#x ⇒ Object (readonly)

Returns the value of attribute x.



21
22
23
 
# File 'lib/bls/point.rb', line 21

def x
  @x
end

#y ⇒ Object (readonly)

Returns the value of attribute y.



21
22
23
 
# File 'lib/bls/point.rb', line 21

def y
  @y
end

#z ⇒ Object (readonly)

Returns the value of attribute z.



21
22
23
 
# File 'lib/bls/point.rb', line 21

def z
  @z
end

Instance Method Details

#==(other) ⇒ Boolean

Compare one point to another.

Parameters:

Returns:

  • (Boolean) —

    whether same point or not.

Raises:



47
48
49
50
51
 
# File 'lib/bls/point.rb', line 47

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) ⇒ Object Also known as: +

hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#addition-add-1998-cmo-2

Raises:



72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/bls/point.rb', line 72

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

#calc_multiply_precomputes(w) ⇒ Object

Raises:



196
197
198
199
200
 
# File 'lib/bls/point.rb', line 196

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 ⇒ Object 



202
203
204
 
# File 'lib/bls/point.rb', line 202

def clear_multiply_precomputes
  self.m_precomputes = nil
end

#double ⇒ Object

hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#doubling-dbl-1998-cmo-2



58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/bls/point.rb', line 58

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) ⇒ Object 



135
136
137
 
# File 'lib/bls/point.rb', line 135

def from_affine_tuple(xy)
  new_point(xy[0], xy[1], x.class.const_get(:ONE))
end

#gen_invert_batch(nums) ⇒ Object 



139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/bls/point.rb', line 139

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 ⇒ Object 



188
189
190
 
# File 'lib/bls/point.rb', line 188

def max_bits
  self.class.const_get(:MAX_BITS)
end

#multiply(scalar) ⇒ Object Also known as: *

Constant time multiplication. Uses wNAF.

Raises:



162
163
164
165
166
167
168
 
# File 'lib/bls/point.rb', line 162

def multiply(scalar)
  n = scalar.is_a?(Field) ? 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

#multiply_unsafe(scalar) ⇒ Object

Raises:



112
113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/bls/point.rb', line 112

def multiply_unsafe(scalar)
  n = scalar.is_a?(Field) ? 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 ⇒ Object 



53
54
55
 
# File 'lib/bls/point.rb', line 53

def negate
  new_point(x, y.negate, z)
end

#new_point(x, y, z) ⇒ Object 



40
41
42
 
# File 'lib/bls/point.rb', line 40

def new_point(x, y, z)
  self.class.new(x, y, z)
end

#normalize_z(points) ⇒ Object 



192
193
194
 
# File 'lib/bls/point.rb', line 192

def normalize_z(points)
  to_affine_batch(points).map{ |p| from_affine_tuple(p) }
end

#precomputes_window(w) ⇒ Object 



171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
 
# File 'lib/bls/point.rb', line 171

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) ⇒ Object Also known as: -

Raises:



105
106
107
108
109
 
# File 'lib/bls/point.rb', line 105

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

#to_affine(inv_z = z.invert) ⇒ Object 



126
127
128
 
# File 'lib/bls/point.rb', line 126

def to_affine(inv_z = z.invert)
  [x * inv_z, y * inv_z]
end

#to_affine_batch(points) ⇒ Object 



130
131
132
133
 
# File 'lib/bls/point.rb', line 130

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 ⇒ Object 



35
36
37
38
 
# File 'lib/bls/point.rb', line 35

def zero
  one = x.class.const_get(:ONE)
  new_point(one, one, x.class.const_get(:ZERO))
end

#zero? ⇒ Boolean

Returns:

  • (Boolean) 


31
32
33
 
# File 'lib/bls/point.rb', line 31

def zero?
  z.zero?
end