Tag: HTC

W związku z zajęciami z kryptografii, potrzebowałem mieć pod ręką trochę narzędzi umożliwiających obliczenie fi (funkcji Eulera), odwrotności modulo, rozkładu liczby na czynniki pierwsze, wyznaczanie odwrotności modulo macierzy 2x2 oraz mnożenie macierzy 2x2 razy 1x2 oraz obliczenia modulo z duuuuuużych liczb przedstawionych jako potęg. Dlatego też powstał kod działający na Androidzie. Jedyne wymaganie to Ruboto - do znalezienia na Markecie. Jest to JRuby dla Androida, umożliwiający odpalanie prostych skryptów na telefonie. Idealne kiedy trzeba napisać coś na szybko. Zaczniemy od potęgowania. Spróbuj dokonać takiego obliczenia modulo: 12345^12345 mod126 w kalkulatorze na Windows. Chyba się nie udało ;) A ten oto poniższy kod, świetnie sobie z tym radzi:

liczba = 12345
power = 12345
n = 126
#--------------------------------------
def mod(liczba, power, n)
  val = 1

  power.times do |i|
    val *= liczba
    val %= n
  end
  val
end

puts "#{liczba}^#{power}(mod#{n})= #{mod(liczba, power, n)}"

A wynikiem jest: 99 Następnie mamy funkcję Eulera (fi):

liczba = 30
#--------------------------------------
def phi(m)
  r = (2..m)
  primes = r.inject(r){|p, i| p.select{|n| n==i || n%i!=0}}
  primes.inject(m){|e, p| e%p==0 ? e/p*(p-1) : e}
end

puts "fi dla #{liczba} wynosi: #{phi(liczba)}"

Która też działa niczego sobie :) - oczywiście to obliczenie dla zbyt dużych liczb na telefonie komórkowym nie będzie przebiegać zbyt szybko, więc używajcie z rozwagą ;) Kolejnym kawałkiem kodu jest kod obliczający odwrotność zadanej liczby w sensie modulo:

liczba = 315
n = 676
#--------------------------------------

class Integer
  def to_ba(size=128)
    a=[]
    (size-1).downto(0) do |i|
      a<<< 2**index
  }

  val = 1
  powers.each { |pow|
    pow.times do |i|
      val *= liczba
      val %= n
    end
  }
  val
end

def check(liczba, odw, n)
  (liczba*odw)%n == 1
end

odw = odwrotnosc(liczba, n)

if odw == 0
  puts "Odwrotnosc nie istnieje NWD(#{liczba}, #{n}) != 1"
else

  if check(liczba, odw, n)
    puts "#{liczba}^-1 (mod#{n})= #{odw}"
  else
    puts "NWD(#{liczba}, #{n}) != 1"
  end
end

Rozkład liczby na czynniki pierwsze:

liczba = 2

# -----------------------------------------------------------------------------
def factorize(orig)
    factors = {}
    factors.default = 0
    n = orig
    i = 2
    sqi = 4
    while sqi <= n do
        while n.modulo(i) == 0 do
            n /= i
            factors[i] += 1
        end
        sqi += 2 * i + 1
        i += 1
    end

    if (n != 1) && (n != orig)
        factors[n] += 1
    end
    factors
end

def printfactorhash(orig, factorcount)
    print format("%-10d ", orig)
    if factorcount.length == 0
        print "Liczba pierwsza"
    else
        factorcount.sort.each { |factor,exponent|
            print factor
            if exponent > 1
                print "^", exponent
            end
            print " "
        }
    end
    puts
end

n = liczba.to_i
mfactors = factorize(n)
printfactorhash(n, mfactors)

Odwrotność macierzy (w sensie modulo):

MATRIX = [[0,11],
          [17,0]]

#[a, b]
#[c, d]

n = 29

#--------------------------------------

class Integer
  def to_ba(size=128)
    a=[]
    (size-1).downto(0) do |i|
      a<<self[i]
    end
    a
  end
end

def phi(m)
  r = (2..m)
  primes = r.inject(r){|p, i| p.select{|n| n==i || n%i!=0}}
  primes.inject(m){|e, p| e%p==0 ? e/p*(p-1) : e}
end

def odwrotnosc(liczba, n)
  fi = phi(n)

  powers = []
  (fi-1).to_ba.reverse.each_with_index { |b, index|
    next if b == 0
    powers << 2**index
  }

  val = 1
  powers.each { |pow|
    pow.times do |i|
      val *= liczba
      val %= n
    end
  }
  val
end

def nwd(a,b)
  if a > b then a -= b else b -= a end while a != b; return a
end

def det(m)
  m[0][0].to_i*m[1][1].to_i-m[0][1].to_i*m[1][0].to_i
end

def inverse(m, n)

  det = det(m)
  det = det%n

  if nwd(det, n) != 1
    puts "NWD(m, n) != 1"
    exit
  end

  puts "det= #{det}"
  odw_a = odwrotnosc(det, n)
  puts "det^-1mod(#{n})= #{odw_a}"

  w = []
  w << [odw_a*m[1][1]%n, -odw_a*m[0][1]%n ]
  w << [-odw_a*m[1][0]%n, odw_a*m[0][0]%n ]
  w
end

def print_res(w)
  puts "[#{w[0][0]}, #{w[0][1]}]"
  puts "[#{w[1][0]}, #{w[1][1]}]"
end

print_res(inverse(MATRIX, n))

Mnożenie macierzy 2x2 przez 1x2 (w sensie modulo n)

MATRIX1 = [
          [21,19],
          [22,18]]

MATRIX2 = [15, 24]

n = 29

def multiply(m1, m2, n)
  w = [(m1[0][0]*m2[0]+m1[0][1]*m2[1])%n, (m1[1][0]*m2[0]+m1[1][1]*m2[1])%n ]
end

def print_res(res)
  puts "[ #{res[0]}, #{res[1]}]"
end

print_res(multiply(MATRIX1, MATRIX2, n))

Podsumowując: powyżej zamieściłem kod który wykonuje następujące czynności:

• Obliczanie modulo dużych liczb przedstawionych w postaci potęg
• Funkcja Eulera - algorytm obliczenia wartości funkcji fi
• Obliczanie odwrotności liczby w sensie modulo
• Rozkład liczby na czynniki pierwsze

Mam nadzieję że się przyda :) A tutaj: źródełko