Running with Ruby

Tag: HTC

Arytmetyka modulo + Ruboto + Ruby + Android

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 2×2 oraz mnożenie macierzy 2×2 razy 1×2 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 2×2 przez 1×2 (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

HTC Magic CyanogenMod 4.2 to 5.0.8 Daily Driver White update

I’ve decided to do major upgrade from CyanogenMod 4.2 to 5.08 Daily Driver on my HTC Magic phone.

Thanks to Edek Łomiarz – I’ve managed to survive and create this tutorial :)

If you want to update your Cyan you will net old radio na SPL, here you have mine:

HTC Magic od Orange (32A):
wersja opr 1.6
Baseband 62.52S.20.18U_3.22.20.17
Kernel 2.6.29.6-cyanogenmod
Mod version: CyanogenMod-4.2.15.1
Compliation: DRC92
Nandroid: 2.2v

So if you have software like presented above and you have already Cyanogen on your phone – you’re free to go.

How to update Cyan?
Download latest Cyanogen mode from XDA: http://forum.xda-developers.com/showthread.php?t=673394. There are two versions – black and white so choose the one you like:

cyanogen_mod2cyanogen_mod

[Update] Stable Cyanogen mode has been released – installation looks the same.

Before updating:

  • Charge your battery
  • Download mod from XDA
  • Copy mod into root dir on your phone SD card
  • Restart phone with pressed home button to load Nandroid

After Nandroid boots, you will see:

nandroid

  • Select Nandroid v2.2 backup
  • Confirm by pressing home button (and wait until backup is over)
  • Select Wipe data/factory reset (resetting phone and OS)
  • Select Apply sdcard:choose.zip and select rom (CM5.0.7t7-32a-w)
  • Wait, wait, wait
  • Reboot system now
  • Wait approximately 10-15 minutes while Cyan is loading for the first time

Thats all. Cyanoged mod is really fast and fancy. He has got a really nice gallery with 3D effects like those in Picasa.

Any problems? You still have your backup so you can restore it.

Remember – you are performing update at your own risk!

Copyright © 2018 Running with Ruby

Theme by Anders NorenUp ↑