Math Operations as Algorithms

Addition

The runtime for addition is O(n) where n is the number of bits in each input number.

Multiplication

The rule here is $x\cdot y=\{\begin{array}{llc}2\left(x\ast \left(\frac{y}{2}\right)\right)& & \text{if y is even,}\\ x+\left(x\ast \frac{y}{2}\right)& & \text{if u is odd,}\end{array}$
The algorithm for performing this is recursive with a time complexity of O(n^2), where for 2 bit integers, we are bit shifting left and right and checking the parity of the last bit as well as performing addition at most once. We can write a better algorithm using divide and conquer.

Division

To divide an integer $x$ and $y$ where $y\ne 0$, we need to find a quotient and a remainder such that $x=q\cdot y+r$. Similar to multiplication, we can define an O(n^2) algorithm.

Modular Arithmetic

Basically, $x\%N$ is the remainder when $x$ is divided by $N$.
This can be thought of as a function where input $x$ and $N$ modded together produce $r$.
There is also another use for the modulo.

Congruency

Two numbers are congruent if their modulo with $N$ are the same.
Note that $a-kb=a\text{ mod }b$

Note

Note that $\equiv$ means equivalent, not equals

Note that $x\equiv y(\text{mod N})⟺N\text{ divides}(x-y)\text{ (with no remainder)}$. There is a proof in the lecture notes for this.

Rules

Look these up if you forget what they mean…

1. Substitution rule
   1. $x\equiv x^{\prime }(\text{mod N})$ and $y\equiv y^{\prime }(\text{mod N})$, then $x+y\equiv x^{\prime }+y^{\prime }(\text{mod N})$ and $xy\equiv x^{\prime }{y}^{\prime }(\text{mod N})$
      1. As a consequence, you can apply repeatedly to simplify a modulo expression and reduce an intermediate stage to its remainder modulo N at any stage. The idea here is to try to force the base to become a 1 or -1.
2. Associativity
3. Commutativity
4. Distributivity

Modular Exponentiation

The idea here is that if you want to compute $x^y\%N$ and $x$ and $y$ are fairly large then, we can’t just compute the exponential and take its mod. But, $x^y\%N$ is a number between $0\dots N-1$.

We can define a recursive algorithm to do this… $x^{y=}\{\begin{array}{ll}(x^{\lfloor \frac{y}{2}\rfloor }{)}^2,& \text{if y is even}\\ x\cdot (x^{\lfloor \frac{y}{2}\rfloor }{)}^2,& \text{if y is even}\end{array}$ This runs in $O(n^3)$ time (with respect to $n$ bits) since $y$ is reduced by 1 bit on every recursive call ($O(n)$) and each call runs multiplication $O(n^2)$ as we can see above.

Greatest Common Divisor

Given two integers a and b, find the largest integer that divides both of them. Here, you basically factor $a$, and $b$ and multiply their common factors.

To do so, you use euclid’s rule.

Euclids Rule

This states that if $a$, and $b$ are positive integers with $a\ge b$ then…

$gcd(a,b)=gcd(a\text{ mod }b,b)$

Basically, this tells us that we can reduce the arguments in our call until we get something that we can compute (our base case which is when $b=0$, in which case we return $a$). Otherwise, we make a recursive call with (b, a mod b) where we actually swap the positions of a and b from the function call arguments.

Property

if $a\ge b$ then $a\%b<a/2$

At each call, both arguments are halved. This requires at most 2n recursive calls where each call requires a division which occurs in O(n^2) time. The runtime of this is $O(n^3)$.

An Extension

How do we verify that a number $d$ is the GCD of $a$ and $b$?

Property

if $d$ divides both $a$ and $b$ with no remainder and $d=ax+by$ for some integers $x$ and $y$. then d must be the greatest divisor. Note that x or y could be negative.

Well, this is because that a and b can be written as for example, $a=p\cdot gcd(a,b)$ so $ax+by=gcd(a,b)(px+qy)$. Therefore $d$ is the GCD. This is how we check if something is the GCD where we extend Euclid’s rule by returning a triple (x,y,d) where x and y cert d. Maybe remember this algorithm.

function extended-euclid(a,b)
Input: 2 integers a and b where a>=b>=0
Output: Integers(x,y,d) such that d=gcd(a,b) and ax+by=d

if b = 0
	return (1,0,a)
(x',y',d) = extended-euclid(b, a%b)
return (y', x'-floor(a/b)y',d)

Modular Division

An integer $x$ is the multiplicative inverse of $a\text{ modulo }N$ if $a\cdot x\equiv 1(modN)$.

• For a given $a$, there can be at most one inverse $x$ in $\{0,1,\dots ,N-1\}$.
• For certain choices of $a$ and $N$, there is no multiplicative inverse.

When does an inverse exist?
$ax\equiv 1(modN)⟹ax-1\text{ is divisible by N}$ which implies that $ax-1=kN$ for some $k$ where if we redefined $-k=y$, we get $ax+Ny=1$ which says that the gcd(a,N)=1 or that $a$ and $N$ are co-prime. This inverse can be found in $O(n^3)$ time as $y\text{ mod }N$ where $y$ comes from $(x,y,d)=\text{extended-euclid(N, a)}$ (a call to extended Euclid).