Notes on Algorithms of Computer Programs

What is computer programming?

Simply put, it tells the computer what to do. Computers can do a lot of things, but they are not very good at thinking for themselves. Programmers need to tell it specific details like feeding a child, and make the computer understand the language-algorithm.

Algorithm refers to an accurate and complete description of a problem-solving solution. It is a series of clear instructions for solving problems. Algorithm represents a systematic method to describe the strategic mechanism for solving problems. In other words, it is possible to obtain the required output within a limited time for a certain specification of input. If an algorithm is flawed or inappropriate for a problem, executing the algorithm will not solve the problem. Different algorithms may use different time, space, or efficiency to complete the same task. The quality of an algorithm can be measured by its space complexity and time complexity.
The instructions in the algorithm describe a calculation that, when run, can start from an initial state and a (possibly empty) initial input, pass through a limited and clearly defined series of states, and finally produce an output and stop at an final state. The transition from one state to another is not necessarily deterministic. Some algorithms, including randomized algorithms, contain random inputs.
The concept of formal algorithms originated in part from attempts to solve Hilbert's decision problems and took shape in subsequent attempts to define efficient computability or efficient methods. These attempts included the recursive functions proposed by Kurt Gödel, Jacques Herbrand, and Stephen Cole Crane in 1930, 1934, and 1935 respectively, the lambda calculus proposed by Alonzo Church in 1936, Emil Leon Post's Formulation 1 in 1936 and Alan Turing's Turing Machine in 1937. Even today, there are often cases where intuitive ideas are difficult to define as formal algorithms.

Characteristics

An algorithm should have the following five important characteristics:
1. Finiteness
The finiteness of an algorithm means that the algorithm must be able to execute Terminates after a finite number of steps;
2. Definiteness
Each step of the algorithm must be clearly defined;
3. Input
An algorithm has 0 or more An input is used to describe the initial situation of the operation object. The so-called 0 input means that the algorithm itself sets the initial conditions;
4. Output (Output)
An algorithm has one or more outputs to reflect the Enter the result after data processing. An algorithm without output is meaningless;
5. Feasibility (Effectiveness)
Any calculation steps performed in the algorithm can be decomposed into basic executable operation steps, that is, each calculation step is Can be completed within a limited time (also called effectiveness).

Elements

1. Calculations and operations of data objects: The basic operations that a computer can perform are described in the form of instructions. The set of all instructions that a computer system can execute becomes the instruction system of the computer system. The basic calculations and operations of a computer are as follows:
1. Arithmetic operations: addition, subtraction, multiplication and division, etc.
2. Logical operations: operations such as OR, AND, NOT, etc.
3. Relational operations: greater than, Operations such as less than, equal to, and not equal to
4. Data transmission: input, output, assignment and other operations [1]
2. Algorithm control structure: The functional structure of an algorithm not only depends on the selected operations, but also It also depends on the execution order between operations.

Classification

Algorithms can be roughly divided into basic algorithms, data structure algorithms, number theory and algebraic algorithms, computational geometry algorithms, graph theory algorithms, dynamic programming and numerical analysis, encryption algorithms, Sorting algorithm, retrieval algorithm, randomization algorithm, parallel algorithm, Hermitian deformation model, random forest algorithm.
Algorithms can be broadly divided into three categories:
1. Limited, deterministic algorithms. This type of algorithm terminates within a limited period of time. They may take a long time to perform a specified task, but will still terminate within a certain amount of time. The results of such algorithms often depend on the input values.
　2. Finite, non-deterministic algorithm This type of algorithm terminates in a limited time. However, for a given value (or values), the result of the algorithm is not unique or certain.
　Three, infinite algorithms are those algorithms that do not terminate because the termination definition conditions are not defined, or the defined conditions cannot be satisfied by the input data. Often, infinite algorithms arise due to a failure to define termination conditions.

Basic Number Theory Reserve

Quadratic Remainder

First look at the formula x2≡n(modp). We now give n and ask to find the value of x. If it can be found, n is the quadratic remainder of mod p, which is actually the ultimate square of n in the sense of mod p. Cipolla is an algorithm used to find x in the above equation.

Legendre symbol

Legendre symbol is a powerful tool to determine whether a number is the quadratic remainder of p. p must be an odd prime number. (n,p) means that n is the Legendre symbol with respect to p. In fact, it is to determine whether n is the quadratic remainder of p.

(np)=⎧⎩⎨1——p is not a multiple of n, n is the quadratic remainder of p −1——p is not a multiple of n, n is the quadratic non-residue of p (either quadratic remainder or non-residue) 0——p is a multiple of n

It seems like a lot of nonsense, Legendre is just standing on the shoulders of giants Just summarized it above.
In fact, Legendre also summarized some properties, but generally only the Euler criterion is used. It may be useful if the Legendre symbol is a product function.
But I still don’t know how to judge whether n is the quadratic remainder of p. Let’s look down at Euler’s criterion

ll Legendre(ll a, ll p)
{
return qsm( a, (p-1)/2, p);
} 12341234

Euler’s criterion

Let’s first review Euler’s theorem xφ(p)≡1 (modp)
Because p here is an odd prime number, so xp−1≡1(modp)
Perform the square root operation on xp−1, in the imaginary number field xp−12≡±1(modp), if If it is equal to 1, it will definitely be opened, and if it is -1, it will definitely not be opened. Therefore, whether x is the quadratic remainder of n uses this Euler criterion.

