|
👍 +1 👎 |
Задача маткрипто олимпиадыЧисло 201071131 является произведением двух простых чисел p и q , а количество натуральных чисел, меньших заданного числа и взаимно простых с ним, равно 201041064. Найти p,q/
|
|
👍 +3 👎 |
http://ru.wikipedia.org/wiki/Функция_Эйлера
Поскольку функция Эйлера для заданного числа четная, легко найти её разложение не множители, и отсюда найти p и q. |
|
👍 −1 👎 |
Извините что вмешиваюсь, но на самом деле трудоемко найти разложение на множители числа 201041064=7*8*9*398891, а число 398891=239*1669 (вручную считать очень долго, а машинный перебор в задаче вряд ли разрешен).
|
|
👍 +2 👎 |
Учиться, учиться и еще раз учиться. Раньше МВТУ называли- высшее ремесленное училище.
|
|
👍 −1 👎 |
Да я в курсе, только Вы это к чему?
|
|
👍 −2 👎 |
Разложение числа на множители здесь вообще не нужно. Зачем Вы это говорили??????Тем более, что множители 8 и 9 не простые числа.
Это задача для школьников , стремящихся поступить в ИКСИ ФСБ России. Для школьников. А Вы себя именуете математиком в компьютерной безопасности. |
|
👍 −2 👎 |
Я в курсе, и это был мой ответ Марии Александровне, если я правильно поняла, она предложила разложить на множители.Или нет?Может я не так ее поняла?
|
|
👍 +1 👎 |
Мария Александровна квалифицировано увидела , что второе число в условии задачи по определению есть функция Эйлера и для данного конкретного случая n=pq эту функцию Эйлера можно разложить в произведение двух множителей, а именно: (p-1)(q-1).
|
|
👍 −1 👎 |
Значит я ее неправильно поняла, прошу прощения, я решила что Мария Александровна предложила разложить само число 201041064, почему я и указала на нецелесообразность такого подхода.
|
|
👍 0 👎 |
Мне интересно, у Вас на первом курсе на специальности "Информационная безопасность" был предмет "Высшая арифметика". ???Без этого предмета нельзя стать спецом в этой области. Сейчас почти во всех ВУЗах модно иметь такую специальность. При СССР во всей стране с трудом можно было найти сотню ребят, способных учиться по этой специальности.
|
|
👍 0 👎 |
У нас этот предмет назывался просто "Информатика" (не путать с программированием и технологией программирования). И да, мы изучали и функцию Эйлера, и много еще чего. Может Вас еще что-то интересует, спрашивайте, я расскажу
|
|
👍 −2 👎 |
Итак, арифметики у Вас не было. А дискретная математика была??? А а абстрактная алгебра была??? Кольца, поля Галуа??? Модульное гаммирование??
|
|
👍 0 👎 |
Дискретка была (предмет не кафедральный), доп.главы дискретки были (уже кафедральный предмет), так же как и тервер (не кафедральный) и доп.главы (кафедральный), еще кафедральные были комбинаторика, мат.логика и теория алгоритмов, теория групп, полей, колец(среди этих курсов теоремы арифметики изучаются, но в отдельный предмет не выделяется), группы и поля мы и сейчас изучаем, нам читают курс "Алгебраические системы". Ничего, связанного с криптографией и шифрованием (а модульное гаммирование я так понимаю уже близко к ним) нам пока еще не читали, это еще только впереди.
|
|
👍 −1 👎 |
Все, последний вопрос, мне просто любопытно, поскольку мне приходится сталкиваться с подготовкой специалистов в этой области в разных ВУЗах. Я сейчас хочу дать Вам маленькую арифметическую задачу, связанную сj всей этой тематикой. Не потому, чтобы именно Вас проверить. а вообще. Ибо только задачи выявляют понимание
Вычислить 3/7+1/3 (mod 17). |
|
👍 +1 👎 |
Рассмотрим 3/7. Деление на 7 эквивалентно умножению на обратный элемент семи в поле Z17.Этот обратный элемент = 5(т.к. 5*7 = 35 = 1mod17).Значит 3/7 = 3*5=15.Далее 1/3, ищем обратный элемент для 3, это 6 (т.к. 3*6 =18 = 1mod17). Значит 1/3 = 1*6 = 6.И окончательно (15+6)mod17 = 4mod17.
|
|
👍 +1 👎 |
Сложно Вас учили. Гораздо проще: решить сравнение 21x=16(mod17), отсюда х=4(mod17). 21 и 16 берутся от обычного сложения исходных дробей.
|
|
👍 −1 👎 |
Тяжело в учении, легко в бою. А уравнения вида ax=b mod c нас учили решать в этом семестре.
|
|
👍 0 👎 |
Марина, тогда Вам надо обратить внимание на новую криптозадачу(олимпиадную для школьников), представленную опять же Смолиным Игорем/
|
|
👍 +1 👎 |
Чтобы найти два числа, мне надо два уравнения. Пока мне не очень ясно , какие это уравнения, хотя одно из условия задачи вытекает. Как из функции Эйлера сделать уравнение?
|
|
👍 0 👎 |
p+q = p*q — (p-1)*(q-1) + 1 = 201071131 — 201041064 + 1 = 30068
Таким образом 'p' является корнем ур-я p^2 — 30068p + 201071131 = 0, корни которого 15064+-4995. |
|
👍 +1 👎 |
Функция Эйлера в данном случае есть (q-1)(p-1) и потому эти числа являются корнями системы pq= 201071131
(p-1)(q-1)=201071 Данная система конечно же сводится к решению квадратного уравнения х^2 -30068х+201071131=0. Только корни этого уравнения p=10039 и q=20029 |
|
👍 −1 👎 |
Я так понимаю, Марк Михайлович имел в виду корни 15064+4995=20029 и 15064-4995=10039, просто записал их в одну строчку через +/- ...
|
|
👍 −1 👎 |
Ошибка есть ошибка. Доказывайте на ЕГЭ, что Вы описались. Я,например, половину времени с учениками трачу на воспитание внимательности. Приходится применять специально ( не мною) разработанные методы. Ведь и родителям результат в виде баллов надо.
|
|
👍 −1 👎 |
Я все свои ЕГЭ уже давно сдала, а описка находится в середине задачи и не приводит к неправильному ответу, уж если речь зашла о ЕГЭ.
|
|
👍 +1 👎 |
Спасибо всем. Я узнал много интересного. Моя задача действительно задача 20-ой Межрегиональной олимпиады школьников по математике и криптографии (1-ый тур). Особенно спасибо за функцию Эйлера, её разложение для моего случая. Мои преподаватели доказывали это разложение сами без функции Эйлера.
Мне также оказалась очень полезна задача: 3/7+1/3 (mod 17). Поэтому спасибо Круглову и Якушевой. Мне никто подобную задачу не мог объяснить. |
|
👍 +1 👎 |
Совет Игорю. Почитайте книгу Г. Дэвенпорт "Высшая арифметика"
|
|
👍 0 👎 |
Найти собственные значения и собственные векторы линейного преобразования, заданного матрицей А
|
|
👍 0 👎 |
Мощность множеств
|
|
👍 0 👎 |
Найти число
|
|
👍 +1 👎 |
Порядок элемента группы
|
|
👍 0 👎 |
Помогите, пожалуйста, с заданиями по геометрии
|
|
👍 +2 👎 |
С6. Составное число.
|