CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page

Was this helpful?

Export as PDF

Ideals

Example: Ideals of the integers

Definition - Ideal of Z\mathbb{Z}Z

I⊆Z I \subseteq \mathbb{Z}I⊆Zis an ideal   ⟺  ∀ a,b∈I and,z ∈Z\iff \forall \ a, b \in I \text{ and} , z\ \in \mathbb{Z}⟺∀ a,b∈I and,z ∈Zwe have

a+b∈I and az∈Ia + b \in I \text{ and } az \in Ia+b∈I and az∈I

Example: aZ={az : z∈Z}→2Z,3Z,4Z,…a\mathbb{Z} = \{az \ : \ z \in \mathbb{Z} \} \to 2\mathbb{Z}, 3\mathbb{Z}, 4\mathbb{Z}, \dotsaZ={az : z∈Z}→2Z,3Z,4Z,… - multiples of aaa

Remarks:

  1. ∀a,b∈Z\forall a, b \in \mathbb{Z}∀a,b∈Zwe have b∈aZ  ⟺  a∣bb \in a\mathbb{Z} \iff a | bb∈aZ⟺a∣b

  2. I1+I2={a1+a2 : a1∈I1,a2∈I2}I_1 + I_2 = \{a_1 + a_2 \ : \ a_1 \in I_1 , a_2 \in I_2\}I1​+I2​={a1​+a2​ : a1​∈I1​,a2​∈I2​} is an ideal

Example: Consider 18Z+12Z18\mathbb{Z} + 12\mathbb{Z}18Z+12Z. This ideal contains 6=18⋅1+12⋅(−1)⇒18Z+12Z=6Z6 = 18 \cdot 1 + 12 \cdot (-1) \Rightarrow 18\mathbb{Z} + 12\mathbb{Z} = 6\mathbb{Z}6=18⋅1+12⋅(−1)⇒18Z+12Z=6Z

Greatest common divisor

Let a,b∈Za, b \in \mathbb{Z}a,b∈Z be 2 integers. If d=gcd⁡(a,b)⇒aZ+bZ=dZd = \gcd(a, b) \Rightarrow a\mathbb{Z} + b\mathbb{Z} = d\mathbb{Z}d=gcd(a,b)⇒aZ+bZ=dZ

PreviousContinued FractionsNextPolynomials With Shared Roots

Last updated 4 years ago

Was this helpful?