程序员必修：数学原理与编程应用（初稿）

30 浏览量更新于2024-07-14 收藏 1.75MB PDF 举报

《编程数学（早期草稿）》是一本由Dennis Yurichev撰写，针对程序员的数学指南，发布于2020年9月22日。该书旨在将数学理论与编程实践相结合，帮助程序员更好地理解和应用数学概念，特别是在加密技术如RSA算法中的关键作用。以下是书中的一些主要知识点： 1. **素数与合数**：章节1集中探讨了素数的基本概念，如如何通过分解整数因子来理解它们，以及它们在构建安全算法如RSA中的重要性。作者举例说明了使用复合数作为容器来实现某些计算任务的方法。 2. **互质数（Coprime Numbers）**：这部分介绍了两个或多个整数之间的相互关系，当它们的最大公约数为1时，称为互质，这对于生成密钥对和理解模运算中的性质至关重要。 3. **半素数（Semiprimes）**：半素数是两个素数的乘积，它们在RSA算法中的安全性分析中有所体现。 4. **RSA算法详解**：这一部分深入讲解了RSA算法的工作原理，包括费马小定理、欧拉函数、欧拉定理等数学工具。作者通过逐步示例解释了如何选择密钥，以及如何利用这些数学原理进行加解密操作。 5. **RSA的安全性和破解**：讨论了如何通过特定的数学攻击（如小数定理的逆用）来尝试破解RSA，以及实际应用中为了增强安全性采取的措施。 6. **模运算（Modular Arithmetic）**：这是RSA算法的基础，包括快速介绍、CPU上的实现、余数计算、随机数生成，以及模逆和线性同余方程组的求解。 7. **概率论**：在密码学中，概率论被用于评估算法的安全性，如文本字符串中出现特定模式的概率，这在密码分析和哈希函数的研究中非常重要。这本书不仅提供数学理论，还注重实践应用，让程序员能够将数学概念转化为实际编程技能。通过学习和理解这些内容，程序员可以提升他们在信息安全、算法设计和性能优化等方面的能力。

Ver 4 - new

Public key creation time - Tue Jun 30 02:08:38 EEST 2015

Pub alg - RSA Encrypt or Sign(pub 1)

RSA n(4096 bits ) - ...

RSA e(17 bits ) - ...

...

Old: Secret Subkey Packet(tag 7) (1816 bytes)

Ver 4 - new

Public key creation time - Tue Jun 30 02:08:38 EEST 2015

Pub alg - RSA Encrypt or Sign(pub 1)

RSA n(4096 bits ) - ...

RSA e(17 bits ) - ...

RSA d(4093 bits ) - ...

RSA p(2048 bits ) - ...

RSA q(2048 bits ) - ...

RSA u(2048 bits ) - ...

Checksum - 94 53

...

... it has all variables stored in the file, including d, p and q.

1.4.8 The RSA signature

It’s possible to sign a message to publish it, so everyone can check the signature. For example, The Publisher wants to

sign the message (let’s say, 456). Then he/she uses d exponent to compute signature:

Listing 1.26: Wolfram Mathematica

In []:= signed = Mod [456^d, n]

Out []= 2282

Now he publishes n = pq (3827), e (17 in our example), the message (456) and the signature (2282). Some other

Consumers can verify its signature using e exponent and n:

Listing 1.27: Wolfram Mathematica

In []:= Mod [2282^e, n]

Out []= 456

... this is another illustration that e and d exponents are complement each other, by modulo totient = (p −1)(q −1).

The signature can only be generated with the access to p and q values, but it can be verified using product (n = pq)

value.

1.4.9 Hybrid cryptosystem

RSA is slow, because exponentiation is slow and exponentiation by modulo is also slow. Perhaps, this is the reason

why it was considered impractical by GCHQ when Cliord Cocks first came with this idea in 1970s. So in practice, if

The Sender wants to encrypt some big piece of data to The Receiver, a random number is generated, which is used as

a key for symmetrical cryptosystem like DES or AES. The piece of data is encrypted by the random key. The key is then

encrypted by RSA to The Receiver and destroyed. The Receiver recovers the random key using RSA and decrypts all the

data using DES or AES.

Chapter 2

Modulo arithmetics

2.1 Quick introduction into modular arithmetic

Modular arithmetic is an environment where all values are limited by some number (modulo). Many textbooks has

clock as example. Let’s imagine old mechanical analog clock. There hour hand points to one of number in bounds of

