{"id":23674,"date":"2023-05-05T07:14:59","date_gmt":"2023-05-05T07:14:59","guid":{"rendered":"https:\/\/www.booksofall.com\/pl\/?post_type=product&p=23674"},"modified":"2023-05-05T07:14:59","modified_gmt":"2023-05-05T07:14:59","slug":"the-joy-of-cryptography","status":"publish","type":"product","link":"https:\/\/www.booksofall.com\/pl\/the-joy-of-cryptography\/","title":{"rendered":"The Joy of Cryptography"},"content":{"rendered":"

0 – Review of Concepts & Notation<\/h2>\n

The material in this section is meant as a review. Despite that, many students report that they \u001bnd this review useful for the rest of the book.<\/p>\n

0.1 Logs & Exponents<\/h4>\n

You probably learned (and then forgot) these identities in middle school or high school:<\/p>\n

\"\"<\/p>\n

Well, it\u2019s time to get reacquainted with them again.<\/p>\n

In particular, never ever write (xa)(xb ) = xab . If you write this, your cryptography instructor will realize that life is too short, immediately resign from teaching, and join a traveling circus. But not before changing your grade in the course to a zero.<\/p>\n

0.2 Modular Arithmetic<\/h4>\n

We write the set of integers as:<\/p>\n

\"\"<\/p>\n

and the set of natural numbers<\/a> (nonnegative integers) as:<\/p>\n

\"\"<\/p>\n

Note that 0 is considered a natural number.<\/p>\n

Definition 0.1
\n<\/strong> For x ,n \u2208 Z, we say that n divides x (or x is a multiple of n), and write n | x , if there exists an integer k such that x = kn.<\/p>\n

Remember that the definitions apply to both positive and negative numbers (and to zero). We generally only care about this definition in the case where n is positive, but it is common to consider both positive and negative values of x .<\/p>\n

Example<\/strong>
\n7 divides 84 because we can write 84 = 12 \u00b7 7.
\n7 divides 0 because we can write 0 = 0 \u00b7 7.
\n7 divides \u221277 because we can write \u221277 = (\u221211) \u00b7 7.
\n\u22127 divides 42 because we can write 42 = (\u22126) \u00b7 (\u22127).
\n1 divides every integer (so does \u22121). The only integer that 0 divides is itself.<\/p>\n

Definition 0.2 <\/strong>(% operator)<\/p>\n

Let n be a positive integer, and let a be any integer. The expression a % n (usually read as \u201ca mod n\u201d) represents the remainder after dividing a by n. More formally, a % n is the unique r \u2208 {0, . . . ,n \u2212 1} such that n | (a \u2212 r ).1<\/p>\n

Pay special attention to the fact that a %n is always a nonnegative number, even if a is negative. A good way to remember how this works is:<\/p>\n

a is (a % n) more than a multiple of n. <\/span><\/p>\n

Example
\n21 % 7 = 0 because 21 = 3 \u00b7 7 + 0.
\n20 % 7 = 6 because 20 = 2 \u00b7 7 + 6.
\n\u221220 % 7 = 1 because \u221220 = (\u22123) \u00b7 7 + 1. (\u221220 is one more than a multiple of 7.)
\n\u22121 % 7 = 6 because \u22121 = (\u22121) \u00b7 7 + 6.<\/p>\n

Unfortunately, some programming languages<\/a> define % for negative numbers as (\u2212a)% n = \u2212(a % n), so they would define \u221220 % 7 to be \u2212(20 % 7) = \u22126. This is madness, and it\u2019s about time we stood up to these programming language designers and smashed them over the head with some mathematical truth! For now, if you are using some programming environment to play around with the concepts in the class, be sure to check whether it defines % in the correct way.<\/p>\n

Definition 0.3<\/strong> (Zn)
\nFor positive n, we write Zn def = {0, . . . ,n \u2212 1} to denote the set of integers modulo n. These are the possible remainders<\/a> one obtains by dividing by n.2<\/p>\n

Definition 0.4<\/strong>(\u2261n)
\nFor positive n, we say that integers a and b are congruent modulo<\/a> n, and write a \u2261n b, if n | (a \u2212 b). An alternative definition is that a \u2261n b if and only if a % n = b % n.<\/p>\n

You\u2019ll be in a better position to succeed in this class if you can understand the (subtle) distinction between a \u2261n b and a = b % n:<\/p>\n

a \u2261n b:
\nIn this expression, a and b can be integers of any size, and any sign. The left and right side have a certain relationship modulo n.<\/p>\n

a = b % n:
\nThis expression says that two integers are equal. The \u201c=\u201d rather than \u201c\u2261\u201d is your clue that the expression refers to equality over the integers. \u201cb % n\u201d on the right-hand side is an operation performed on two integers that returns an integer result. The result of b % n is an integer in the range {0, . . . ,n \u2212 1}.<\/p>\n

Example<\/strong>
\n\u201c99 \u226110 19\u201d is true. Applying the definition, you can see that 10 divides 99 \u2212 19.
\nOn the other hand, \u201c99 = 19 % 10\u201d is false. The right-hand side evaluates to the integer 9, but 99 and 9 are different integers.<\/p>\n

In short, expressions like a \u2261n b make sense for any a,b (including negative!), but expressions like a = b % n make sense only if a \u2208 Zn .<\/p>\n","protected":false},"excerpt":{"rendered":"