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