MindMap Gallery Chapter 8-Number Theory
Summary of the basics of number theory. "Chapter 8-Number Theory" in cryptography theory and technology refers to the introduction to number theory, which is one of the core concepts in cryptography.
Edited at 2024-01-22 23:35:28This Valentine's Day brand marketing handbook provides businesses with five practical models, covering everything from creating offline experiences to driving online engagement. Whether you're a shopping mall, restaurant, or online brand, you'll find a suitable strategy: each model includes clear objectives and industry-specific guidelines, helping brands transform traffic into real sales and lasting emotional connections during this romantic season.
This Valentine's Day map illustrates love through 30 romantic possibilities, from the vintage charm of "handwritten love letters" to the urban landscape of "rooftop sunsets," from the tactile experience of a "pottery workshop" to the leisurely moments of "wine tasting at a vineyard"—offering a unique sense of occasion for every couple. Whether it's cozy, experiential, or luxurious, love always finds the most fitting expression. May you all find the perfect atmosphere for your love story.
The ice hockey schedule for the Milano Cortina 2026 Winter Olympics, featuring preliminary rounds, quarterfinals, and medal matches for both men's and women's tournaments from February 5–22. All game times are listed in Eastern Standard Time (EST).
This Valentine's Day brand marketing handbook provides businesses with five practical models, covering everything from creating offline experiences to driving online engagement. Whether you're a shopping mall, restaurant, or online brand, you'll find a suitable strategy: each model includes clear objectives and industry-specific guidelines, helping brands transform traffic into real sales and lasting emotional connections during this romantic season.
This Valentine's Day map illustrates love through 30 romantic possibilities, from the vintage charm of "handwritten love letters" to the urban landscape of "rooftop sunsets," from the tactile experience of a "pottery workshop" to the leisurely moments of "wine tasting at a vineyard"—offering a unique sense of occasion for every couple. Whether it's cozy, experiential, or luxurious, love always finds the most fitting expression. May you all find the perfect atmosphere for your love story.
The ice hockey schedule for the Milano Cortina 2026 Winter Olympics, featuring preliminary rounds, quarterfinals, and medal matches for both men's and women's tournaments from February 5–22. All game times are listed in Eastern Standard Time (EST).
Chapter 8-Number Theory
Prime number
prime numbers only have divisors of 1 and self
factor
factoring a number is relatively hard compared to multiplying the factors
prime factorisation
is when its written as a product of primes
Relatively Prime Numbers (coprime)
if the have no common divisors apart from 1
Conversely, can determine the GCD by comparing their prime factorizations and using least powers
Fermat's Theorem
Notice
1. Here a is a number that is relatively prime to p, so after multiplying a and then mod p, you will get a new sequence of 1~p-1, which may not be sequential.
2.(p-1)! and p are exponents because 1~p-1 and p are prime numbers to each other.
3.(p-1)! and p are prime numbers to each other, so they can be eliminated because
In the modulo p operation, a number that is relatively prime to p can be "reduced"
ie This number is relatively prime with p, which means that it must have an inverse element in the modulo p operation. In the mod p operation, this inverse element can be multiplied at the same time, and the result is 1 in the modulo p operation.
Chinese Remainder Theorem(CRT)
Used to speed up modular operations
Euler
def
complete set of residues
0....n-1
reduced set of residues
is numbers(residues) which are relatively prime to n
number of elements in reduced set of residues
computation
Euler's Theorem
def
Prime Distribution
Appears every ln(n)
To find a prime number of size n, you only need to test about 0.5ln(n) numbers, because prime numbers are more densely distributed in technology than among all integers, and even numbers can be ignored
Primality Testing
Trial Division
Test whether a number is prime by dividing it by all prime numbers less than its square root.
Only applies to smaller numbers
Statistical Primality test
based on properties that all prime numbers satisfy property
but some composit number, called pseudo-prmes, also satisfy the property
Suitable for large numbers
example
Miller Rabin Algorithm
Based on Fermat’s Little Theorem and properties of prime numbers
If n is not judged to be a prime number in multiple tests, you can become more and more confident that n is a prime number, but you cannot be sure.
slower Deterministic Primality Test (slow deterministic primality test)
AKS is also a deterministic primality test