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]
#1

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