Mathematical Background: Modular Arithmetic, The Euclidean Algorithm, Prime Numbers, And Finite Fields GF(p)
Category: CRYPTOGRAPHY | 30th September 2026, Wednesday
Introduction
Modern Cryptography Rests On A Small Set Of Mathematical Ideas From Number Theory And Abstract Algebra. Ciphers Such As RSA, Diffie-Hellman, Elliptic-curve Systems, And AES All Perform Arithmetic In Structured Finite Sets Rather Than On Ordinary Real Numbers. Understanding These Structures Explains Why The Algorithms Work, Why They Are Efficient, And Why They Are Hard To Break.
This Chapter Covers Four Connected Topics. Modular Arithmetic Supplies The "clock-style" Number System In Which Cryptographic Computation Happens. The Euclidean Algorithm Gives An Efficient Way To Find Common Divisors And Modular Inverses. Prime Numbers Provide The Building Blocks And The Hardness Assumptions. Finite Fields, Especially GF(p), Combine These Ideas Into A Complete Algebraic System With Addition, Subtraction, Multiplication, And Division.
The Material Is Presented In The Order In Which Each Idea Depends On The Previous One. Divisibility Comes First, Since Everything Else Is Built On It. Modular Arithmetic Follows, Then The Euclidean Algorithm, Then Primes And Their Properties, And Finally The Algebra Of Finite Fields. Worked Examples Appear Throughout So The Abstract Definitions Stay Tied To Concrete Numbers.
Divisibility And The Division Algorithm
An Integer B Is Said To Divide An Integer A, Written B | A, If There Exists An Integer M Such That A = Mb. In That Case B Is Called A Divisor Or Factor Of A. For Example, 3 Divides 12 Because 12 = 4 × 3. The Relationship Is Basic But Powerful, Because Most Of Number Theory Asks Which Numbers Divide Which Others.
Several Simple Properties Follow Directly From The Definition. If A | 1, Then A Must Be 1 Or −1. If A | B And B | A, Then A = ±b. Any Nonzero B Divides 0. If A | B And B | C, Then A | C, So Divisibility Is Transitive. If B | G And B | H, Then B Divides Mg + Nh For Any Integers M And N, A Fact Used Constantly In Proofs About Common Divisors.
The Division Algorithm States That For Any Integer A And Any Positive Integer N, There Exist Unique Integers Q And R Such That A = Qn + R With 0 ≤ R < N. Here Q Is The Quotient And R Is The Remainder. The Remainder Is Always Nonnegative And Strictly Smaller Than N. For Instance, Dividing 17 By 5 Gives Q = 3 And R = 2, Since 17 = 3 × 5 + 2.
Negative Numbers Require Care. Dividing −7 By 5 Gives Q = −2 And R = 3, Because −7 = (−2) × 5 + 3, And The Remainder Must Lie Between 0 And 4. Many Programming Languages Return A Negative Remainder For Negative Dividends, Which Differs From The Mathematical Convention. Cryptographic Code Must Therefore Normalize Results Into The Range 0 To N − 1 To Avoid Subtle Errors.
Modular Arithmetic
Two Integers A And B Are Congruent Modulo N If They Leave The Same Remainder When Divided By N, Equivalently If N Divides A − B. This Is Written A ≡ B (mod N). Thus 73 ≡ 4 (mod 23), Because 73 − 4 = 69 = 3 × 23. The Integer N Is Called The Modulus, And The Congruence Behaves Much Like An Equality.
The Notation A Mod N Denotes The Remainder Itself, A Specific Integer In The Range 0 To N − 1. The Two Notations Are Related But Not Identical: A ≡ B (mod N) Is A Statement About A Relationship, While A Mod N Is An Operation That Returns A Value. The Congruence A ≡ B (mod N) Holds Exactly When A Mod N Equals B Mod N.
Congruence Modulo N Is An Equivalence Relation. It Is Reflexive, Since A ≡ A. It Is Symmetric, Since A ≡ B Implies B ≡ A. It Is Transitive, Since A ≡ B And B ≡ C Imply A ≡ C. An Equivalence Relation Splits The Integers Into Disjoint Classes, And Here Each Class Is Called A Residue Class, Containing All Integers With The Same Remainder Modulo N.
The Set Of Residue Classes Modulo N Is Written Z_n = {0, 1, 2, ..., N − 1}. Each Element Stands For An Entire Class Of Integers. For N = 5, The Class Of 2 Includes …, −8, −3, 2, 7, 12, …. Working With The Representatives 0 Through 4 Is Convenient, But It Is Worth Remembering That Each One Actually Represents Infinitely Many Integers.
Arithmetic In Z_n Is Defined By Performing The Ordinary Operation And Then Reducing Modulo N. The Key Property Is That Reduction Can Be Done Before Or After The Operation. Specifically, (a + B) Mod N Equals ((a Mod N) + (b Mod N)) Mod N, And The Same Holds For Subtraction And Multiplication. This Lets Cryptographic Programs Keep Numbers Small By Reducing At Every Step.
Consider A Small Example In Z_7. Adding 5 And 4 Gives 9, Which Reduces To 2. Multiplying 5 And 4 Gives 20, Which Reduces To 6. Subtracting 4 From 5 Gives 1, While Subtracting 5 From 4 Gives −1, Which Reduces To 6. Every Result Lands Back Inside The Set {0, ..., 6}, Which Shows That The Set Is Closed Under These Operations.
Modular Arithmetic Obeys Many Of The Familiar Algebraic Laws. Addition And Multiplication Are Both Commutative And Associative. Multiplication Distributes Over Addition. Zero Is The Additive Identity And One Is The Multiplicative Identity. Every Element Has An Additive Inverse, Namely N − A For A Nonzero A, So Subtraction Is Always Possible. These Properties Make Z_n A Commutative Ring.
Exponentiation Is Central To Public-key Cryptography, And Modular Arithmetic Makes It Practical. Computing 7^100 Directly Produces An Enormous Number, But Reducing After Each Multiplication Keeps Values Below N. The Square-and-multiply Method Goes Further By Using The Binary Expansion Of The Exponent, So A Power Of Size K Bits Needs Only About 2k Multiplications Rather Than 2^k. This Efficiency Is What Makes RSA Feasible.
One Important Difference From Ordinary Arithmetic Is The Failure Of Cancellation. In The Integers, Ab = Ac With A ≠ 0 Implies B = C. In Z_n This Can Fail. For Example, In Z_6 We Have 2 × 1 = 2 × 4 = 2, Yet 1 ≠ 4. The Problem Arises Because 2 And 6 Share The Common Factor 2, Which Creates Zero Divisors Such As 2 × 3 ≡ 0 (mod 6).
Cancellation Is Restored When The Multiplier Is Coprime To The Modulus. If Gcd(a, N) = 1 And Ab ≡ Ac (mod N), Then B ≡ C (mod N). This Observation Leads Directly To The Idea Of Multiplicative Inverses. An Element A In Z_n Has A Multiplicative Inverse Exactly When Gcd(a, N) = 1, And This Condition Explains Why Primes Are Such A Natural Choice Of Modulus.
The Multiplicative Inverse Of A Modulo N Is An Integer A?¹ Satisfying A × A?¹ ≡ 1 (mod N). In Z_7, The Inverse Of 3 Is 5, Since 3 × 5 = 15 ≡ 1. In Z_8, The Element 3 Has Inverse 3, Since 3 × 3 = 9 ≡ 1. But In Z_8 The Element 2 Has No Inverse, Because Gcd(2, 8) = 2. Finding Inverses Efficiently Is Exactly The Job Of The Extended Euclidean Algorithm.
The Elements Of Z_n That Possess Multiplicative Inverses Form The Set Z_n*, The Reduced Residue System, Which Contains All Integers In 0 To N − 1 Coprime To N. It Is Closed Under Multiplication And Forms A Group. The Number Of Elements Is Given By Euler's Totient Function φ(n). For Example, Z_10* = {1, 3, 7, 9}, So φ(10) = 4. This Structure Underlies The RSA Cryptosystem.
Greatest Common Divisors And The Euclidean Algorithm
The Greatest Common Divisor Of Two Integers A And B, Written Gcd(a, B), Is The Largest Positive Integer That Divides Both. For Example, Gcd(12, 18) = 6. Two Integers Are Called Relatively Prime, Or Coprime, When Their Gcd Equals 1. Coprimality Is The Condition Governing The Existence Of Modular Inverses, So Computing Gcds Is A Routine Cryptographic Task.
A Slow Way To Compute A Gcd Is To Factor Both Numbers And Multiply The Shared Prime Factors. This Is Impractical For The Large Numbers Used In Cryptography, Since Factoring Is Believed To Be Computationally Hard. The Euclidean Algorithm Avoids Factoring Entirely And Computes The Gcd Using Only Division With Remainder, Which Is Remarkably Fast Even For Numbers Hundreds Of Digits Long.
The Algorithm Rests On A Simple Identity: Gcd(a, B) = Gcd(b, A Mod B) For A > B > 0. The Reason Is That Any Common Divisor Of A And B Also Divides A − Qb, Which Is The Remainder, And Conversely Any Common Divisor Of B And The Remainder Also Divides A. The Pair Of Numbers Therefore Shrinks While Keeping The Same Gcd, Until The Remainder Reaches Zero.
The Procedure Is Easy To State. Divide A By B To Get A Remainder R. Replace A With B And B With R. Repeat Until The Remainder Is Zero. The Last Nonzero Remainder Is The Gcd. Because Each Remainder Is Strictly Smaller Than The Previous Divisor, The Process Must Terminate, And It Does So In A Small Number Of Steps.
A Worked Example Finds Gcd(1970, 1066). Dividing Gives 1970 = 1 × 1066 + 904. Next, 1066 = 1 × 904 + 162. Then 904 = 5 × 162 + 94, Followed By 162 = 1 × 94 + 68, Then 94 = 1 × 68 + 26, Then 68 = 2 × 26 + 16, Then 26 = 1 × 16 + 10, Then 16 = 1 × 10 + 6, Then 10 = 1 × 6 + 4, Then 6 = 1 × 4 + 2, And Finally 4 = 2 × 2 + 0. The Last Nonzero Remainder Is 2, So Gcd(1970, 1066) = 2.
The Efficiency Of The Algorithm Is Well Understood. The Number Of Division Steps Is At Most About Five Times The Number Of Decimal Digits In The Smaller Input, And The Worst Case Occurs For Consecutive Fibonacci Numbers, A Result Known As Lamé's Theorem. In Bit Terms The Running Time Is Polynomial, Roughly Quadratic In The Length Of The Inputs, So Gcds Of Thousand-bit Numbers Are Computed Almost Instantly.
Bézout's Identity Extends The Picture. For Any Integers A And B, There Exist Integers X And Y Such That Ax + By = Gcd(a, B). This Means The Gcd Can Always Be Written As An Integer Combination Of The Two Numbers. The Identity Is Not Merely A Curiosity; It Is Precisely What Is Needed To Construct Modular Inverses, Because If Gcd(a, N) = 1 Then Ax + Ny = 1 Gives Ax ≡ 1 (mod N).
The Extended Euclidean Algorithm Computes The Bézout Coefficients X And Y Alongside The Gcd. It Runs The Ordinary Algorithm While Tracking, For Each Remainder, How It Can Be Expressed As A Combination Of The Original Two Inputs. Equivalent Back-substitution Through The Division Steps Yields The Same Result. The Cost Is Only Slightly Greater Than That Of The Plain Algorithm.
Here Is A Small Illustration Of Finding The Inverse Of 3 Modulo 11. Applying The Algorithm Gives 11 = 3 × 3 + 2, Then 3 = 1 × 2 + 1, Then 2 = 2 × 1 + 0, So The Gcd Is 1. Working Backward, 1 = 3 − 1 × 2 = 3 − 1 × (11 − 3 × 3) = 4 × 3 − 1 × 11. Therefore X = 4, And 3?¹ ≡ 4 (mod 11). Checking, 3 × 4 = 12 ≡ 1 (mod 11), As Required.
The Extended Algorithm Is Used Whenever A Modular Inverse Is Needed. In RSA Key Generation It Computes The Private Exponent D From The Public Exponent E As The Inverse Of E Modulo φ(n). In Elliptic-curve Arithmetic It Supplies The Inverses Required For Point Addition. In The Chinese Remainder Theorem It Helps Combine Congruences. It Is Therefore One Of The Most Frequently Executed Routines In Public-key Software.
Prime Numbers
A Prime Number Is An Integer Greater Than 1 Whose Only Positive Divisors Are 1 And Itself. The First Primes Are 2, 3, 5, 7, 11, 13, And So On. An Integer Greater Than 1 That Is Not Prime Is Called Composite. The Number 1 Is Neither Prime Nor Composite. The Number 2 Is The Only Even Prime, Which Makes It A Special Case In Many Algorithms.
The Fundamental Theorem Of Arithmetic Says That Every Integer Greater Than 1 Can Be Written As A Product Of Primes, And That This Factorization Is Unique Apart From The Order Of The Factors. For Instance, 360 = 2³ × 3² × 5. Primes Are Therefore The Multiplicative Atoms From Which Every Integer Is Built, Which Is Why They Occupy Such A Central Role In Number Theory.
Euclid Proved That There Are Infinitely Many Primes. His Argument Assumes A Finite List Of All Primes, Multiplies Them Together, And Adds One. The Resulting Number Is Not Divisible By Any Prime On The List, So It Either Is A New Prime Or Has A New Prime Factor, Contradicting The Assumption. Infinitely Many Primes Means Cryptographers Never Run Out Of Candidates When Generating Keys.
The Distribution Of Primes Is Described By The Prime Number Theorem, Which States That The Number Of Primes Up To X Is Approximately X Divided By The Natural Logarithm Of X. Near A Large Number N, Roughly One Integer In Ln N Is Prime. For A 1024-bit Number This Is About One In 710, Or About One In 355 If Only Odd Numbers Are Considered. Random Search Therefore Finds Primes Quickly.
Because Factoring Is Believed To Be Hard While Multiplication Is Easy, Primes Support One-way Behavior. Multiplying Two 1024-bit Primes Takes Microseconds, But Recovering Them From Their Product Is Infeasible With Known Classical Algorithms. RSA Depends Directly On This Asymmetry. Should An Efficient Factoring Method Be Found, RSA Would Fail, Which Is Why Quantum Algorithms Such As Shor's Algorithm Are Considered A Serious Long-term Threat.
Testing Whether A Number Is Prime Is Much Easier Than Factoring It. The Simplest Method, Trial Division, Checks Divisibility By Every Integer Up To The Square Root, But It Is Far Too Slow For Large Numbers. Practical Systems Use Probabilistic Tests, Which Quickly Rule Out Composites And Report Probable Primes With An Error Probability That Can Be Made Negligibly Small.
Fermat's Little Theorem Underlies Many Of These Tests. It States That If P Is Prime And A Is Not Divisible By P, Then A^(p−1) ≡ 1 (mod P). For Example, With P = 7 And A = 3, We Have 3? = 729 = 104 × 7 + 1, So 3? ≡ 1 (mod 7). If A Candidate N Fails This Congruence For Some Base A, Then N Is Definitely Composite.
Fermat's Test Can Be Fooled. Some Composite Numbers, Called Carmichael Numbers, Satisfy The Congruence For Every Base Coprime To Them. The Smallest Is 561 = 3 × 11 × 17. Because Of Such Exceptions, Stronger Tests Were Developed. The Miller-Rabin Test Refines The Idea By Examining Square Roots Of 1 Modulo N, And It Has No Analogue Of Carmichael Numbers That Defeat It For All Bases.
In The Miller-Rabin Test, One Writes N − 1 = 2^s × D With D Odd, Chooses A Random Base A, And Checks Whether A^d ≡ 1 Or A^(2^r D) ≡ −1 For Some R In The Range 0 To S − 1. If Neither Holds, N Is Composite. If It Holds, N Is A Probable Prime. For Any Composite N, At Most One Quarter Of The Bases Fail To Expose It, So K Independent Rounds Give An Error Probability Of At Most 4^(−k).
Euler's Theorem Generalizes Fermat's. For Any A Coprime To N, A^φ(n) ≡ 1 (mod N). When N Is Prime, φ(n) = N − 1, And The Result Reduces To Fermat's Little Theorem. When N = Pq For Distinct Primes P And Q, φ(n) = (p − 1)(q − 1). This Formula Is The Heart Of RSA: Encryption And Decryption Are Inverse Operations Because Exponents That Multiply To 1 Modulo φ(n) Cancel Out.
The Chinese Remainder Theorem Shows How To Solve Simultaneous Congruences With Pairwise Coprime Moduli. Given X ≡ A? (mod M?) And X ≡ A? (mod M?) With Gcd(m?, M?) = 1, There Is A Unique Solution Modulo M?m?. It Allows Large Computations Modulo A Composite To Be Split Into Smaller Computations Modulo Each Prime Factor, Then Recombined. RSA Implementations Use It To Speed Up Decryption By Roughly A Factor Of Four.
Groups, Rings, And Fields
To Describe Finite Fields Precisely, One Needs The Language Of Abstract Algebra. A Group Is A Set G With A Binary Operation Satisfying Four Properties: Closure, Associativity, An Identity Element, And An Inverse For Every Element. If The Operation Is Also Commutative, The Group Is Called Abelian. The Integers Under Addition Form An Abelian Group, As Does Z_n Under Addition Modulo N.
The Structure Of Z_n* Under Multiplication Is Also An Abelian Group, Provided One Restricts To Elements Coprime To N. Inverses Exist There By Construction. A Group Is Called Cyclic If Some Element G, Called A Generator, Produces Every Other Element As A Power. Cyclic Groups Are Important Because The Difficulty Of Finding The Exponent Given G And The Result, The Discrete Logarithm Problem, Supports Diffie-Hellman And DSA.
A Ring Is A Set With Two Operations, Usually Called Addition And Multiplication, Such That It Forms An Abelian Group Under Addition, Multiplication Is Associative, And Multiplication Distributes Over Addition. The Integers And Z_n Are Rings. A Ring Is Commutative If Multiplication Commutes. An Integral Domain Is A Commutative Ring With A Multiplicative Identity And No Zero Divisors, Meaning Ab = 0 Forces A = 0 Or B = 0.
A Field Is A Commutative Ring In Which Every Nonzero Element Has A Multiplicative Inverse. In Other Words, One Can Add, Subtract, Multiply, And Divide By Nonzero Elements, And All The Usual Laws Hold. The Rational Numbers, Real Numbers, And Complex Numbers Are All Fields, But They Are Infinite. Cryptography Favors Finite Fields, Since Computers Work With Bounded, Exact Values And Since Finite Structure Gives Hard Mathematical Problems.
The Integers Are Not A Field, Because Most Integers Such As 2 Have No Integer Inverse. Z_n Is Not Generally A Field Either, Because Elements Sharing A Factor With N Lack Inverses. The Lesson Is That Division Requires Every Nonzero Element To Be Coprime To The Modulus. The Only Way To Guarantee That For All Nonzero Elements Is To Make The Modulus A Prime Number, Which Leads Straight To The Finite Field GF(p).
The Finite Field GF(p)
For A Prime P, The Set Z_p = {0, 1, ..., P − 1} With Addition And Multiplication Modulo P Is A Finite Field, Denoted GF(p), The Galois Field Of Order P. It Is Named After Évariste Galois. Because P Is Prime, Every Nonzero Element A Satisfies Gcd(a, P) = 1, So Each Has A Multiplicative Inverse That The Extended Euclidean Algorithm Can Compute.
The Proof That GF(p) Is A Field Follows From The Earlier Discussion. Closure, Associativity, Commutativity, And Distributivity Are Inherited From The Integers. The Additive Identity Is 0 And Every Element A Has Additive Inverse P − A. The Multiplicative Identity Is 1. Only The Existence Of Multiplicative Inverses Needs The Primality Of P, And Bézout's Identity Supplies Them. Hence All Field Axioms Hold.
Consider GF(7) Concretely. Its Elements Are 0 Through 6. The Inverses Of The Nonzero Elements Are 1?¹ = 1, 2?¹ = 4, 3?¹ = 5, 4?¹ = 2, 5?¹ = 3, And 6?¹ = 6. Each Pair Multiplies To 1 Modulo 7. Division Is Defined As Multiplication By The Inverse, So 3 ÷ 5 Equals 3 × 3 = 9 ≡ 2 In GF(7). Complete Arithmetic, Including Division, Is Therefore Available.
By Contrast, Consider GF(8). One Might Expect The Set {0, ..., 7} With Arithmetic Modulo 8 To Be A Field, But It Is Not, Since 8 Is Not Prime And Elements Such As 2, 4, And 6 Have No Inverses. A Field Of Order 8 Does Exist, But It Is Built Differently, As GF(2³) Using Polynomial Arithmetic. Fields Of Order P^n With N Greater Than 1 Are Called Extension Fields And Require Polynomials.
Every Finite Field Has A Number Of Elements Equal To A Prime Power P^n, And For Each Prime Power There Is Essentially One Field, Unique Up To Renaming Of Elements. The Prime P Is Called The Characteristic Of The Field, Meaning That Adding 1 To Itself P Times Gives 0. For GF(p) The Characteristic Is P Itself. This Uniqueness Result Means That "the" Field Of A Given Order Is A Well-defined Object.
The Multiplicative Group Of GF(p), The Nonzero Elements Under Multiplication, Is Cyclic Of Order P − 1. This Is A Deep And Useful Fact. It Means There Is Always A Primitive Root G Such That The Powers G?, G¹, ..., G^(p−2) List Every Nonzero Element Exactly Once. For P = 7, The Element 3 Is A Primitive Root, Since Its Powers Are 1, 3, 2, 6, 4, 5, Covering All Six Nonzero Residues.
Not Every Element Is A Primitive Root. In GF(7), The Element 2 Has Powers 1, 2, 4 And Then Repeats, So Its Order Is 3, Not 6. The Order Of An Element Is The Smallest Positive Exponent Giving 1, And By Lagrange's Theorem It Always Divides P − 1. Choosing A Generator, Or An Element Of Large Prime Order, Is A Routine Step When Setting Up Diffie-Hellman Or DSA Parameters.
The Discrete Logarithm Problem In GF(p) Asks: Given A Prime P, A Generator G, And A Value Y, Find X Such That G^x ≡ Y (mod P). Computing Y From X Is Easy Using Fast Exponentiation, But Going The Other Way Is Believed To Be Hard When P Is Large. Diffie-Hellman Key Exchange Lets Two Parties Derive A Shared Secret From Public Values Using This Asymmetry, Without Ever Transmitting The Secret Itself.
In Diffie-Hellman, The Parties Agree On A Prime P And A Generator G. Alice Picks A Secret A And Sends G^a Mod P, While Bob Picks A Secret B And Sends G^b Mod P. Each Raises The Received Value To Their Own Secret, Obtaining G^(ab) Mod P. An Eavesdropper Sees Only G^a And G^b And Would Need To Solve The Discrete Logarithm Problem To Recover The Shared Key. The Whole Scheme Works Because Arithmetic In GF(p) Is Commutative.
Division In GF(p) Also Makes Possible Elliptic-curve Cryptography Over Prime Fields. An Elliptic Curve Over GF(p) Is The Set Of Solutions To An Equation Such As Y² = X³ + Ax + B Modulo P, Together With A Point At Infinity. Adding Points Uses Formulas That Involve Dividing By Differences Of Coordinates, Which Is Why A Genuine Field Is Needed. Curves Offer Equivalent Security With Much Shorter Keys Than Plain Modular Exponentiation.
Polynomials Over GF(p) Give A Route To Extension Fields And To The Arithmetic Used In AES. In AES, Bytes Are Treated As Elements Of GF(2?), Constructed As Polynomials With Coefficients In GF(2) Reduced Modulo An Irreducible Polynomial Of Degree 8. Addition Becomes Bitwise XOR, And Multiplication Involves Polynomial Multiplication Followed By Reduction. The Same Field Axioms Hold, So Every Nonzero Byte Has An Inverse, Which The S-box Uses.
Fields Also Matter In Coding Theory And Secret Sharing. Shamir's Secret Sharing Scheme Hides A Secret As The Constant Term Of A Random Polynomial Over GF(p) And Gives Each Participant A Point On The Curve. Any Threshold Number Of Points Recovers The Polynomial By Interpolation, Which Requires Division In The Field, While Fewer Points Reveal Nothing. Reed-Solomon Error-correcting Codes Rely On The Same Polynomial Algebra Over Finite Fields.
Conclusion
The Four Topics Covered Here Form A Coherent Toolkit. Modular Arithmetic Provides A Bounded Number System In Which Computations Stay Small And Exact. The Euclidean Algorithm And Its Extended Form Provide Fast Gcd Computation And Modular Inverses. Prime Numbers Supply The Hardness Assumptions, The Moduli That Guarantee Invertibility, And The Structure Behind Fermat's And Euler's Theorems.
Finite Fields, And GF(p) In Particular, Unite These Ideas Into A Full Arithmetic In Which Addition, Subtraction, Multiplication, And Division All Work. This Completeness Makes Them The Natural Setting For Discrete Logarithms, Elliptic Curves, And Secret Sharing, While Their Extension Fields Power Symmetric Ciphers Such As AES. A Solid Grasp Of These Foundations Makes The Design And Security Arguments Of Modern Cryptographic Systems Far Easier To Follow.
Tags:
Modular Arithmetic, The Euclidean Algorithm, Prime Numbers, And Finite Fields GF, Mathematical Background