0..11 (zero is usually shown as 12). What hour will be if to sum up 10 hours (no matter, AM or PM) and 4 hours? 10+4 is

14 or 2 by modulo 12. Naively you can just sum up numbers and subtract modulo base (12) as long as it’s possible.

Modern digital watch shows time in 24 hours format, so hour there is a variable in modulo base 24. But minutes and

seconds are in modulo 60 (let’s forget about leap seconds for now).

Another example is US imperial system of measurement: human height is measured in feets and inches. There are 12

inches in feet, so when you sum up some lengths, you increase feet variable each time you’ve got more than 12 inches.

Another example I would recall is password cracking utilities. Oen, characters set is defined in such utilities. And

when you set all Latin characters plus numbers, you’ve got 26+10=36 characters in total. If you brute-forcing a 6-

characters password, you’ve got 6 variables, each is limited by 36. And when you increase last variable, it happens in

modular arithmetic rules: if you got 36, set last variable to 0 and increase penultimate one. If it’s also 36, do the same.

If the very first variable is 36, then stop. Modular arithmetic may be very helpful when you write multi-threading (or

distributed) password cracking utility and you need to slice all passwords space by even parts.

This is yet another application of modulo arithmetic, which many of us encountered in childhood.

Given a counting rhyme, like:

Eeny , meeny , miny , moe ,

Catch a tiger by the toe.

If he hollers , let him go ,

Eeny , meeny , miny , moe.