if(qsm(n,(p-1)/2)==p-1){ printf("No root\n");
continue;
}12341234

-1 is p-1 in the sense of mod p.

Algorithm flow

Given n and p
Even if our Legendre sign of n with respect to p is 1, then how do we take the square of n?
Now is the time to open your mind.

Find a number a

We randomly assign a number a, and then perform the square root operation on a2−n (that is, calculate the value of its Legendre symbol) until their Legendre symbol is Until -1 (that is, until the prescription cannot be opened).
Just find an a that satisfies (a2−n)p−12=−1
Don’t worry about why for now, we will talk about it later, we will silently worship Cipolla’s imagination now.

while(1){
a=rand()%p;
w=(a*a-n+p)%p; if(qsm(w,(p-1) /2)==p-1)break;
}1234512345

Because we are looking for a randomly, will it take a long time to find it?
Answer: No!
∙Theorem 1: There are p−12 n in x2≡n(modp) so that the equation has a solution
⇒Prove theorem 1: x2≡n(modp), if there are different numbers u, v, so that After they bring in x, the equation can be solved, then it is obvious that u2−v2|p is satisfied, so (u+v)(u−v)|p is satisfied, because
u2−v2|p so p cannot be A multiple of (u-v), so (u+v)|p, then the number of such number pairs existing in p is p−12
According to Theorem 1, the expectation of randomly finding a is 2.

Create a plural domain

It is said to be created, but in fact, there is no need to program it at all. It is said to be a plural domain just for the convenience of understanding.
In the commonly learned complex number field, there is an i, which satisfies i2=−1.
We also create a similar domain, because we need to take the square root of a2−n, and a2−n has a quadratic remainder that is not p, so we define ω=a2−n−−−−√. Then the current ω, like i, satisfies ω2=a2−n, so we define a new domain.

struct CN{
ll x,y;
CN friend operator *(CN x,CN y){
CN z;
z.x=(x.x*y.x%p+ x.y*y.y%p*w%p)%p;
z.y=(x.x*y.y%p+x.y*y.x%p)%p; return z;
}
}u,v;123456789123456789

We define operators just like normal complex number operations. You can find that z. The representation in this domain is similar to a normal complex number: a+bω

Get the answer

What we require is x2≡n(modp), the value of x
We now know After knowing a and ω, you can get the answer.
Answer=(a+ω)p+12
Really? real! But doesn't this answer consist of real and imaginary numbers?
According to Lagrange's theorem, it can be concluded that the coefficient of the imaginary number must be 0.

CN Cqsm(CN x,ll y){\\fast power of complex numbers CN z;z.x=1,z.y=0;\\pay attention to initialization while(y){ if(y&1)z=z*x;
a,u.y=1;//Why u.y is 1 - just use statistical coefficients in complex number statistics
u=Cqsm(u,(p+1)/2);
ll yi= u.x,er=p-u.x; if(yi>er)swap(yi,er); if(yi==er){ printf("%lld\n",yi);
} else{ printf(" %lld %lld\n",yi,er);
}12345678910111234567891011


Why are there two answers, such as 4√=±2, x2≡(p−x)2( modp) Obviously, because x2≡x2−2px+p2(modp) is disassembled and all p is removed, x2≡(p−x)2(modp).

Proof Principle

Then come up with some theorems for easy explanation.

Theorem

∙Theorem 2: (a+b)p≡ap+bp(modp)

⇒Prove Theorem 2: According to the binomial theorem:

(a+ b)p≡∑pi=0Cipap−ibi(modp)

≡∑pi=0p!(p−i)!i!ap−ibi(modp)

It can be found that only when i=0 or i= When p, the formula does not have p factors, so any factors with p in the middle can be omitted, so (a+b)p≡ap+bp(modp)

∙Theorem 3: ωp≡−ω(modp)
⇒Prove Theorem 3: ωp
=ωp−1∗ω
=(ω2)p−12∗ω
=(a2−n)p−12∗ω——Because ω2=a2− n
=−ω——Because it satisfies (a2−n)p−12=−1
∙Theorem 4: ap≡a(modp)
⇒Prove Theorem 3: ap according to Fermat’s Little Theorem
≡ap−1≡1(modp)
So ap≡a∗ap−1≡a(modp)

Derivation

Question: x2≡n(modp) solve for x
Cipolla: The real number of x≡(a+ω)p+12(modp)

Convert the formula directly:

(a+ω)p+12(modp)

≡((a +ω)p+1)12(modp)

≡((a+ω)p(a+ω))12(modp)
≡((ap+ωp)(a+ω))12( modp) According to Theorem 2
≡((a−ω)(a+ω))12(modp) According to Theorem 3 and Theorem 4
≡(a2−ω2)12(modp) According to Theorem 3 and Theorem 4
≡(a2−(a2−n))12(modp) satisfies ω2=a2−n
≡n12(modp)
So (a+ω)p+12≡n12≡n√(modp )
This is too much imagination! ! ! ! ! ! ! ! ! ! ! ! ! !

The above is the detailed content of Notes on Algorithms of Computer Programs. For more information, please follow other related articles on the PHP Chinese website!