RSA Part 1

2573 days ago by bburkho

The first function takes inputs $a$ and $b$ and returns $[q,r]$ such that $a = bq + r$. This is performing a modulus operation such that $0\leq{r}<b$.

def my_div(a,b): this = 1 count = 0 nums = 0 #checks b > 0 and a and b are integers if b < 1 or floor(a) != a or floor(b) != b: return 0 #in the case that a is negative since b is positive q will be negative if abs(a) != a: this = -1 a = abs(a) double = [] #the infinite while finds k such that (2^k)*b <= a and (2^k+1)*b > a while(true): b = 2*b count += 1 if b > a: b = b/2 count -= 1 a = a - b #once k is found we use nums to find q nums += (2^count) discount = count for i in range(discount): b = b/2 count -= 1 if (a - b) >= 0: nums += (2^count) #on the final iteration we find r a = a - b #get out of the infinite loop once we have q and r break return [this*nums,a] 
       

Examples:

my_div(35,15) 
       
[2, 5]
[2, 5]
my_div(-48,9) 
       
[-5, 3]
[-5, 3]

The second function will take the same inputs $a$ and $b$ and this time return a triple $[x,y,d]$ such that the equation $ax + by = d$ is satisfied. The results $x$ and $y$ will be integers as a result of the equality gcd($a$,$b$) = gcd($b$,$r$) where r is the remainder determined from my_div($a$,$b$).

def my_gcd(c,d): quads = [] count = 0 #checks that they're both integers if floor(c) != c or floor(d) != d: return o #checks that at least one of them is non-zero if c < 1 and d < 1: return 0 #gets things in the right order if c >= d: large = c small = d else: large = d small = c a = [1,0,large,0,1,small] sol = my_div(large,small) #perform successive row operations to solve for q,x, and y then #break once we have the gcd and 0 as the farthest column in the #matrix where the matrix is represented with linear indices while(true): a[0] = a[0] - sol[0]*a[3] a[1] = a[1] - sol[0]*a[4] a[2] = a[2] - sol[0]*a[5] if(a[2] == 0 or a[5] == 0): break sol = my_div(a[5],a[2]) a[3] = a[3] - sol[0]*a[0] a[4] = a[4] - sol[0]*a[1] a[5] = a[5] - sol[0]*a[2] sol = my_div(a[5],a[2]) if(a[2] == 0 or a[5] == 0): break if(a[2] == 0): print("{}*{} + {}*{} = {}".format(a[3],large,a[4],small,a[1])) return [a[3],a[4],a[5]] else: print("{}*{} + {}*{} = {}".format(a[0],large,a[1],small,a[2])) return [a[0],a[1],a[2]] 
       

A few examples of output:

my_gcd(12345,545) 
       
-66*12345 + 1495*545 = 5
[-66, 1495, 5]
-66*12345 + 1495*545 = 5
[-66, 1495, 5]
my_gcd(34564,346) 
       
48*34564 + -4795*346 = 2
[48, -4795, 2]
48*34564 + -4795*346 = 2
[48, -4795, 2]