2’s complement (draft)

Probably the most illuminating way of calculating the number of possible bit patterns of a bit string of length n is combinatorially by the counting principle: 2 × 2 × 2 × … × 2 (n occurrences of 2) = 2n. And in base 2 positional notation 2n would be written 100…00 (a one followed by n zeros).

Let x ∈ ℕ, 2n > x ≥ 0. Define the 2’s complement of x as 2n – x if x ≠ 0. When x = 0 its 2’s complement is 0. So x + (2n – x) = 2n and 2n – (2n – x) = x.

0 < x < 2n-1 ⇒ 0 > -x > -2n-1 ⇒ 2n > 2n – x > 2n-1.
2n > x > 2n-1 ⇒ -2n < -x < -2n-1 ⇒ 0 < 2n – x < 2n-1.

Note that 2n-1, like zero, is its own complement.

If we want half of the bit patterns (2n รท 2 = 2n-1) to represent negative integers then it’s natural to let the first n-1 bits represent zero and the positive integers from 1 to 2n-1 – 1.

If we have the representation of a negative integer then it’s easy to compute the corresponding negative integer. Let 2n-1 < 2n – x < 2n. Remove sign bit: 2n – x – 2n-1 = 2n-1 – x. Then -2n-1 + (2n-1 – x) = -x.

Addition of two negative integers

Let x,y ∈ ℕ, x ≠ 0, y ≠ 0. To show that -x + -y = -(x + y), assume x < 2n-1, y < 2n-1, x + y < 2n-1. Then (2n – x) + (2n – y) = 2n + (2n – (x + y)). Discarding the 2n bit leaves 2n – (x + y).

Addition of a positive integer and a negative integer

0 < y < x < 2n-1 ⇒ 0 < x – y < 2n-1.
x – y = x + -y ≡ x + 2n – y ≡ x – y (discarding the 2n bit).

0 < x < y < 2n-1 ⇒ 0 < y – x < 2n-1 – x < 2n-1.
x – y ≡ x + 2n – y = 2n – (y – x).
x – y < 0 ⇒ x – y ≡ 2n – |x – y| = 2n – -(x – y) = 2n – (y – x).

Sign Extension

2n > 2n – x ≥ 2n-1.
m additional bits.
Sign extend: 2n – x + Σ(i = 0 to m-1, 2n+i).
Prove: 2n+m – x = 2n – x + Σ(i = 0 to m-1, 2n+i).
2n+m – x – (2n – x + Σ(i = 0 to m-1, 2n+i)) = 2n+m – Σ(i = 0 to m-1, 2n+i) – 2n = 2n+m – 2n+m = 0.

Recover RSA primes p, q for |p – q| sufficiently small

Let s = sqrt(pq). Assume p ≤ q.

Starting from s, find the smallest prime k ≥ s.

Since q – p is small, q – s is small also. So pk is close to pq, i.e. pq – pk is small.

Starting from pq, since k is prime, exactly one n{a, a + 1, a + 2, …, a + k – 1 = pq} is not coprime with k. Using the method found here, n = a + (-a mod k) .

Let d = gcd(n, pq). If d > 1 then d = p. Otherwise choose the next k consecutive numbers less than a and repeat.

Runnable code in the Frink language:

p = 96436875510168134260978951531720215975911176926194651907111357743104310827706384687021784900521146900897417521181
q = 96436875510168134260978951531720215975911176926194651907111357743104310827706384687021784900521146900897417697981

if isPrime[p]
  println["p is prime"]
if isPrime[q]
  println["q is prime"]

println["prime difference:"]
println[q - p]

mysqrt[n] :=
{
  b = bitLength[n]
  m = 0
  i = ceil[b/2] - 1
  while i >= 0
  {
     if (m+2^i)^2 <= n
       m = m + 2^i
     i = i - 1
  }
  return m
}

pq = p * q
s = mysqrt[pq]
if s^2 <= pq && (s+1)^2 > pq
  println["sqrt function works"]
else
  println["wtf"]
k = nextPrime[s - 1]
println["prime between q and s:"]
println[k]
println["prime, sqrt difference:"]
println[k - s]
i = pq - k + 1
do
{
  n = i + (-i % k)
  d = gcd[n,pq]
  if d > 1
  {
    println["good"]
    break
  }
  i = i - k
} while i >= s

Exercises 0.3 #4

