hw6.py

# Name: Kyle Holzinger
# BUID: U92663004
# Date: 12.15.14

from math import floor
from fractions import gcd
from random import randint

'''
Problem 1

a.

8 x = 16 mod 32
8 is a factor of 8, 16, and 32
x = 2 mod 4

b.

x = 8 mod 12
x = 4 mod 16

gcd(12, 16) = 4
does 8 = 4 mod 4? yes
r = 8 mod 4 = 0 mod 4

compute
z = (8-0)/4 mod 3
z = (4-0)/4 mod 4

z = 2 mod 3
z = 1 mod 4
z = 2*4 *4^-1 + 1*3*3^-1mod 12
z = 2*4*1 + 1*3*3
z = 8 + 9 = 17 mod 12

x = g*z + r mod (12*16)/4
x = 4*17 + 0 mod 48
x = 20 mod 48

c.

x = 10 (mod 14)
x = 17 (mod 21)

gcd(14,21) = 7
Does 10 = 17 mod 7? Yes.

r = 10 mod 7 = 3 mod 7

compute
z = (10 - 3)/7 mod 2
z = (17 - 3)/7 mod 3

z = 1 mod 2
z = 2 mod 3
z = 1 * 3 * 3^-1 mod 2 + 2 * 2 * 2^-1 mod 3 mod (2*3)
z = 3 + 8 = 11 mod 6 = 5 mod 6

x = g*z + r mod (14*21/7)
x = 7*5 + 3 mod 48
x = 38 mod 48

d.

x^2 = 4 (mod 35)
3 x = 15 (mod 21)

Solve x^2 = 4 (mod 35)

TODO:
the answer is 12 or 33 mod 35.

e.

2x = 12 mod 26

Is 2 a factor of 2, 12, and 26? Yes
x = 6 mod 13

x = 6 mod 26
x = 19 mod 26 

f.

The subgroups of (Z/8Z, +) are....
{0}
{0,4}
{0,2,4,6}
{0,1,2,3,4,5,6,7}
'''
'''
Problem 2
a.
x = 11 mod 16
x = 3 mod 12

x - 11 = 0 mod 16
x - 11 = -8 mod 12

(x - 11)/4 = 0 mod 4
(x - 11)/4 = 1 mod 3

(x - 11)/4 = 0 (3 * 3^-1 mod 4) + 1(4 * 4^-1 mod 3) mod 12

(x - 11)/4 = 1(4 * 1) mod 12

x - 11 = 16 mod 48

x = 27 mod 48

It has been 27 hours since the alarm rang at midnight. To get the current time,
we can do 27 mod 24, which is 3 and therefore the current time is 3 AM.

b.

x = 2 mod 12
x = 8 mod 15

gcd(12, 15) = 3
Is 2 = 8 mod 3? Yes

x - 2 = 0 mod 12
x - 2 = 6 mod 15

(x - 2)/3 = 0 mod 4
(x - 2)/3 = 2 mod 5

(x - 2)/3 = 0 * (5 * 5^-1 mod 4) + 2 * (4 * 4^-1 mod 5) (mod 4 * 5)
          = 0 + 32 (mod 20)
(x - 2) = 96 (mod 60)
x = 98 mod 60
x = 38 mod 60

Assuming that Bob has at most 60 problems to solve, how many problems does
Bob have?

Bob has at most 38 problems.


If Bob can only reserve batches of machines that all have the same
capacity, and the fastest machine can only solve 19 problems before
the deadline, is there anything Bob can do to avoid having at least
one machine not used to its full capacity?

Yes, if he uses 2 machines, both of them can solve 19 problems, because
19 + 19 = 38.

c.
Alice stored a 16-bit integer x in an 8-bit memory location
(effectively storing x mod 2^8), and then she also saved x in a
separate 4-bit memory location (effectively storing x mod 2^4).

Because when you do modulo in binary (given the modulus is a power
of 2) you are truncating the bit string, doing x mod 2^8 leaves the
first 8 bits of the 16 bit string. If you do x mod 2^4, you are left
with the first 4 bits of the string. Therefore, this x mod 2^4 does
not provide any further information, and you will have to test the
other 2^8 possible answers. This is because for the 8 bits that were
chopped off during the truncation, there are 2^8 possible values.

'''

def inv(a, m):
  if gcd(a, m) == 1:
    return egcd(a, m)[0] % m
  return None

def egcd(a, b):
  (x, s, y, t) = (0, 1, 1, 0)
  while b != 0:
    k = a // b
    (a, b) = (b, a % b)
    (x, s, y, t) = (s - k*x, x, t - k*y, y)
  return (s, t)

def to_simple_equation(e1):
  c = 1
  a = solveOne(e1[0], e1[1], e1[2])
  m = e1[2] / gcd(e1[0],e1[2])
  return (c, a, m)

def solveOne(c, a, m):
  denom = gcd(c, m)
  if not (a % denom == 0):
    return None

  return ((a/denom) * inv(c/denom, m/denom)) % (m/denom)

def solveTwo(e1, e2):

  if (solveOne(e1[0], e1[1], e1[2]) == None) or (solveOne(e2[0], e2[1], e2[2]) == None):
    return None

  if not (e1[0] == 1):
    e1 = to_simple_equation(e1)
  if not (e2[0] == 1):
    e2 = to_simple_equation(e2)

  denom = gcd(e1[2], e2[2])

  if not ( (e1[1] % denom) == e2[1] % denom):
    return None

  r = e1[1]
  a1 = (e1[1] - r) / denom
  a2 = (e2[1] - r) / denom
  p1 = e1[2] / denom
  p2 = e2[2] / denom

  x = (a1 * (p1 * inv(p2, p1)) + a2 * (p1 * inv(p1, p2)) ) % (p1 * p2)
  return x * denom + r

def solveAll(es):
   C = es
   while (len(C) > 1):
      Ci = C.pop()
      Cj = C.pop()

      if (solveTwo(Ci, Cj) == None):
         return None
      m = ((Ci[2] / gcd(Ci[0], Ci[2])) * (Cj[2] / gcd(Cj[0], Cj[2]))) / gcd(Ci[2], Cj[2])
      C.append((1, solveTwo(Ci, Cj), m))
   return C.pop()[1]

def plus256unreliable(x, y):
   r = randint(0,7) - 4
   return (min(255, max(0, ((x + y)%256) + r)))

def plus16(x, y):
   return plus256unreliable(plus256unreliable(x*16, y*16), 8) // 16

def plus256(x, y):
   m = [3,5,7,16]
   fin = [(1,plus16(x % i, y % i), i) for i in m]
   return solveAll(fin) % 256