Number Theory — History & OverviewPart I — What Is Number Theory & Why Is It Relevant Today?Jesus NajeraBlockedUnblockFollowFollowingMar 3Math is the Universe’s natural tongue.
Since the very beginning of our existence as a species, numbers have deeply fascinated us.
Often inviting our greatest thinkers to unravel the many, deep mysteries of the cosmos, the study of natural numbers, Number Theory, is one of the oldest branches of mathematics.
The pureness of Number Theory has captivated mathematicians generation after generation — each contributing to the branch that Carl Gauss described as the “Queen of Mathematics.
” Until relatively recent breakthroughs, Number Theory reigned as the king of pure math.
Today, however, a basic understanding of Number Theory is an absolutely critical precursor to cutting-edge software engineering, specifically security-based software.
Number Theory is at the heart of cryptography — which is itself experiencing a fascinating period of rapid evolution, ranging from the famous RSA algorithm to the wildly-popular blockchain world.
Two distinct moments in history stand out as inflection points in the development of Number Theory.
First, in archaic times, Euclid put forth his GCD (Greatest Common Divisor) algorithm — a brilliant set of steps that simplifies fractions to their simplest form using geometrical observations.
Then, approximately two-thousand years later, Karl Gauss formalized Euclid’s principles by marrying together Euclid’s informal writings with his own extensive proofs in the timeless Disquistiones Arithmeticae.
Euclid & The Greatest Common DivisorThe origin of Number Theory as a branch dates all the way back to the B.
Cs, specifically to the lifetime of one Euclid.
An extraordinary mathematician, Euclid of Alexandria, also known as the “Father of Geometry,” put forth one of the oldest “algorithms” (here meaning a set of step-by-step operations) recorded.
This algorithm, the Greatest Common Divisor, stands the test of time as our kickoff point for Number Theory due to the fascinating properties it highlighted in natural numbers.
Around 300 B.
C, Euclid unleashed his classic Elements book series; a series of ten books spanning a range of topics from integers, to line segments & surface areas.
Interestingly enough, his GCD algorithm wasn’t listed once but twice in this series — first in Book 7 (presented with numbers), then later in Book 10 (presented through geometry).
According to math historians, it’s likely that the latter form of the algorithm, the one grounded in geometry (Book 10), actually preceded the alternative, the number-based form found in Book 7.
Working with lengths, areas, & volumes, it’s theorized that the GCD algorithm was of great importance to Euclid because it provided a way to find the largest common length between any two segments (a) & (b).
Given the time period he lived in, it’s highly likely that this observation was of great use for anyone & everyone involved in any type of construction (masonry, carpentry, etc…).
Expanding on the previous definition, the Greatest Common Divisor, geometrically-speaking, of two lengths (a) & (b) is the greatest length (g) that measures a & b evenly; alternatively, lengths (a) & (b) are both integer multiples of the length (g).
A geometric example follows below — imagine that we’re tasked with tiling a 15m x 25m floor.
In order to minimize costs, we only want to buy tile length of the same size; which requires that we calculate the largest length of tile (in meters) that’ll perfectly fit, both in length & width, without breaking apart.
In other words, what’s the great common divisor of 15 & 25?We glossed over the specific steps involved in calculating the GCD for our example, but, hopefully, the illustration above provides an intuitive understanding of the geometry involved.
As circled, the answer to our example question is 5 m, which indeed is both the largest common integer found in 15 & 25.
Gauss & The Fundamental Theorem of ArithmeticThe following large leap in Number Theory stems from a break-through approximately ~2000 years after Euclid.
At the stunning young age of 21, one Carl Gauss put forward a dissertation that married Euclid’s elements with then-modern math.
His masterpiece publication, Disquistiones Arithmeticate (loosely translated to “Arithmetical Investigations) packed multiple brilliant & precise methods that, while not necessarily all his original work, aggregated & systematized the field of Number Theory.
With this publication he established the branch by formalizing previously scattered & informal methods, providing original answers to important outstanding problems, & founding the landscape for future contributors.
The cornerstone eureka moment of Disquistiones is a now-timeless theorem known as the Fundamental Theorem of Arithmetic:Any integer greater than 1 is either a prime, or can be written as a unique product of prime numbers (ignoring the order).
The Wikipedia definition above becomes digestible by splitting it into two separate parts.
The first, states that any integer greater than 1 is either prime itself or can be constructed by multiplying strictly prime numbers.
The second part guarantees that for every non-prime (composite) number, there is only one, single way of multiplying these prime numbers (again, ignoring order).
Put another way, the primes are the (multiplicative) “building blocks” of the integers: products of primes will generate (uniquely) all the integers.
This result was undoubtedly known to mathematicians of past centuries, but Gauss, in the Disquisitiones, was the first to state it formally and give a rigorous proof.
Ulam SpiralOnto Crafty Cryptographic ApplicationsNow equipped with the basic history of number theory & a quick preview into the depth of its impact, it’s time to familiarize ourselves with the most applicable topic within number theory: cryptography.
As we’ll see next, while Gauss formally set the stage for the branch, early examples of cryptographic systems were already well in existence, with pretty daring stakes.
Through a few of those examples, we’ll extrapolate basic, common cryptography principles; which, afterward, will help us break-down & understand one of the most important security algorithms in modern times: the RSA algorithm.
sourceshttps://www.
cs.
purdue.
edu/homes/spa/courses/cs182/mod5.
pdf.. More details