( https://en.wikipedia.org/wiki/Eeny,_meeny,_miny,_moe )

... predict, who will be choosen.

If I’m correct, that rhyme has 16 items, and if a group of kids constist of, say, 5 kids, who will be choosen? 16 mod 5 = 1,

meaning, the next kid aer the one at whom counting had begun.

Or 7 kids, 16 mod 7 = 2. Count two kids aer the first one.

If you can calculate this quickly, you can probably get an advantage by choosing a better place within a circle...

Now let’s recall old mechanical counters which were widespread in pre-digital era:

Figure 2.1: The picture was stolen from http://www.featurepics.com/ — sorry for that!

This counter has 6 wheels, so it can count from 0 to 10

− 1 or 999999. When you have 999999 and you increase the

counter, it will resetting to 000000— this situation is usually understood by engineers and computer programmers as

overflow. And if you have 000000 and you decrease it, the counter will show you 999999. This situation is oen called

“wrap around”. See also: http://en.wikipedia.org/wiki/Integer_overflow.

2.1.1 Modular arithmetic on CPUs

The reason I talk about mechanical counter is that CPU registers acting in the very same way, because this is, perhaps,

simplest possible and eicient way to compute using integer numbers.

This implies that almost all operations on integer values on your CPU is happens by modulo 2

or 2

depending on

your CPU. For example, you can sum up 0x87654321 and 0xDEADBABA, which resulting in 0x16612FDDB. This value is

too big for 32-bit register, so only 0x6612FDDB is stored, and leading 1 is dropped. If you will multiply these two num-

bers, the actual result it 0x75C5B266EDA5BFFA, which is also too big, so only low 32-bit part is stored into destination

may argue: when sum is too big for register, CF (carry flag) is set, and it can be used aer. And there is x86 MUL instruc-

tion which in fact produces 64-bit result in 32-bit environment (in EDX:EAX registers pair). That’s true, but observing

just 32-bit registers, this is exactly environment of modulo with base 2

Now that leads to a surprising consequence: almost every result of arithmetic operation stored in general purpose reg-

ister of 32-bit CPU is in fact remainder of division operation: result is always divided by 2

and remainder is le in reg-

ister. For example, 0x16612FDDB is too large for storage, and it’s divided by 2

(or 0x100000000). The result of division

(quotient) is 1 (which is dropped) and remainder is 0x6612FDDB (which is stored as a result). 0x75C5B266EDA5BFFA

divided by 2

(0x100000000) produces 0x75C5B266 as a result of division (quotient) and 0xEDA5BFFA as a remainder,

the latter is stored.

And if your code is 32-bit one in 64-bit environment, CPU registers are bigger, so the whole result can be stored there,

but high half is hidden behind the scenes – because no 32-bit code can access it.

points to the same string buer containing the result of the second calculation. As a solution, it’s possible to allo-

cate/deallocate string buer each time, but more hackish way is to have several buers (4 are here) and fill the next

each time. The bufno variable here is a buer counter in 0..3 range. Its value increments each time, and its value is

also always kept in limits by AND operation (3 & ++bufno).

The author of this piece of code (seemingly Linus Torvalds himself) went even further and forgot (?) to initialize bufno

counter variable, which will have randomgarbage at the function start. Indeed: no matter, which buer we are starting

each time! This can be mistake which isn’t aect correctness of the code, or maybe this is le so intentionally – I don’t

know.

2.1.3 Getting random numbers

When you write some kind of videogame, you need random numbers, and the standard C/C++ rand() function gives

you them in 0..0x7FFF range (MSVC) or in 0..0x7FFFFFFF range (GCC). And when you need a random number in 0..10

range, the common way to do it is:

X_coord_of_something_spawned_somewhere =rand () % 10;

Y_coord_of_something_spawned_somewhere =rand () % 10;

No matter what compiler do you use, you can think about it as 10 is subtraced from rand() result, as long as there is

still a number bigger than 10. Hence, result is remainder of division of rand() result by 10.

One nasty consequence is that neither 0x8000 nor 0x80000000 cannot be divided by 10 evenly, so you’ll get some

numbers slightly more oen than others.

I tried to calculate in Mathematica. Here is what you get if you write <i>rand()

In []:= Counts[Map[ Mod[#, 3] &, Range[0, 16^^8000 - 1]]]

Out []= <|0 -> 10923, 1 -> 10923 , 2 -> 10922| >

So a number 2 appers slightly seldom than others.

Here is a result for rand() % 10:

In []:= Counts[Map[ Mod[#, 10] &, Range [0, 16^^8000 - 1]]]

Out []= <|0 -> 3277 , 1 -> 3277, 2 -> 3277, 3 -> 3277 , 4 -> 3277,

5 -> 3277, 6 -> 3277 , 7 -> 3277, 8 -> 3276 , 9 -> 3276| >

Numbers 8 and 9 appears slightly seldom (3276 against 3277).

Here is a result for rand() % 100:

In []:= Counts[Map[ Mod[#, 100] &, Range[0, 16^^8000 - 1]]]

Out []= <|0 -> 328, 1 -> 328, 2 -> 328, 3 -> 328, 4 -> 328, 5 -> 328,

6 -> 328 , 7 -> 328 , 8 -> 328 , 9 -> 328 , 10 -> 328, 11 -> 328,

12 -> 328, 13 -> 328, 14 -> 328 , 15 -> 328 , 16 -> 328, 17 -> 328,

18 -> 328, 19 -> 328, 20 -> 328 , 21 -> 328 , 22 -> 328, 23 -> 328,

24 -> 328, 25 -> 328, 26 -> 328 , 27 -> 328 , 28 -> 328, 29 -> 328,

30 -> 328, 31 -> 328, 32 -> 328 , 33 -> 328 , 34 -> 328, 35 -> 328,

36 -> 328, 37 -> 328, 38 -> 328 , 39 -> 328 , 40 -> 328, 41 -> 328,

42 -> 328, 43 -> 328, 44 -> 328 , 45 -> 328 , 46 -> 328, 47 -> 328,

48 -> 328, 49 -> 328, 50 -> 328 , 51 -> 328 , 52 -> 328, 53 -> 328,

54 -> 328, 55 -> 328, 56 -> 328 , 57 -> 328 , 58 -> 328, 59 -> 328,

60 -> 328, 61 -> 328, 62 -> 328 , 63 -> 328 , 64 -> 328, 65 -> 328,

剩余122页未读，继续阅读

weixin_38538381

粉丝: 6
资源: 907

程序员必修：数学原理与编程应用（初稿）

程序员的刷题软件-Math-for-Programmers:本书的源代码，程序员的数学

mathematics-for-machine-learning-solutions.pdf

Introduction to Mathematics for Game Development - James Cowley (June 23, 2016)-计算机科学

Mathematics for Computer Science (2012)-计算机科学

Mathematics-for-Machine-Learning-Linear-Algebra

Mathematics-for-Machine-Learning-Pre-Class-assignment-3-Matrix-Scratch

Fundamentals-of-Mathematics-Trigonometry-for-JEE-Main-and-Advanced

Discrete-Mathematics-for-Computer-Science

discrete-mathematics-for-computer-scientists

Mathematics-for-Machine-Learning-Coursera:我对Coursera作业的回答

最新资源