I) Let E be a correspondence from U to X. If (s0, x0) ∈ (ED)C then there is a t0 ∈ T such that (t0, x0) ∈ ED and (s0, t0) ∈ C. And there is a u0 ∈ U such that (u0, x0) ∈ E and (t0, u0) ∈ D. So (s0, u0) ∈ DC and (s0, x0) ∈ E(DC). Thus (ED)C ⊂ E(DC). If (s1, x1) ∈ E(DC) then there is a u1 ∈ U such that (u1, x1) ∈ E and (s1, u1) ∈ DC. And there is a t1 ∈ T such that (t1, u1) ∈ D and (s1, t1) ∈ C. So (t1, x1) ∈ ED and (s1, x1) ∈ (ED)C. Thus E(DC) ⊂ (ED)C. Therefore (ED)C = E(DC).

II) To do

Exercises 0.3 #2

~ ⊂ ℕ(2) × ℕ(2). If (a1, a2) ∈ ℕ(2) then a1 + a2 = a2 + a1. So ((a1, a2), (a1, a2)) ∈ ~. If ((a1, a2), (b1, b2)) ∈ ℕ(2) × ℕ(2) then a1 + b2 = a2 + b1. By commutativity b1 + a2 = b2 + a1, so ((b1, b2), (a1, a2)) ∈ ℕ(2) × ℕ(2). If ((a1, a2), (b1, b2)), ((b1, b2), (c1, c2)) ∈ ℕ(2) × ℕ(2) then a1 + b2 = a2 + b1 and b1 + c2 = b2 + c1. Subtracting gives a1 – c1 = a2 – c2, so a1 + c2 = a2 + c1. Thus ((a1, a2), (c1, c2)) ∈ ℕ(2) × ℕ(2). Hence ~ is an equivalence relation.

Exercises 0.3 #1

i) If m, n ∈ ℕ then m × n ∈ ℕ and m + n ∈ ℕ. So [X = {2k | k ∈ ℕ} ∪ {2k + 1 | k ∈ ℕ}] ⊂ ℕ. Let n ∈ ℕ. Since ℕ is not bounded above, there is a largest k ∈ ℕ such that 2k ≤ n. So 2k ≤ n < 2(k + 1) = 2k + 2. Because there is no natural number between a natural number and its successor, n = 2k or n = 2k + 1. So ℕ ⊂ X. Thus X = ℕ. Let m ∈ {2k | k ∈ ℕ} ∩ {2k + 1 | k ∈ ℕ}. Then m = 2k1 = 2k2 + 1 for k1, k2 ∈ ℕ. If k1 = k2 then 2k2 + 1 > 2k1. If k1 < k2 then 2k2 + 1 > 2k1. If k1 > k2 then k1 ≥ k2 + 1 > k2 ⇒ 2k1 > 2k2 + 1. Contradiction. Thus {2k | k ∈ ℕ} and {2k + 1 | k ∈ ℕ} are disjoint.

ii) Skipped (similar to (i)).

Exercises 0.2 #5

I) S = {s1, s2, s3}, T = {t1, t2}, A = {s1}, α = {(s1, t1), (s2, t1), (s3, t2)}, α(~A) = {t1, t2}, ~α(A) = {t2}. Thus α(~A) ⊄ ~α(A).

II) Suppose α is injective and α(~A) ⊄ ~α(A). Then there is a t ∈ T such that t ∈ α(~A) and t ∉ ~α(A) ⇒ there is an s1 ∈ ~A such that α(s1) = t and t ∈ α(A) ⇒ there is an s2 ∈ A such that α(s2) = t ⇒ α(s1) = α(s2) and s1 ≠ s2. Contradiction. Thus α is injective ⇒ α(~A) ⊂ ~α(A).

III) α is surjective can’t imply α(~A) ⊄ ~α(A), otherwise a bijective map would contradict part (II). α is surjective can’t imply α(~A) ⊂ ~α(A) by the example in part (I).

Exercises 0.2 #4

I) t ∈ α(A ∪ B) ⇒ there is an s ∈ A ∪ B such that α(s) = t ⇒ there is an s ∈ A or s ∈ B such that α(s) = t ⇒ t ∈ α(A) or t ∈ α(B). Thus α(A ∪ B) ⊂ α(A) ∪ α(B). t ∈ α(A) ∪ α(B) ⇒ there is an s ∈ A or s ∈ B such that α(s) = t ⇒ there is an s ∈ A ∪ B such that α(s) = t ⇒ t ∈ α(A ∪ B). Thus α(A) ∪ α(B) ⊂ α(A ∪ B).

II) t ∈ α(A ∩ B) ⇒ there is an s ∈ A ∩ B such that α(s) = t ⇒ there is an s ∈ A and s ∈ B such that α(s) = t ⇒ t ∈ α(A) and t ∈ α(B). Thus α(A ∩ B) ⊂ α(A) ∩ α(B).

III) α = { (s1, t1), (s2, t0), (s3, t0) }. A ⊂ S = { s1, s2 }. B ⊂ S = { s1, s3 }. α(A ∩ B) = { t1 }. α(A) ∩ α(B) = { t1, t0 }.