| |||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||
А что он там сам нашел или не нашел — это не исторический факт.
, не помню подробностей. Он объясняет, что нужно умножить на что, потом сложить итд. Это не значит, что только эта конкретная задача с этим конкретным числом клеток его интересовала, конечно — нет, он объясняет читателю, как решать любую задачу такого рода.
Сунь Цзы объясняет, как, получив одно решение с помощью предложенных чисел, «упростить» его, отнимая 105, пока оно не станет маленьким — и действительно, 233 упрощается до 23. Но я не думаю, что он не знал, как действовать с другими делителями и остатками. Наоборот, я как раз пишу, что по-моему знал, потому что иначе непонятно, как он решил *эту* конкретную задачу.
НОУ ИНТУИТ | Лекция | Простые числа
Аннотация: Эта лекция имеет несколько целей: ввести простые числа и их приложения в криптографии, обсудить некоторые алгоритмы проверки простоты чисел и их эффективность, обсудить алгоритмы разложения на множители и их приложения в криптографии, описать китайскую теорему об остатках и ее приложения, ввести квадратичное сравнение, ввести возведение в степень по модулю и логарифмы.
Ключевые слова: криптография, составной объект, путь, делимое, решето Эратосфена, теорема Ферма, инверсия, алгоритм Евклида, теорема Эйлера, испытание, целое число, алгоритм, правильный ответ, битовые операции, псевдокод, криптографическая система, каноническое разложение, итеративность, криптосистема, криптоанализ, RSA, CRT, значение, остаток
Асимметрично-ключевая криптография, которую мы обсудим в лекциях 14-15, базируется на некоторых положениях теории чисел, включая теории, связанные с простыми числами, разложением на множители составных объектов в простые числа, модульном возведение в степень и логарифмах, квадратичных вычетах и китайской теореме об остатках. Эти проблемы будут рассмотрены здесь, в чтобы упростить понимание лекциии 14-15.
12.1. Простые числа
Асимметрично-ключевая криптография широко использует простые числа. Тема простых чисел — большая часть любой книги по теории чисел.
Эта лекция обсуждает только несколько понятий и фактов, чтобы открыть путь к лекциях 14-15.
Определение
Положительные целые числа могут быть разделены на три группы: число 1, простые числа и составные объекты, как это показано на рис. 12.1.
Рис. 12.1. Три группы положительных целых чисел
Положительное целое число — простое число тогда и только тогда, когда оно точно делимо без остатка на два целых числа — на 1 и на само себя. Составной объект — положительное целое число больше с чем двумя делителями.
Простое число делимо без остатка только на себя и 1.
Пример 12.1
Какое наименьшее простое число?
Решение
intuit.ru/2010/edi»>Наименьшее простое число — 2, оно делится без остатка на 2 (само на себя) и 1. Обратите внимание, что целое число 1 — не простое число согласно определению, потому что простое число должно быть делимо без остатка двумя различными целыми числами, не больше и не меньше. Целое число 1 делимо без остатка только на себя; поэтому 1 — это не простое число.Пример 12.2
Перечислите простые числа, меньшие, чем 10.
Решение
Есть четыре простых числа меньше чем 10: 2, 3 5 и 7. Интересно, что процент простых чисел в диапазоне 1-10 — 40%. С увеличением диапазона процент уменьшается.
Взаимно простые числа
Два положительных целых числа a и b являются взаимно простыми (coprime), если НОД (a, b) = 1, потому что число 1 является взаимно простым с любым целым числом.
Если p — простое число, тогда все числа от 1 до p–1 являются взаимно простыми к p. В
«Модульная арифметика»
мы обсуждали множество Zn*, чьи элементы — все числа, взаимно простые с n. Множество Z * является тем же самым, за исключением того, что модуль (p) — простое число.
Количество простых чисел
После того как понятие простых чисел было определено, естественно возникает вопрос: число простых чисел конечно или бесконечно? Возьмем число n. Сколько есть простых чисел меньших, чем это число, или равных n?
Число простых чисел
Число простых чисел бесконечно. Приведем нестрогое доказательство: предположим, что множество простых чисел конечно (ограничено), и пусть p — наибольшее простое число. Перемножим все простые числа, входящие в это множество, и получим результат . Целое число (P + 1) не может иметь простого делителя (p – наибольшее простое число).
Тогда этот делитель должен быть одним из множителей, входящих в P. Это значит, что q делит P. Если q также делит (P + 1), то q делит (P + 1) – P = 1. Единственное число, которое делит 1, — это сама 1, которая не является простым числом. Поэтому q должно быть большим, чем p, и ряд простых чисел не исчерпывается принятым конечным множеством.
Число простых чисел бесконечно.
Пример 12.3
Как тривиальный пример, предположим, что единственные простые числа находятся в множестве {2, 3, 5, 7, 11, 13, 17}. Здесь P = 510510 и P + 1 = 510511. Однако 510511 состоит из следующих простых чисел ; ни одно из этих простых чисел не было в первоначальном списке. Эти три простых числа больше, чем 17.
Число простых чисел, меньших n
Чтобы рассмотреть вторую возможность, введем функцию , которая определяет число простых чисел, меньших или равных n.
Ниже показаны значения этой функции для различного .
Но если n является очень большим, как мы можем вычислить ? Для ответа мы можем использовать только приближение, которое показано ниже:
Гаусс обнаружил верхний предел; Лагранж обнаружил нижний предел.
Пример 12.4
Найдите количество простых чисел, меньших, чем 1 000 000.
Решение
Приближение дает диапазон от 72 383 до 78 543. Фактическое число простых чисел — 78 498.
Проверка на простое число
Следующий вопрос, который приходит на ум: как мы можем определить для данного числа n, является ли оно простым числом? Мы должны проверить, делимо ли без остатка это число всеми простыми числами, меньшими, чем .
Мы знаем, что этот метод неэффективен, но он хорош для начала.
Пример 12.5
Действительно ли 97 — простое число?
Решение
Наибольшее ближайшее целое число — . Простые числа меньше чем 9 — 2, 3, 5 и 7. Проверим, делимо ли без остатка 97 любым из этих номеров. Ответ: не делимо, так что 97 — простое число.
Пример 12.6
Действительно ли 301 — простое число?
Решение
Наибольшее ближайшее целое число. Мы должны проверить 2, 3, 5, 7, 11, 13 и 17. Числа 2, 3 и 5 не делят 301, но 7 — делит. Поэтому 301 — не простое число.
Решето Эратосфена
Греческий математик Эратосфен изобрел метод, как найти все простые числа, меньшие, чем n.
Метод назван решетом Эратосфена. Предположим, что мы хотим найти все числа, меньшие, чем 100. Мы записываем все числа между 2 и 100. Поскольку , мы должны видеть, делим ли без остатка любой номер меньше чем 100 на числа 2, 3, 5 и 7. Таблица 12.1 показывает результат.
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
intuit.ru/2010/edi»>Процесс состоит в следующем:- Вычеркнуть все числа, делимые без остатка на 2 (кроме самого 2).
- Вычеркнуть все числа, делимые без остатка на 3 (кроме самого 3).
- Вычеркнуть все числа, делимые без остатка на 5 (кроме самого 5).
- Вычеркнуть все числа, делимые без остатка на 7 (кроме самого 7).
- Оставшиеся числа – простые.
Теорема об остатках и Теорема о множителях
Или: как избежать полиномиального длинного деления при нахождении множителей
Вы помните, как выполняли деление в арифметике?
«7, разделенные на 2 равных 3 с оставшейся 1 »
Каждая часть подразделения имеет названия:
, которая может быть Перезаписано как сумма:
.
Многочлены
Ну, мы также можем делить многочлены.
f(x) ÷ d(x) = q(x) с остатком r(x)
Но лучше записать это в виде суммы следующим образом:
Как в этом примере, используя Polynomial Long Деление:
Пример: 2x
2 −5x−1 разделить на x−3- f(x) равно 2x 2 −5x−1
- d(x) равно x−3
После деления получаем ответ 2x+1, но есть остаток 2.
- q(x) равно 2x+1
- г(х) равно 2
В стиле f(x) = d(x)·q(x) + r(x) мы можем написать:
2x 2 −5x−1 = (x−3)(2x+1) + 2
Но вам нужно знать еще одну вещь:
Степень r(x) всегда меньше, чем d(x)
Скажем, мы делим на многочлен степени 1 (например, «x−3» ) остаток будет иметь степень 0 (другими словами, константа, например «4»).
Мы будем использовать эту идею в «Теорема об остатке»:
Теорема об остатке
Когда мы делим f(x) на простой многочлен x−c, мы получаем:
f(x) = (x−c)·q(x) + r(x)
x−c равен степени 1 , поэтому r(x) должно иметь степень 0 , так что это просто некоторая константа r :
f(x) = (x−c)·q(x) + r
Теперь посмотрим, что произойдет, когда мы имеем x, равный c:
f(c) = (c−c)·q(c) + r
f(c) =(0)·q(c) + r
f(c) = r
Итак, мы получаем:
Теорема об остатке:
Когда мы делим многочлен f(x) на x−c, получается остаток f(c)
Таким образом, чтобы найти остаток после деления на x-c, нам не нужно делать никакого деления:
Просто вычислить f( в).
Проверим это на практике:
Пример: Остаток после 2x
2 −5x−1 делится на x−3(Наш пример сверху)
Нам не нужно делить на ( x−3) … просто вычислить f(3) :
2(3) 2 −5(3)−1 = 2×9−5×3−1
= 18−15−1
= 2
И это остаток, который мы получили из наших расчетов выше.
Нам вообще не нужно было длинное деление!
Пример: Остаток после 2x
2 −5x−1 делится на x−5Тот же пример, что и выше, но на этот раз мы делим на «x−5»
«c» равно 5, поэтому давайте проверим f(5):
2(5) 2 −5(5)−1 = 2×25−5×5−1
= 50−25−1
= 24
Остаток равен 24
Еще раз… Нам не нужно было выполнять длинное деление, чтобы найти это.
Факторная теорема
Теперь…
Что, если мы вычислим f(c) и получим 0 ?
… это означает, что остаток равен 0 , и .
..
… (x−c) должен быть множителем многочлена!
Мы видим это при делении целых чисел. Например, 60 ÷ 20 = 3 без остатка. Таким образом, 20 должно быть в 60 раз больше.
Пример: x
2 −3x−4f(4) = (4) 2 −3(4)−4 = 16−12−4 = 0
, поэтому (x−4) должно быть множитель x 2 −3x−4
Итак, мы имеем:
Теорема о факторах:
Когда f(c)=0, тогда x−c является множителем f(x)
И наоборот:
Если x−c является фактором f(x), то f(c)=0
Почему это полезно?
Знание того, что x−c является множителем, равнозначно знанию того, что c является корнем (и наоборот).
Множитель «x-c» и корень «c» — это одно и то же
Знаем одно, и мы знаем другое
Во-первых, это означает, что мы можем быстро проверить, если (x-c ) является множителем полинома.
Пример: Найдите множители 2x
3 −x 2 −7x+2 Многочлен имеет степень 3, и его может быть трудно решить.
Итак, сначала построим график:
Кривая пересекает ось x в трех точках, и одна из них может быть 2 . Легко проверить:
f(2) = 2(2) 3 −(2) 2 −7(2)+2
= 16−4−14+2
= 0
Да! f(2)=0 , значит, мы нашли корень и множитель.
Итак, (x−2) должно быть в 2 раза больше 3 −x 2 −7x+2
Как насчет того, где оно пересекается около −1,8 ?
f(−1,8) = 2(−1,8) 3 −(−1,8) 2 −7(−1,8)+2
= −11,664−3,24+12,6+2
= −0,304
Нет, (x+1,8) не является фактором. Мы могли бы попробовать другие значения поблизости и, возможно, нам повезет.
Но, по крайней мере, мы знаем, что (x−2) — это множитель, поэтому давайте воспользуемся полиномиальным делением: 2
2x 3 −4x 2
3x 2 −7x
3x 2 −6−x
x 0133 −x+2
0
Как и ожидалось, остаток равен нулю.
Более того, у нас осталось квадратное уравнение 2x 2 +3x−1 , которое легко решить.
Его корни равны -1,78… и 0,28…, поэтому окончательный результат:
2x 3 -x 2 -7x+2 = (x-2)(x+1,78… )(x−0,28…)
Мы смогли решить сложный многочлен.
Резюме
Теорема об остатке:
- При делении многочлена f(x) на x−c остаток равен f(c)
Факторная теорема:
- Когда f(c)=0, тогда x−c является множителем f(x)
- Когда x−c является коэффициентом f(x), тогда f(c)=0
Задающие вопросы:
1
2
3
4
5
6
Теорема об остатках | Purplemath
Purplemath
Теорема об остатках полезна для вычисления многочленов при данном значении x , хотя может показаться, что это не так, по крайней мере, на первый взгляд. Это потому, что инструмент представлен в виде теоремы с доказательством, и вы, вероятно, не чувствуете себя готовым к доказательствам на данном этапе вашего обучения.
К счастью, вам не нужно понимать доказательство теоремы; вам просто нужно понять, как использовать Теорема.
Содержание продолжается ниже
MathHelp.com
Теорема об остатках начинается с безымянного многочлена p ( x ), где « p ( x )» просто означает «некоторый многочлен p , переменная которого равна x ». Тогда Теорема говорит о делении этого полинома на некоторый линейный множитель x — a , где a — просто некоторое число.
Затем, в результате длинного полиномиального деления, вы получите некоторый полиномиальный ответ q ( x ), где « q » означает «множественный полином»; и немного остатка r ( x ), r означает «остаток после деления». Этот остаток может быть правильным многочленом, содержащим переменную, или может быть просто числом.
В качестве конкретного примера P , A , Q и R , давайте посмотрим на полиномиальные P ( x ) = x ( x ) = x ( x ) = x ( x ) = x ( x ) = x ( x ).
− 6, и давайте разделим на линейный коэффициент x − 4 (так что a = 4):
Таким образом, мы получаем коэффициент Q ( x ) = x 2 + 4 x + 9 сверху, с остатком R ( x ) = 30655 = 30655 = 30655 = 30655 = 30655 = 30655 = 30655) = 30655) = 30655) = 30655). Еще когда вы изучали деление обычных чисел на длинные, вы узнали, что ваш остаток (если он был) должен быть меньше того, на что вы делили. В терминах полинома, поскольку мы делим на линейный множитель (то есть множитель, в котором степень на x представляет собой просто понятную «1»), то остаток должен быть постоянным значением. То есть, когда вы делите любой многочлен на линейный делитель » x — a «, ваш остаток будет и должен быть просто некоторым простым числом.
Теорема об остатках, таким образом, указывает на связь между делением и умножением. Например, поскольку 12 ÷ 3 = 4, то 4 × 3 = 12. Если ваше деление заканчивается с ненулевым остатком, то, когда вы пойдете другим путем и выполните умножение, вам нужно будет добавить этот остаток обратно.
Например, так как:
13 ÷ 5 = 2 R 3
…тогда, вернувшись обратно с умножением, вы получите:
13 = 5 × 2 + 3
Этот процесс работает так же с многочленами. That is:
If:
p ( x ) ÷ ( x − a ) = q ( x )
with remainder r ( x )
… тогда:
P ( x ) = ( x — A ) Q ( x ) + R ( x ) + R ( x ) + R ( x ) + R ( x ) + R ( x ). — тогда» является «алгоритмом деления многочленов». Но этот алгоритм является основой для теоремы об остатках.) 93 — 7 x — 6) ÷ ( x — 4) = x 2 + 4 x +
с оставшимся 30
… Тогда:
55. x 6 3
… Тогда: 555566 40005 … Тогда: 55566 3 . 55566
.. Тогда:
5566
… Тогда:
5. — 7 х — 6 = ( х — 4) ( х 2 + 4 х + 9) + 30
К чему весь этот утомительный повтор деления? Потому что для полиномов деление на линейный коэффициент x — a и нахождение числового остатка дает нам значение полинома при оценке в x = a ; другими словами, теорема дает нам сокращенный способ вычисления многочленов.
Алгоритм деления для многочленов говорит, что мы можем переформулировать многочлен через его делитель x — a , его частное и остаток. После переформатирования таким образом мы можем вычислить полином как x = a . Но когда x = a , то делитель x — a равен a − a , что равно нулю! Таким образом, оценка полинома в x = A дает нам следующий результат:
P ( A ) = ( A — A ) A — A ).
( и )
= (0) q ( a ) + r ( a )
= 0 + r ( a )
= r ( a )
И помните, что остаточный член r ( a ) это просто число! Таким образом, значение многочлена p ( x ) при x = a равно остатку, полученному при делении этого многочлена p ( x ) на x . .
Что говорит теорема об остатках?
Теорема об остатках говорит нам, что для вычисления многочлена p ( x ) в некотором числе x = a , мы можем вместо этого разделить на линейное выражение x — a . Остаток, r ( a ), дает значение многочлена x = a .
В нашем конкретном примере:
p (4) = (4 − 4)((4) 2 + 4(4) + 9) + 30
= (0)(16 + 16 + 9) + 30
= 0 + 30
= 30
Но вы должны подумать: хорошо, хорошо; значение полинома p ( x ) при x = a равно r ( a ) при делении на x 5 − 9035 , длинное деление каждый раз, когда вы должны оценить многочлен при заданном значении x ?!? Ты прав; выполнение длинного деления каждый раз действительно было бы излишним.
К счастью, это не то, чего они на самом деле хотят от вас.
При делении на линейный коэффициент нет необходимости использовать длинное полиномиальное деление; вместо этого вы можете использовать синтетическое деление, которое намного быстрее. В нашем конкретном примере мы получили бы:
Обратите внимание, что последняя запись в нижней строке равна 30, остаток от деления в большую сторону (как и ожидалось), а также значение p ( x ) = x 3 — 7 x — 6 при x = 4. И , что является точкой теоремы об остатках:
В чем смысл теоремы об остатках?
Суть теоремы об остатках состоит в том, что существует более простой и быстрый способ вычисления многочлена p ( x ) при данном значении x , и этот более простой способ состоит в том, чтобы не вычислять p ( x ), но вместо этого выполнять синтетическое деление с тем же значением x .
Последнее число в результате синтетического деления — это искомое значение, являющееся оценочным значением полинома.
Какой пример использования теоремы об остатках?
- Используйте теорему оставшейся для оценки F ( x ) = 6 x 3 — 5 x 2 +4 x a 5. 3. 3,355556.
Во-первых, несмотря на то, что теорема об остатках относится к многочлену, к делению в длинное число и к переформулированию многочлена через частное, делитель и остаток, бла-бла-бла, на самом деле я не это имел в виду. делать. Вместо этого я должен выполнять синтетическое деление, используя «3» в качестве делителя:
Поскольку остаток (последняя запись в нижней строке) равен 112, то теорема об остатках утверждает, что:
f (3) = 112.
- Используя теорему об остатках, найдите значение f (−5), для f ( x ) = 3 x 4 + 2 x 3 + 4 x .
Мне нужно выполнить синтетическое деление, не забывая ставить нули в степенях x , которые не входят в многочлен:
Поскольку остаток равен 1605, то, благодаря теореме об остатках, я знаю, что:
f (−5) = 1605.
, после деления равен нулю? Что это значит?
Ну, во-первых, это означает, что полином равен нулю при любом значении x , которое вы использовали при синтетическом делении. Но, во-вторых, там сказано, что (интересного) остатка нет; остаток от нуля означает, что вы разделили на x — на и ничего не осталось, поэтому x — на должно быть множителем многочлена.
- Используйте теорему оставшейся, чтобы определить, является ли x = 2 — ноль F ( x ) = 3 x 7 — x 9 40041+55555555555555555555555555595555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555. − 5 x 2 − − 4
− 5 x 2 − − 4Для x = 2 должно быть нулем f ( x ), то f (2) должно равняться нулю. В контексте теоремы об остатках это означает, что мой остаток при делении на x = 2 должен быть равен нулю. Вот мое деление:
Я вижу, что остаток не равен нулю; на самом деле это 360. Это говорит мне о том, что:
x = 2 не является нулем f ( x )
- Используйте теорему об остатках, чтобы определить, является ли x решение х 6 +5 x 5 +5 x 4 +5 x 3 +2 x 2 –15 x 2 –1 x 2 +2 x 2 .
For x = −4 to be a solution of f ( x ) = x 6 + 5 x 5 + 5 x 4 + 5 x 3 + 2 x 2 — 10 x — 8 = 0, должно быть f (−4) = 0.