class Rb25519::FField
Attributes
p[RW]
Public Class Methods
eea(i,j)
click to toggle source
# File lib/rb-pure25519.rb, line 176 def self.eea(i,j) s,t,u,v = 1,0,0,1 while (j != 0) q, r = i / j, i % j unew, vnew = s , t s = u - (q * s) t = v - (q * t) i, j = j, r u, v = unew, vnew end d, m, n = i, u, v return [d, m, n] end
new(size)
click to toggle source
# File lib/rb-pure25519.rb, line 200 def initialize(size) raise RuntimeError.new("Field must be prime") unless size.ferm_is_prime? @p = size end
rosetta_mod_exp(b, exp, mod)
click to toggle source
Class methods
# File lib/rb-pure25519.rb, line 164 def self.rosetta_mod_exp(b, exp, mod) exp < 0 and raise ArgumentError, "negative exponent" prod = 1 base = b % mod until exp.zero? exp.odd? and prod = (prod * base) % mod exp >>= 1 base = (base * base) % mod end prod end
Public Instance Methods
[](v)
click to toggle source
# File lib/rb-pure25519.rb, line 206 def [](v) FFieldValue.new(self, v) end
add(a,b)
click to toggle source
# File lib/rb-pure25519.rb, line 210 def add(a,b) nv = a.to_i + b.to_i nv -= @p if nv >= @p nv end
div(a,b)
click to toggle source
rv = (a / b)
# File lib/rb-pure25519.rb, line 237 def div(a,b) a.to_i * inv(b.to_i) end
exp(b,e)
click to toggle source
rv = b^e
# File lib/rb-pure25519.rb, line 245 def exp(b,e) self.class.rosetta_mod_exp(b.to_i, e.to_i, @p) end
inv(v)
click to toggle source
# File lib/rb-pure25519.rb, line 227 def inv(v) #puts "Inversion" return self.class.eea(@p, v.to_i)[1] end
mul(a,b)
click to toggle source
# File lib/rb-pure25519.rb, line 222 def mul(a,b) # Naive implementation of multiply (a.to_i * b.to_i) % @p end
sqrt(n)
click to toggle source
# File lib/rb-pure25519.rb, line 249 def sqrt(n) n = n.to_i return nil if exp(n, (@p-1)/2) != 1 if (@p % 4) == 3 r = exp(n, (p+1) / 4) return [ r, -r % @p ] end ## ## Implement Tonelli-Shanks (from https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm ) ## # Factor out Q and S # # p1 = @p-1 q,s = nil,nil p1.bit_length.times.each do |_s| _q, _res = p1.ferm_ndiv(1 << _s) ## puts [_s, _q, _res].inspect if _res == 0 and _q.odd? q,s = _q, _s end end ## puts "q,s: #{[q,s].inspect}" # Find `z` such that Legendre ( z | p ) == -1 z = nil (1..@p).each{|_z| (z = _z; break) if self.exp(_z, (@p-1)/2) > 1 } ## puts "Found z: #{z}" c = exp(z, q) ## puts "Calculated c: #{c}" r = nil _r = exp(n, (q+1) / 2 ) t = exp(n, q) m = s @p.times do if (t == 1) r = _r ## puts "R is #{r}" break end # Modify t and R # # find i such that 0 < i < M, such that t**2**i == 1 (mod p) i = nil i = (1..(m-1)).find{|_i| exp(t, (1<<_i)) == 1 } ## puts "Found i: #{i}" b = exp(c, (1 << (m - i - 1))) _r = mul(_r, b) t = mul(t, exp(b, 2) ) c = exp(b, 2) m = i ## puts({:b => b, :r => _r, :t => t, :c => c}.inspect) end [r, @p - r] if r end
sub(a,b)
click to toggle source
# File lib/rb-pure25519.rb, line 216 def sub(a,b) nv = a.to_i - b.to_i nv += @p if nv < 0 nv end